News for hackers. Stuff that matters.
Re:Send+more=money and how to use forward-checking in search by mzl on Wednesday July 21, 2021 @02:08PM (#27909834)
Arc consistency is not really a good term to use, since it was originally defined for 2-ary constraints only, but is sometimes used for n-ary constraints. That is why I use the term domain consistency consistently :-)

Given a propagator for circuit that reaches domain consistency (note, for the whole n-ary constraint), that is equivalent to a checker of there is a Hamiltonian path and that will most likely never be a polynomial algorithm (unless P=NP). I can’t say that I’m interested in any particular property of the decomposition of the constraint into 2-ary parts, it is not that interesting of a structure. The cool filterings that circuit propagators do are based on global analysis of the whole graph, not on any local property. For example by finding ordering a of strongly connected components in the current graph.

Almost all propagators need to be reasonably fast to be usable, that is sort of a given in this area. An exponential propagator is almost always a bad idea. For all_different there is a O(n^2.5) algorithm for domain consistency which is really cool and important. In practice, the simple value propagation (remove assigned values from the other variables) is often better for finding solutions quickly.

Re:Send+more=money and how to use forward-checking in search by dragontamer on Wednesday July 21, 2021 @02:14PM (#27909926)
I see your point, and my mistake in using "Arc Consistency" when that's mostly a theoretical (ie: binary constraints only) terminology.

Extending the concept of Arc-consistency out to general n-arity constraints leads to two, ambiguous generalizations. I took one generalization, you seem to have taken the other (because the generalization I took was uninteresting to the problems you are talking about).

Re:Send+more=money and how to use forward-checking in search by mzl on Wednesday July 21, 2021 @02:43PM (#27910305)
Yeah, it’s a suboptimal terminology, at least in my opinion.

I have a strong bias for the practical side of constraint programming systems, as may have come through.