TransWikia.com

Constraint programming resources

Operations Research Asked by Joffrey L. on November 28, 2020

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.

3 Answers

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/

Answered by hakank on November 28, 2020

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

Answered by jnmonette on November 28, 2020

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.

Answered by A.Omidi on November 28, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP