Mathematical programming versus constraint programming¶
Mathematical programming and constraint programming are two technologies critical to solving complex planning and scheduling problems.
At IBM®, we find 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, and 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 (for example: quadratic, MIQCP, and convex vs non-convex).
- A constraint programming model supports only discrete decision variables (integer or Boolean) and activity and time-based variables, while a 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, a 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 a mathematical programming engine will use different techniques such as a lower bound proof provided by cuts and linear relaxation.
- A constraint programming engine does not make assumptions on the mathematical properties of the solution space (convexity, linearity etc.), while a mathematical programming engine requires that the model falls in a well-defined mathematical category such as Mixed Integer Quadratic Programming (MIQP).
Mathematical programming / Constraint programming comparison table¶
| Mathematical programming | Constraint programming | |
|---|---|---|
| Conflict detection | Yes | Yes |
| Relaxation | Yes | |
| Lower bound and optimality gap measure | Yes | |
| Optimality proof | Yes | Yes |
| Modeler support | Yes | Yes |
| Model-and-run | Yes | Yes |
| Modeling limitations | Restricted to linear and quadratic problems | Restricted to discrete problems |
| Specialized constraints | Yes | |
| Logical constraints | Yes | Yes |
| Theoretical basis | Algebra | Logical inferences |