3
$\begingroup$

I have some experience with linear and integer programming modeling (I read Model Building In Mathematical Programming by Williams).

Now I am trying to learn how to model with constraint programming. Is there some rule of thumbs on how to pass from an IP way of modeling to a CP way of modeling?

Unfortunately, I didn't found a similar book on CP modeling. I am aware of an online course in coursera but I do prefer books. Moreover, I am interested in comparing LP/IP models to CP models and not only to learn CP modeling.

$\endgroup$
2
  • $\begingroup$ Possible duplicate: or.stackexchange.com/questions/1500/… $\endgroup$
    – rasul
    Dec 31 '20 at 0:14
  • $\begingroup$ @r.beigi This is not a duplicate. However, the title could be changed to reflect the actual question which asks for resources on modelling for constraint programming solvers. $\endgroup$
    – Dekker1
    Dec 31 '20 at 0:46
8
$\begingroup$

There are many resources available to learn constraint modelling. When learning about constraint modelling I can recommend the following books:

  • Principles of Constraint Programming by Krzysztof Apt is probably the most used constraint programming book that will teach you all the aspects of constraint programming.

  • The book that would most fit your description might however be Building Decision Support Systems by Mark Wallace. This book focuses on the modelling of combinatorial problems using the MiniZinc constraint modelling language. Although MiniZinc can be used with both integer programming and constraint programming solvers (and even more kinds of solvers), its original design is as a standard input language for constraint programming solvers and the techniques learned can be transferred to other constraint programming solvers.

  • Another book that is often used is Handbook of Constraint Programming by Rossi, van Beek, and Walsh. This book is written from the perspective of artificial intelligence and will focuses on the search techniques employed by constraint programming.

Apart from books there are many (written) tutorials dedicated to constraint programming:

  • Gecode, one of the most used constraint programming solver, provides the Modelling and Programming with Gecode (MPG) handbook. This handbook is probably the best and most complete resource that is dedicated to the implementation (i.e., building the model) of constraint models and how a solver will handle these models. It even covers extensions possible to the solver, one of the big strengths of constraint programming that is often overlooked. As the name suggest, some parts are very specific to the Gecode solver and might not be applicable to other solvers. (That is not necessarily a problem since Gecode is one of the fastest constraint programming solvers).

  • More focussed on modelling, MiniZinc provides an online tutorial to get started with the language. This tutorial introduces all concepts of constraint modelling at a fast pace.

Finally, depending on your interest there are also a few books on Constraint Logic Programming that I can recommend: Programming with Constraints by Mariott and Stuckey and Constraint Logic Programming by Mark Wallace.

P.S. Although I know you were specifically looking for a book, I would really recommend the Coursera courses Basic Modelling for Discrete Optimisation and Discrete Optimistion for anyone who wants to learn constraint modelling and wants to get some hand on experience. Since it actually allows you to be automatically graded on going from a problem description to a constraint model, there is no better tool to really get a feel for how to model well.

$\endgroup$
2
  • $\begingroup$ Note that there are probably many other books and tutorials for tools out there. I've focused on the ones that include the topic of modelling (with more than giving examples) and ones that were helpful for me. I'm happy to include others in the list when prompted. $\endgroup$
    – Dekker1
    Dec 31 '20 at 0:44
  • 2
    $\begingroup$ Hello Dekker1, thanks for the detailed answer. It already helps a lot! Yes please, feel free to suggest further resources. My plan is to lean 1. How to properly model and 2. How the internals of a solver work. I plan to implement a mini CP/CP-SAT solver for learning purposes. $\endgroup$ Dec 31 '20 at 14:23
8
$\begingroup$

When I started learning CP (coming from IP), one of the first things I discovered is that model elements are less standardized in CP than in IP. An IP model typically contains a polynomial objective function and equality/inequality constraints involving polynomial functions (where you are hoping the polynomials are linear or at worst quadratic). Beyond that (and declaring types and bounds for variables), about the only model constructs I can think of are SOS1/SOS2 constraints and indicator constraints. Most high quality MIP solvers understand all the above, and if the solver does not do SOS1/SOS2 or indicator constraints, they can be replaced with more equations and inequalities (involving binary variables). Differences among solver tend to be more on the solution technique side than in which model elements they know.

With CP, there are a lot more types of constraints. I would guess that any CP solver worth a look would implement the "all different" constraint, but beyond some basic core set of constraints it gets interesting. IBM's CP Optimizer, for instance, implements constraints specifically intended for scheduling problems, such as "end before begin" (task A must end before task B begins), which I don't think you will find in every (or even most) CP solvers. So building an IP model for a job shop is largely independent of the solver you choose, whereas building a CP model for a job shop very much depends on the solver.

Another major difference is tied to that profusion of constraints. There are things you can express directly in a CP model that would be either impossible or extremely painful to express in an IP model. I would characterize the "all different" constraint as moderately painful in IP. (There's a straightforward way to model it, using a separate binary variable for each possible value of the original variable, but you might not like having that many binary variables in your model.) My experience with CP is limited, but the CP solvers I've seen have all been able to index a variable with a variable (i.e.,deal with the expression x[y] where x is a vector variable and y is a scalar variable that chooses one component of x). You can usually (always?) do the equivalent in an IP model, but it again involves copious binary variables and copious additional constraints, makes the model difficult to read, and has been known to cause severe brain cramps. In CP, the equivalent is as simple as writing "x[y]" or using a build in constraint function along the lines of "select(x, y)".

Other differences include the following. LP/IP tends to "like" continuous variables and "tolerate" integer variables, in the sense that integer variables make solving harder. CP tends to "like" integer variables (with finite, preferably small, domains) and "tolerate" continuous variables. How, or even whether, a CP solver handles continuous variables will differ among solvers. IP models tend, at least in my experience, to have tighter bounds than CP models do (although I'm sure someone can find exceptions), which means it may be a bit easier to tell how good your intermediate IP solution is compared to how good your intermediate CP solution is.

$\endgroup$
2
  • 1
    $\begingroup$ Interesting thoughts. I think one of the complexities/hurdles in developing CP solvers is the combinatorial nature of optimizing different generic constraints together. For instance, if the CP model has constraints C1, C2 and C3, it may be better to take a different approach to solve it compared to a model that only has constraints C1 and C2. As a result, it is hard to efficiently handle an arbitrary number of constraint types in a model. The good thing about MILP solvers is that they do not suffer from this issue as long as constraints can be represented linearly. $\endgroup$
    – rasul
    Jan 1 at 1:10
  • $\begingroup$ @r.beigi I had not thought of that. I don't know much about the internals of constraint solvers, but I suppose there may be questions about the best way to handle constraint propagation with multiple different global constraints, including the order in which constraints are checked. $\endgroup$
    – prubin
    Jan 1 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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