Constraint Solving with MiniZinc

The most succinct difference is (usually) a constraint solver is going to find a solution (or the best solution) while a DFS logic will attempt to enumerate all solutions.

For example, consider a geometric problem of placing a point on the plane according to constraints (such as left of line AB, above line CD, etc.) Assuming a solution exists, there might be a whole region of solutions (for example three lines might describe a triangle where any point inside the triangle is a solution).

A linear constraint solver is going to give you an answer of an arbitrary point in the triangle. It is not going to give you a stream of results "1.00,5.00; 1.01,5.02; 1.02,5.04; etc." If you want that you need to perturb some of the inputs to the solver to change the output. In other words there is no built-in combinatoric enumeration order.

In contrast, a depth first solver would output exactly that, because that's how it also views the problem internally - by enumerating options. It may be sophisticated in ruling out scanning parts of the space which can't be in the solution, but it can't avoid enumerating partial solutions which are part of a full solution because that's how the algorithm works. It would be the same as an implementation leaving arbitrary rows out of a table join in SQL - the algorithm depends, for correctness and completeness, on that not being done.

(Note again the distinction between leaving out partial solutions that are part of a full solution versus leaving out searching entire regions which can be ruled out of ever being a solution. So I'm not arguing that it has to brute force solutions I'm making the more nuanced argument that the "row count" is significant in data flow within a DFS logic engine in a way that is not even a concept within a linear constraint solver's data flow. Or to put it another way, within a linear constraint solver there's only ever "one row" but it is kind of fuzzy what the values of the columns are.)

However unlike a strictly linear constraint solver minizinc also supports either-or constraints so I don't know how much that changes the above. I would be interested to find out if MiniZinc tracks the combinatorics of multiple either-or constraints in the way that a Datalog or SQL would - I suspect it instead treats them all as interchangeable and indistinguishable rather than enumerable.

Another difference between constraint solvers and DFS logic is generally you can pick an arbitrary variable in a constraint solver and change it's value an recalculate the model. In a DFS logic you generally cannot do that; at most you could (at the implementation level not the user level) unbind and rebind the most recently bound variable, or unwind the stack and recalculate from an earlier point.

https://www.reddit.com/r/MiniZinc/

http://hakank.org/common_cp_models/ is a page which collects models that solve the same problem in different CP systems (and mostly with the same approach). It can be used to compare similarities and differences between systems, though one have to do the comparison oneself.

A long time ago (in 2012) I did a talk on comparing features in different CP systems mostly focused how "easy" - subjectively and IMHO - it was to learn the systems: http://hakank.org/constraint_programming/sweconsnet_talk_201...