Comment by lifebeyondfife | Hacker News Reader

Comment by lifebeyondfife | Hacker News Reader

Parent Full thread

There are three phases to Constraint Programming: (1) Model (2) Constraints (3) Search & Propagation.

The first step in solving a problem with CP is to come up with a representation for a solution. This involves deciding what your variables will represent (in this case, "How many orders of each appetiser") and what is their possible domain of values (in this case, "0 to 10" has been chosen, quite arbitrarily).

The solver itself is generally dumb. It will propagate some constraints sensibly but mostly it will just search over the entire space - equal to the size of the domain to the power of the number of variables. 11^6 = 1.8 million, quite a small CP problem.

There's a bit of an art in creating a good model for a CSP (Constraint Satisfaction Problem) to keep the search space as small as it needs to be.

EDIT: Just to be clear...

The way constraint solvers work is to make a decisions in a Depth First Search manner and judge the validity of the new state after each choice. So after fruit > 7 and salad > 2, bounds consistency on the constraint will rule out the possibility of reaching a solution from that node in the search tree.

> The solver itself is generally dumb. It will propagate some constraints sensibly but mostly it will just search over the entire space - equal to the size of the domain to the power of the number of variables

This is false. The cornerstone of solving interesting constraint programming problems is the ability to effectively propagate constraints. Naturally, since constraint programming models NP-complete problems, a large part of all problems will take exponential time. However, when propagation does not help and the solver effectively searches through all combinations, that is a failure mode. It is precisely the cases where propagation reduces the amount of combinations explored that are interesting.

From the similarity of our answers below I see we've got a similar understanding of constraint programming.

For loosely constrained problems, yes, constraint programming will enumerate exponential combinations and that's not a good fit for this methodology. The point I was trying to guard against is that the solver isn't smart and therefore when asking, "Is it smart enought to know X?", I'd say it depends.

If the solver in question has some decent bounds propagation on the six or so binary arithmetic constraints in the problem, then no, it won't enumerate all 1001^6 combinations (assuming domains of size 1001).

A more helpful answer from me would have been, "It's unknown if it's smart enough, but the more constrained i.e. the more combinations your constraints reject, the better".

Seeing as there were four solutions out of 1.8 million states (in the domains of size 11 example), that's very constrained.

I think it is a mistake to try to characterize when CP works based on constrainedness or on the number of solutions. In fact, being loosely constrained is typically used to imply that a problem is easy. The problem for CP is when a problem is NOT loosely constrained, but propagation is weak. This means that whatever reasoning we can do with the set of constraints, we cannot express as value prunings.

As for the number of solutions vs constrainedness: as far as I know, the only domain in which there exists a clear theoretical understanding of number of solutions vs difficulty is random problems, where we see an "easy-hard-less hard" pattern as we increase the density for a fixed size problem. What happens there is that there is an exponential number of solutions in the easy region which form a small (polynomial number) of very big clusters. As we get to the hard region, the number of solutions remains exponential, but the solution space shatters into an exponentially large number of clusters. The definition of a cluster in this case is: if two solutions have constant Hamming distance, they are in the same cluster. On the other hand, some unsatisfiable problems (so 0 solutions) are very very hard for CP and related approaches.

All this is just to say that the picture is much more complicated than you say and the best way to figure out if CP is a good fit for an application is to try it. People develop intuition over time of course, but the issue is far from understood.

No, solvers do no-where near 1.8 million nodes.

The solver I work on (minion), which is not optimised for arithmetic problems, or easy problems, does 86 search nodes when finding all 4 solutions. It makes no differences if the domains are 0..10, or 0..100000, in terms of either speed or search size. I would be amazed if any CP solver doesn't tighten the bounds straight away to something like:

    {0..7},{0..5},{0..4},{0..4},{0..3},{0..2}

Yup pure laziness as it was a toy problem. Though in my experiments with a gecode sudoku model its propagation was amazing, reducing the search space to a handful of branches. Another toy problem of course but one of a significantly larger size. Am I over estimating the power of propagation?

Propagation power really depends on the problem. For some problems, propagation is amazingly good, and for some it does not do much at all.

One can characterize propagation algorithms for the amount of propagation they do. A domain consistent propagation algorithm will make all deductions that are possible to make in a certain state, removing all values for variables that are not a part of any solution to that constraint. Loosely, a bounds consistent propagation algorithm will do the same, but only for the bounds of the variables.

The constraint used in Sudoku (called all_different or distinct) has really good propagation algorithms (both bounds and domain consistent), and is one of the cornerstones of constraint programming.

No, you're not overestimating it but it very much depends on the problem and constraints. It's good to do the d^n search space check to give you a feel for the starting size of the problem but if your problem is heavily constrained i.e. the constraints make finding a solution hard, then propagation is very powerful.

Consider variables a[1:1000] and b[1:10] and constraint a + b = 10. A good solver will use propagation to reduce that to a[1:9] and b[1:9] because there is no support for a >= 10 or b >= 10. Even reducing one extra value from a variable's domain is reducing the search space by a factor so propagation over tight constraints is extremely powerful.

Most arithmetic constraints like those used in your program will use bounds consistency (find support for the lower and upper bound values). Special constraints such as "all different" have their own propagation algorithms that efficiently remove potential values from the domains of multiple variables. These are known as Global Constraints.

Reply on news.ycombinator.com