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 developerWorks community.

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.

The purpose of this post is to give some pointer to material explaining constraint programming techniques to mathematical optimization practitioners. 

[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)

• Assign an id from 1 to m to each worker.  Two different workers have different ids.
• One integer decision variable per job.  The value of that variable would be the id of the worker that will perform the job
• One all different constraint on the set of decision variables

That is all.  The all different constraint captures the business requirement that one worker cannot perform more than a job in a day.

 

Let's contrast this with a mixed integer programming (MIP) approach.  One way to represent the problem would be as follow.

• Assign an id from 1 to n to each worker.  Two different workers have different ids.
• One binary decision variable for each pair (worker, job).  The value of the variable xij is 1 if and only if job j is performer by worker with id i.
• A set of constraints, one per job j,  stating that job j must be assigned one worker:
  • sum_i xij = 1
• A set of constraints, one per worker of id i, stating that this worker can perform at most one job
  • sum_j xij <= 1

We see the major difference in modeling capacity.  With CP we have n variables and one constraint.  In MIP we have nm variables and n+m constraints.  This way to map global constraints to MIP constraints using binary variables is quite generic, see for instance the nice paper written by my colleague Philippe Refalo on that topic. 

 

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.