Constraint programming and The MiniZinc Challenge (2013)

You've just missed the problem submission deadline for the 2014 MiniZinc challenge[1], but if you've got a solver to submit, now is the time to apply! Last year was interesting, as or-tools[2] won a bunch of categories after a long reign by Gecode[3].

For those that don't know much about constraint programming: it is a declarative programming paradigm for solving highly combinatorial problems.

The basic idea is: you model your problem as a set of variables and a set of rules (constraints) on what values those variables can have in order to be a solution to your problem. For example, for two variables x and y, you might express the constraint that x ≥ y.

Once you've characterized your problem in this way, you can basically press a button and the constraint solver will find you one or all solutions by a combination of search and inference which intelligently pares down the search space. For best results, you can also specify the search strategy for the solver.

More interesting than the simple constraint example given above are global constraints, which can express relationships for more variables and can therefore use more intelligent inference than simple pairwise constraints. The traditional example is the all_different(x_1,...,x_n) constraint, which ensures that the variables upon which it is operating take on distinct values.

A lot of constraint programming research is oriented towards finding good algorithms for global constraints. These can then be re-used by any model which needs to express the same kind of relationship. There are already quite a lot of these; they can be found in the global constraint catalog[4].

[1] http://www.minizinc.org/challenge2014/challenge.html

[2] https://code.google.com/p/or-tools/

[3] http://www.gecode.org/

[4] http://www.emn.fr/z-info/sdemasse/gccat/