Hacker News Reader

Comment by mzl | Hacker News Reader

> 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.

View on HN

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.

Reply on news.ycombinator.com