How to select a Constraint Programming Solver

Question

I would like to clarify that I am absolutely not an expert when it comes to constraint programming (I happen to use it when it seems to be the right tool for the right job).

It is my understanding that the possibility to use global constraints can have a tremendous impact on how efficiently a problem can be solved.

However, not all global constraint are implemented in all constraint programming solvers. For example if I use the global constraint catalog to search existing global constraints, I will find out that the AllDifferent constraint (which represents the fact that no two variables of a given subset of the variables of the problem should take the same value) is implemented, under different names, in quite some constraint programming solvers. On the other hand only two solvers are referenced as implementing the increasing constraint is referenced as only being implemented by three solvers.

Here comes my question:

When using constraint programming, do you first write the model, trying to use global constraints when possible, and later on select which constraint programming solver you are going to use based on the availability of those global constraint? Or do you have a set constraint programming solver that you always use, no matter which global constraint you actually need (implementing the needed global constraint yourself if needed)?

Answer 1

@Rob wrote a great and extensive answer, but I would like to add two systems.

• MiniZinc is a high level CP system that is great for learning CP, prototyping problems as well as testing different solvers. MiniZinc first flatten a MiniZinc (.mzn) model to FlagZinc format (.fzn) and there are quite a few CP solvers that supports the FlatZinc format, e.g. Gecode, Chuffed, OR-tools, SICStus Prolog, JaCoP, Picat (CP/SAT), etc (they are listed in the MiniZinc main page). There is also an MiniZinc IDE where some of these solvers are included.

  An example of the high level syntax of MiniZinc is the element constraint x[y] = z where x in an array of decision variables, y and z are decision variables. The constraint constrain z to be the yth value in x. Most other CP languages write this constraint as something like element(x,y,z). Thus this syntax in MiniZinc makes it a little easier to write and understand the constraint.

  MiniZinc support quite a few global constraints, though if a FlatZinc solver supports a specific global constraint, it will use its own instead.

  There is also an yearly MiniZinc Challenge where FlatZinc solvers are solving a number of different MiniZinc models. Last year, OR-Tools dominated the challenge completely. Most MiniZinc models and instances of former challenges are collected at GitHub,

  One drawback of MiniZinc is that it is not a - Turing compatible - programming language, but it is quite easy to spawn a MiniZinc process to solve a problem, and some systems have this integrated (e.g. SICStus Prolog, ECLiPse CLP). And if you are into C++ it is not that complicated to integrate it even more.

  And here's my MiniZinc page with a couple of examples, small and large.

  To summarize, MiniZinc is great for learning the concept of Constraint Programming and for prototyping. If one need to use another programming language, it's often quite easy to port the MiniZinc model to another CP system.

• Picat Well, I have to add it to the list since I am in the Picat team and I really like Picat as a CP system. :-)

  Picat is a logic-based multi-paradigm programming language inspired by Prolog. The creator of Picat - Neng-Fa Zhou - is also the creator of B-Prolog (which is used in Picat's engine). This Prolog inspiration is seen for example with the support of non-determinism, but Picat also supports for loops, while loops, re-assignments, indexing of lists/arrays etc.

  Picat supports a couple of constraint solving modules: MIP (GLPK and Gurobi), SAT, and SMT (z3 and cvc4); all these solvers has support for the same syntax/constraints (with exception of MIP solver which only supports linear constraints). The PicatSAT FlatZinc solver has done quite well the last MiniZinc Challenges.

  One feature of Picat that I - mostly - like is that the order of the constraints are important when using the CP module. In most CP systems the order of the constraints does not matter, but in Picat (for the CP module) the order might make a difference and this is one other way to make a model more efficient.

  (Picat also has a planner module for traditional planning problems, but this is a bit out of scope of the question.)

  We wrote a book Constraint Solving and Planning with Picat about how to use Picat for Constraint Programming problems (as well as planning problems). The freely available PDF. I hope that the two chapters about CP might be useful as an introduction to CP in general.

  Also, My Picat page has quite a few examples of Picat models.

• For harder CP problems, it's no uncommon have one have to tweak the model to make it fast enough. Most CP systems has a different ways of doing that:

  • selecting the order of variables to test (variable selection)
  • when testing a specific variable, selecting the order of the values to test (value selecting).

  Unfortunately, selecting these is - as of now - and art and one have to test different variants.

  Also, there are some "tricks" that often speed things up, apart from finding the best variable/value strategies, e.g. symmetry breaking and adding redundant constraints to prune the search tree.

A side note: @Rob mentioned that I don't blog anymore which is correct. Instead I write - occasionally - at - Facebook - Twitter - StackOverflow, mostly answering questions about MiniZinc and Constraint Programming - And publish stuff on GitHub

Answer 2

... Do you have a set constraint programming solver that you always use, no matter which global constraint you actually need (implementing the needed global constraint yourself if needed)?

Find one that is well supported, that you understand to some extent, and that is powerful enough (speed and expressiveness) to suit your future needs. Invest your time in choosing a good tool and learning to use it well, then implementing constraints will be easier than struggling with a tool that is inadequate for the job.

There are online tools for linear optimization, constraint solving, even an extension for Microsoft Excel called OpenSolver which extends Excel’s built-in Solver with more powerful solvers. Constraint Logic Solvers are available which run on many different languages:

• Java-based constraint solvers
• C-based constraint solvers
• C++ -based constraint solvers
• C, C++, Python and Tcl based constraint solvers
• C++/Java/Python/Scheme and Smalltalk-based constraint solvers
• Python-based constraint solvers
• PROLOG-based constraint solvers
• VB.NET-based constraint solvers
• Mozart-Oz-based constraint solvers
• Other constraint solvers

Which to choose is partly a function of many things. Different Contraint Programming Solvers perform better than others in benchmarks, speed and ability is one aspect to consider.

Focus on how easy is it to learn a system, and the modelling aspect. Consider the syntax, element constraint, reification and defining predicates (decompositions). Look for community support and the number of examples, documentation, etc.

You'll notice that Google's OR-Tools has a Stack Overflow tag for OR-Tools and is free. In Java, there's OptaPlanner (StackOverflow) and Choco (StackOverflow), both open source too. OR-Tools is placed well in the benchmarks:

"OR-Tools is an open source software suite for optimization, tuned for tackling the world's toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming.

After modeling your problem in the programming language of your choice, you can use any of a half dozen solvers to solve it: commercial solvers such as Gurobi or CPLEX, or open-source solvers such as SCIP, GLPK, or Google's GLOP and award-winning CP-SAT.".

Further afield are proof solvers such as ACL2 (A Computational Logic for Applicative Common Lisp), an extension to Lisp which is itself an extensible theory in a first-order logic, and an automated theorem prover. It represents a difficult uphill climb, but it produces programs capable of proving themselves to be correct.

If you visit the GCC you'll notice that they describe the global contraints in Prolog (and XML) so if you want to rely on that reference it's helpful if your Constraint Logic Solver is written in (or accepts) Prolog (or that you are fluent in that language).

"Constraints
Constraint logic programming extends Prolog to include concepts from constraint satisfaction. A constraint logic program allows constraints in the body of clauses, such as: A(X,Y) :- X+Y>0. It is suited to large-scale combinatorial optimisation problems and is thus useful for applications in industrial settings, such as automated time-tabling and production scheduling. Most Prolog systems ship with at least one constraint solver for finite domains, and often also with solvers for other domains like rational numbers.".

There are global constraints in SICStus Prolog, and five libraries: Constraint Handling Rules, Constraint Logic Programming over Booleans (unsupported since release 4.0.7), Constraint Logic Programming over Finite Domains, Constraint Logic Programming over Rationals or Reals (unsupported), and a Finite Domain Constraint Debugger - it's quite a full featured version of Prolog, but it's not free.

B-Prolog is a fast alternative and while it does have a tag on SO there's barely a dozen uses of it. But if you look at Wikipedia's comparison of Prolog implementations you'll notice that it has a feature set comparable to SICStus.

So you should probably favor a Prolog implementation, but there's no reason why you couldn't use Haskell. Which underlying language is used to run whichever solver is very much a personal preference, but choosing one language and a solver framework with a large community and numerous libraries for different solvers (or the ability to output for a long list of separate solver executables) ensures that you'll always be able to progress forward rather than getting stuck implementing missing features or asking for assistance.

Additional Info:

One way to try different solvers is to visit the NEOS Server, a free internet-based service for solving numerical optimization problems. Hosted by the Wisconsin Institute for Discovery at the University of Wisconsin in Madison, the NEOS Server provides access to more than 60 state-of-the-art solvers in more than a dozen optimization categories. There are 3rd party submission tools that allow you to write a simple program at home and submit your job to the server. See the NEOS FAQ for details.

A means to get your problem solutions reviewed is at OPTIL.io, an on-line judge system that receives algorithmic solutions of optimization problems in a form of source code from the crowd of developers, compiles it, executes in a homogeneous run-time environment and objectively evaluates using the set of test cases. Problems that are solved can be provided by external companies or scientists. Solutions can be submitted in almost any programming language.

A good tool to compare some of the popular solvers is the Apache Software Foundation's Constraint Programming Solvers comparison tool. For example comparing Choco, Picat, and OR-Tools shows that OR-Tools requires quite a lengthy specification compared to Picat, while Choco is certainly more mature and supports more Global Constraints.

Hakan Kjellerstrand's webpage and blog on Constraint Programming while not updated in the past year has a decade of archives and (amongst numerous other pages) a webpage about Global Constraints, also one on Operations Research.

Wikipedia's has webpages on: Constraint Satisfaction and Hill Climbing (but nothing for Late Acceptance Hill Climbing (LAHC)). LAHC is one of the techniques employed by OptaPlanner, an AI constraint solver. Google returns over 70M results for "Late Acceptance Hill Climbing" - lesson: don't let one site's miss (due to chosen search terms) make you miss out on other results, check multiple search terms and search engines. Another search term to use is "Late Acceptance Anytime Algorithm" (related to LAHC) which returns another 56M results.

Some of the newest directions have the least information available, it's important to do your own research and determine which direction you wish to go. Breakthroughs in AI and Neuromorphic Computing are frequent enough that best laid plans go awry a few years later; but as long as the legacy tools you have available are sufficiently capable and fast enough for your needs you shouldn't worry about bleeding edge too much, nor completely discount it either.

The website arXiv has 3761 results for "Constraint Programming" and is an excellent source for researching the latest techniques.

I would like to clarify that I am absolutely not an expert when it comes to constraint programming (I happen to use it when it seems to be the right tool for the right job).

A description of the bottom-up and top-down proof procedures used for searching the problem space gives some insight into choosing your tool and approach.

Answer 3

If you're looking for objective metrics, such as GitHub stars, commit rates, contributor counts, StackOverflow question count and other usage statistics, libhunt covers constraint solvers at least for Java:

• Java constraint solvers

Warning: objective metrics don't tell the entire story.