Constraint Programming
Update on september 6 2013. Paul shaw made a great presentation on our Constraint programming Optimizer that complements this post nicely. Slides and replay are available in our deve
Constraint Programming is one of these key words you may have seen that eludes a precise definition. For some it is a computer programming language paradigm beside imperative programming or functional programming. Such people often speak about Constraint Logic Programming (CLP). For others, including me, it is a set of tools and technologies for solving combinatorial problems. The latter view implies that constraint programming is part of operations research. I will stick to that view and focus on the empirical use of constraint programming in what follows. [Disclaimer] What follows is based on my experience as the main designer and implementer of the former ILOG Solver product, which was considered the market leader in commercial constraint programming software as of 2006 (see Wikipedia and the Handbook Of Constraint Programming).
So, what is constraint programming? As said above I'll speak from the view point of someone having a business problem to solve, and looking for software tools that might help. Readers of this blog know that I am a proponents of mathematical optimization. Other tools and techniques may be relevant as well, and constraint programming is one of them.
Let me propose one definition for the sake of discussion.
The richer language is actually quite simple to describe. With CP you express a problem using decision variables, usually integer valued variables. You can also express an objective function, but it is more often used for satisfaction problems. So far we aren't really departing from traditional mathematical programming, are we? The main novelty of CP is the large set of modeling artifacts called global constraints.
Let's look at one such global constraint, the all different constraint. There are many more global constraints available, see for instance this catalog, but all different is probably the most popular one This constraint state that a given set of decision variable must be pairwise distinct. This is useful in many resource allocations problems. For instance, assume you have to assign one day jobs to workers. A given worker can only do one such job a day, hence one cannot assign two jobs to the same worker. In CP we would model this as follow (assume we have n jobs and m workers)
Let's contrast this with a mixed integer programming (MIP) approach. One way to represent the problem would be as follow.
CP is a clear winner on the modeling side given its ability to express a combinatorial constraint such as all different directly, instead of having to linearize it using many more variables. Let's look at the solving side now.
CP and MIP solves problems in a different way. Both use a divide and conquer approach, where the problem to be solved is recursively split into sub problems by fixing values of one variable at a time. The main difference lies in what happens at each node of the resulting problem tree. In MIP one usually solves a linear relaxation of the problem and uses the result to guide search. This is a branch and bound search. In CP, logical inferences based on the combinatorial nature of each global constraint are performed. This is an implicit enumeration search. I will point reader to this paper by Irv Lustig and I for more details.
It is difficult to give advice on when one solving approach is better than the other in practice. Let me just say that MIP is strong when the linear relaxation is tight. CP is good when the linear relaxation does not help, for instance in job scheduling problems. Since there is no general law, my advice is to try both in case you have a doubt. In order to ease this dual approach we have bundled our CP and MIP solver into one product, CPLEX Optimization Studio, so that the choice of technology can happen after your project starts. There are of course other CP tools, and one good source of information on them is Hakan Kjellerstrand's blog.
There is much more to say on CP and MIP than the above, and I'll revisit this topic in forthcoming posts. In the meantime I'd like to point readers to the paper I wrote with my colleague Irv Lustig on the relationship between CP and MIP. More information on our product is available on our CP Optimizer page. |