10
$\begingroup$

I am looking for resources to learn constraint programming. I will divide the resources I am looking for in three types:

Modeling
Is there resources (books, articles, courses, etc.) that are equivalent to Model Building in Mathematics by Paul Williams but in constraint programming modeling?

Knowing how a CP solver work

I am looking for resources to learn just enough information on how the solver work. I guess that knowing some of those information could lead to better modeling/debugging.

What to do when a solver is not efficient ?

Is there techniques to use when using a CP solver is not sufficient from the performance point of view? For example, in integer programming there is matheuristics or decomposition methods. Is there similar methods to use with constraint programming. Maybe a mix of metaheuristics and constraint programming or some decomposition methods related to constraint programming.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
11
$\begingroup$

Here's a complement to @jnmonette's and @A.Omidi's answers.

The best book that covers CP in detail is "Handbook of Constraint Programming" (https://www.amazon.com/Constraint-Programming-Foundations-Artificial-Intelligence/dp/0444527265). However, it's from 2006 so it don't discuss the more recent development in CP, such as lazy clause generation and integration with SAT solving techniques. But all the foundations of CP are there so it's a great read.

A slightly more recent - and in part more technical - book is Guido Tack's doctoral thesis "Constraint Propagation - Models, Techniques, Implementation" (2009) (https://www.gecode.org/publications/2009-02-24-constraint-propagation---models--techniques--implementation.html ) . Guido is one of the main developers of Gecode and the thesis explains very well Gecode under the hood.

Regarding CP modeling, there are unfortunately very few books on this. One of the best is Gecode's documentation "Modeling and Programming with Gecode" (https://www.gecode.org/documentation.html ). It explains a lot of models and different approaches for solving certain problems, including how to fix slow models.

I would also like to mention Helmut Simonis excellent tutorials on Constraint Programming with the ECLiPSe CLP (Prolog) system: https://www.eclipseclp.org/ELearning/

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the detailed answer :) Is there some papers that complement the "Handbook of constraint programming" ? $\endgroup$
    – Joffrey L.
    Commented Aug 18, 2020 at 17:43
  • $\begingroup$ @JoffreyL. There is a lot of CP papers. For example the Constraints Journal: springer.com/journal/10601 And also the submitted papers for the yearly CP conference ("Principles and Practice of Constraint Programming"). We should not forget the papers for CPAIOR conferences (main site: cpaior.org ). $\endgroup$
    – hakank
    Commented Aug 18, 2020 at 18:40
8
$\begingroup$

For modeling, I would recommend one of the following coursera courses, taught using the MiniZinc modeling language: https://www.coursera.org/learn/basic-modeling and https://www.coursera.org/learn/advanced-modeling

For knowing how a solver works, I can recommend the slides of the course "Combinatorial Optimisation and Constraint Programming" at Uppsala University, more particularly the second part of the slides (starting at T12) at http://user.it.uu.se/~pierref/courses/COCP/slides/ (The first part covers the modeling bit, so is also of interest.)

You can certainly also look at this coursera course: https://www.coursera.org/learn/discrete-optimization (which covers much more than just constraint programming).

Regarding the last question, I would recommend looking up "Large Neighborhood Search" (LNS), which is some form of meta-heuristics technique on top of a constraint programming solver. I believe that most current solvers support LNS in a way or another. I can't think of a specific resource regarding LNS, apart from the paper that introduced the idea: Paul Shaw. Using constraint programming and local search methods to solve vehicle routing problems. In Proceedings of CP98, 1998.

More generally, you can find a bunch of relevant resources on this page, including books, solvers, and more courses: http://www.it.uu.se/research/group/optimisation/resources/constraint

Improve this answer
$\endgroup$
5
$\begingroup$

Constraint programming in its essence can be used to solve mixed-integer programming problems but, not for all cases is efficient. It is frequently used in the scheduling problems to solve the large scale models in which, using BIP/MIP is a bit complicated and need some special methods like decompositions.

For more details, would you see this or this useful links? Also, there is a nice introduction to CP optimizer which has been published by Philippe Laborie.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.