"Alice, Bob, and Creo are splitting up candy. Alice is oldest so she should get the more than the others. Bob doesn't like to have 5 candies. Creo wants to have at least as much as Bob. There are 20 candies to divide, how do you split them?" This would be a classic example of a finite domain constraint problem. There are three variables (Alice, Bob, and Creo... let's call them A B and C) and they can have a value between 0 and 20 (the number of candies they get). There are some constraints; The sum of all candies owned must be 20 (or less..), so
A + B + C <= 20. Alice gets more than Bob or Creo so
A > B and
A > C. Bob doesn't want exactly 5 candies, so
B != 5. And Bob wants as many as Creo, so
B = C. There multiple solutions, one would be where Alice gets 7 and the others get 5. Or Alice gets 8 and the others get 6. But not Alice gets 3, Bob gets 5, Creo gets 17.
This is an intro to the concept of "finite domain constraint solving". The past year I've been working for a client on a library that does exactly this, in JS. And before I take you all on a deep dive into the magical world of fd solving, I think it's good to look at some of the basics. Here, we, gooooo.
Concept
I think the problem is conceptually very easy. The above describes it pretty decently, for the abstract version; There are some variables with a set of possible values they can take on (their "domain"). In this case those values are integers. And in our particular case,
>=0. There are constraints that apply certain restrictions between one or or more variables. The goal is to find a valuation of each variable such that no constraint is violated. Multiple solutions are possible, and usual, though most of the time you're looking for just any one.
A constraint is violated if it is not met. Simple as that. A constraint can be "A must be less than B". If A becomes 5 and B becomes 2 then the constraint is not met and it would not be a valid valuation. If A is 2 and B is 5 then the constraint is satisfied and it would be valid valuation. There are some core constraints like "less than", "equals", or "addition". There are also higher level ones that combine them. For example a "distinct" over some variables is basically a pyramid of "not equal" constraints, one for each unique pair of the variables.
The finite domain consists of a set of finite integers. The process of solving persists of repeating three steps; optimization, stabalization, and branching. You are said to be excavating a "search space". Each time you branch can be considered a node in the search tree (tree being the search space). There are various ways of traversing the search tree and the tree can be _huge_.
Huge
It's difficult to properly express the "hugeness" here. Consider the simple problem of
A >= B with
A = [0..20] and
B = [0..20]. There are
21 * 21 = 441 valuations to this problem and only about half of them satisfy the constraint. That total is your search space though. So if you have 5 variables with that same
[0..20] domain, then each var has 21 possible valuations and your variables have
21 ** 5 = 4084101 possible valuations. How many of them are valid totally depends on your constraints. As you can see the problem space grows rapidly.
For each variable you add, even if it's just a "boolean" variable which has
[0..1], you're growing the problem space by multiplying it by the number of values that var can have. If you're still uncertain just how big of a problem this becomes, read up on the
"Wheat and chessboard problem" on wikipedia.
Optimization
Now that we've illustrated the problem space to tackle, it becomes obvious why some optimizations are necessary. Remember, solving a problem takes three steps; optimization, stabalization, and branching. The optimization step consists of eliminating constraints and variables that are satisfied.
While solving you always reduce the domains, never grow them. Because of this, variables that have been "solved" (whose domain have been reduced to one single value) will no longer change the problem because their valuation can at worst reject the current branch. You don't need a variable for that. Instead, constraints that use solved variables can be "rewritten" to use a constant value instead. This usually makes them easier to solve, but at least reduces their complexity. The fewer (distinct) variables a problem has, the easier it becomes to solve it. This kind of pruning can have a huge impact on the problem space.
Constraints whose condition has been resolved can be eliminated. If constraints are broken then they reject the current branch and backtracking commences. Otherwise they will no longer influence the rest of the search and should no longer be evaluated. For example, if you have the condition
A > B and A can only be
[10..20] while B can be
[0..5] then there is no way that A ever becomes larger or equal to B. Hence there's no point in still checking the constraint and you should remove it from the problem.
This way the solving becomes a set of reductions of the problem. Each node of the search tree should get a, at least slightly, simplified version of the problem of the parent search node.
Stabalization
After optimization we get to stabilization. This is another form of stabilization that kind of goes hand in hand with the previous step. The idea is to reduce the domains of the variables as much as possible given the constraints. Most of the time the constraints may not immediately resolve but can at least limit the domains of its variables. For example, if
A > B then you can eliminate any value from A's domain that is lower or equal to the lowest value in B. Those values could never lead to a valid result so we shouldn't ever even consider them. This kind of reduction is applied for every variable. This may cause a chain reaction so you have to re-evaluate all constraints that are using vars that changed this way until no change is detected. At this point the space is "stable", but not necessarily solved.
In this context, "stable" means that we can not reduce the domains of the vars any further by deduction of the rules of the constraints. The constraints can not tell you anything about the domains without "trying", which will be the next step. For example, if
A > B and
A contains only a few values that are above B then the constraint is stable but not satisfied nor solved.
Branching
The next step is branching. You pick a variable and force reduce its domain somehow. Then you get two (or more branches depending on how you tackle that) and each branch gets a slightly different problem, each may or may not lead to a solution. For example, if you have A and B with
A = [10..20], B = [0..5] with some constraints and must branch. Let's say you start with A and set it to 10. You now have a new "constraint problem" with A explicitly set to 10 and must try to solve it. If it leads to a solution you're done (or could be). If it doesn't you'll need to backtrack and decide how to branch next. You could try the next number (11), or simply set A to the domain without 10, since you've at least proved by "reductio ad absurdum", or by proving it can only lead to an invalid result, that 10 can't be valid. Which says nothing about the other values in the domain.
Strategies play an important role in solving. While the actual solving is pretty fixed and a matter of fast and efficient trickery, the branching is all about strategy and the place to guide the search. That's where you the system tells you "I'm at a fork, do I take left or right?". This part can be quite involved and completely depends on your use case. There are two main types of strategy to consider; how to pick the next variable to branch on and how to pick the next value from the domain of the chosen variable. These are distinct though could be related. You could have vars that have specific strategy overrides like a var that you want to maximize ("when branching always try the highest number first"), or dynamic like a priority list of variables ("pick var A first, then C, then B") which becomes alphabetic once the list is exhausted. There are too many options here to mention, I'm sure you can think of some yourself.
Storage
Optimization is not only a speed concern. Remember the size of the search space. You can
easily exceed the memory of your computer by storing the entire state of the search for a complex enough problem. You'll have to come up with clever strategies and encodings of storing the search state. In fact, currently in
finitedomain my biggest enemy is the JS GC (garbage collection). It takes up about 50% of the runtime. 50%!! This is for large problems (>10k vars/constraints) which take between 500ms~1000ms). And trust me, I've been battling this for a while and I know what I'm doing. It's just that difficult. And fun. And complex. And frustrating. Did I mention fun? Yes, fun. It's a challenge. And an academic one at that.
The library
For the past year I've been working on improving a library that was forked from
FD.js. FD.js was the result of a research paper or something like that. And while it was sound,
despite my best efforts to incorrectly undermine that *cough* (
hey, honest mistake), couldn't scale. I don't think it was intended to be fast ("hur hur, fd solving in js are you crazy"), I'll save you further analysis on that part for a future blog post.
The original fork was translated to coffeescript (FD.coffee) and had some changes applied before I jumped in. Right now that fork has been translated (back?) to ES6 semantics and optimized to heck and stored under
finitedomain, where I'm pretty much the only contributor (at the moment). We're now at a place where I can feed it 25.000 vars and 35.000 constraints (propagators are low level constraints generated by the higher level constraints) and it will solve it under a second, ~650ms on my machine.
- FD Preparing...
- FD Prepare Time: 90ms
- FD Var Count: 25632
- FD Constraint Count: 18886
- FD Propagator Count: 34424
- FD Solving...
- FD Solving Time: 673ms
- FD Solutions: 1
- FD Solution Construction Time: 4ms
That. Is. Crazy.
This is not a contrived example or anything. It's an exported example of a heavy real world case of where
finitedomain is used in production. I use it as tentative perf case to make sure I'm not completely regressing.
Of course this doesn't mean much in terms of solve time itself. The potential space, even if all vars were boolean (and they're not) would be
2 ** 18886.
Wolfram Alpha claims this number has 5.686 digits. That's not a reasonable space to exhaustively search in ANY environment, so those 35k constraints must be cutting the problem down drastically (solution found in about 2000 steps, so yeah). OR the solution just happens to be "around the corner", possible and I'm not sure how likely that is for this case. Regardless, what it does demonstrate is being able to handle that many vars and constraints and trimming them down to a solution really really fast. In JS, mind you. This used to take seconds, minutes even.
Anyways. Finite domain constraints are really fun. They are a puzzle to solve and I really enjoy to solve them automatically. And to speed up that process. That task isn't done yet. There's still so much to do there...
More on this subject next time, I think. If I get around to it.