Mathematical programming and constraint programming are two technologies critical to solving complex planning and scheduling problems. At IBM, we've found that knowing both technologies is important in addressing some of the most difficult optimization problems. To make the most of each, it is important to understand their similarities and differences.
General model structure
A constraint programming optimization model has the same structure as a mathematical programming model: a set of decision variables, an objective function to maximize or minimize, and a set of constraints.
Modeling differences:
A constraint programming model natively supports logical constraints as well as a full range of arithmetic expressions, including modulo, integer division, minimum, maximum, or an expression which indexes an array of values by a decision variable.
A constraint programming model can also use specialized constraints, such as the "all-different" constraint, that can accelerate searches for frequently used patterns.
A constraint programming model has no limitation on the arithmetic constraints that can be set on decision variables, while a mathematical programming engine is specific to a class of problems whose formulation satisfies certain mathematical properties.
A constraint programming model has only discrete decision variables (integer or Boolean), while an mathematical programming model supports either discrete or continuous decision variables.
Optimization engine differences:
A constraint programming engine makes decisions on variables and values and, after each decision, performs a set of logical inferences to reduce the available options for the remaining variables' domains. In contrast, an mathematical programming engine, in the context of discrete optimization, uses a combination of relaxations (strengthened by cutting-planes) and "branch and bound."
A constraint programming engine proves optimality by showing that no better solution than the current one can be found, while an mathematical programming engine uses a lower bound proof provided by cuts and linear relaxation.
A constraint programming engine doesn't make assumptions on the mathematical properties of the solution space (convexity, linearity etc.), while an mathematical programming engine requires that the model falls in a well-defined mathematical category (for instance Mixed Integer Quadratic Programming (MIQP).
Mathematical programming / Constraint programming Comparison Table
| Mathematical programming | Constraint programming | |
|---|---|---|
| Relaxation | 
|
|
| Lower bound and optimality gap measure |
|
|
| Optimality proof |
|
|
| Modeler support |
|
|
| Model-and-run |
|
|
| Modeling limitations | Restricted to linear and quadratic problems | Restricted to discrete problems |
| Specialized constraints |
| |
| Logical constraints |
|
|
| Theoretical basis | Algebra | Logical inferences |
