What are the differences between Constraint Programming and MIP?

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, the propagation schemes 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 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 often weak.
• CP solvers are less effective on models with a significant number of continuous variables and are often limited to purely discrete problems.
• 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, e.g., the popular GeCode, or the Google CP solver.

Further information

• How do I model logical and general expressions?
• Where can I learn more about building optimization models?
• How do I determine why my model is infeasible?
• How do I find additional solutions to a model?