Constraint Programming (CP) is a field of mathematical programming which focuses on finding feasible solutions subject to some given constraints. Theoretically, it is as hard as mixed integer programming (MIP). The most prominent differences are
- CP algorithms use a search tree similar to MIPs but often, they don’t solve LP relaxations. They use advanced constraint propagation techniques instead of solving LP relaxations as the foundation of the search process. Basically they branch and propagate the branching variable bound change, using more sophisticated propagation schemes than those used in presolve and probing routines of a MIP solver. For many problem classes, this is less powerful than solving a continuous relaxation of the model, since the solution of a continuous relaxation can guide the search and provide dual bounds. However, it can be effective when the relaxation is extremely time consuming to solve or when the combinatorial structure of the model gets lost in the relaxation.
- CP engines have sophisticated modeling objects that are more elaborate than even Gurobi’s SOS, piecewise linear functions, and general constraints. This is useful in several ways, but it is also the reason why CP requires a great deal of expertise to be used effectively.
- CP Solvers can complement MIP solvers. They may be effective at finding good heuristic solutions that can improve MIP solver performance, particularly with respect to a first feasible solution.
- CP solvers perform well on, e.g., loosely constrained discrete sequencing problems with disjunctive constraints (for example, job shop scheduling) where the LP relaxation is generally weak.
- CP solvers are less effective on models with a significant number of continuous variables and are often limited to purely discrete problems.
Specific details
CP problems are not modeled the same way as models solved with a MIP solver, because one wants to take advantage of the more powerful CP modelling objects. Since CP often does not solve continuous relaxations, it implements a more effective propagation than what is usually done in presolve and probing algorithms within MIP software. One could view CP as branch-and-propagate rather than branch-and-bound or branch-and-cut.
Moreover, CP solvers are more brittle compared to MIP solvers as a small change to a CP model (for example, adding a constraint) can drastically impact the ability of the CP solver to find good solutions.
There certainly are cases where exploring a CP approach may be promising. Luckily, there are several open-source tools available. A very popular one is GeCode. Another option is the Google CP solver.