In theory
A strong MIP formulation is one where the Linear Programming (LP) relaxation provides a tight approximation to the convex hull of the integer feasible solutions. The closer the LP relaxation is to the convex hull, the tighter and stronger the formulation is, and typically, the faster it will be solved.
In practice
We attempt here to distinguish weak MIP formulations from the perspective of the models and associated physical systems, rather than the underlying theory.
Consider examples where objects need to be placed in a certain non-overlapping layout so that the used area (or the overall capacity) is minimized. Typical applications can be found in industry: chip layout design, job scheduling across 2 dimensions (e.g., time and memory for assigning compute jobs to servers) or simply any factory machinery layout (e.g., in steel production factories). This no-overlap restriction is primarily ensured via discrete variables, representing the main complexity in the associated MIP models and rendering them potentially challenging.
Example: The Rectangle Packing Game
The objective of this game is to rearrange the rectangles, in order to minimize the amount of space being used, without letting the rectangles overlap. The lower the final score, the better. Please, watch from minute 10 in Tech Talk & Chat– Converting Weak to Strong MIP Formulations - Gurobi Optimization for a short demo of the game.
Layout and score associated with the best integral solution:
Score: 106250
Layout and score associated with the best relaxed solution:
All components are positioned in an overlapping manner at the upper-left corner.
Score: 75000
What is important here is to compare the physical systems associated with the MIP model and its LP relaxation (as visually represented in the above example). If there are significant differences/disconnects, then this typically implies a weak formulation. Sometimes, it might be more insightful to consider algebraic or geometric interpretations, whenever applicable.
What are the implications on the MIP solving?
To put it simply, the solution process starts with an LP relaxation, where all discrete components in a model become continuous. Solving this relaxation yields an initial dual bound. During the Branch-and-Bound process, all those originally discrete components are being gradually fixed.
In case of a weak MIP formulation, the solution of the LP relaxation provides a (loose) dual bound that is quite far from the true optimal solution and, therefore, the gap between them is not easily closed.
| Weak formulation | Strong formulation | |
| Algorithmically | The tree search might need to spend a lot of effort to repair the LP relaxation solution(s) along the way. As relaxing integrality gives access to unrealistically favorable solutions and associated objective values, the learned information could potentially be deceptive due to this unrealistic aspect. | The relaxation model of the physical system is reasonably/realistically well-connected to the (physical) system's MIP model. Therefore, the search tree has better information and must spend a lot less effort to repair the LP relaxation solutions. |
| Signs in the Gurobi log |
See the documentation on MIP Logging for more details. |
There is generally a good progress in the dual bound. |
A weak initial dual bound can or can’t be fixed over time during the solution process. That’s why we would be truly calling a formulation weak if this is manifested in the solving process, as the runtime behavior is what matters in practice.
We consider then the weakness as a symptom of the solution process, rather than a property of the formulation.
Our Tech Talks on how to improve weak formulations are a great way to get started with this topic:
- Tech Talk & Chat– Converting Weak to Strong MIP Formulations - Gurobi Optimization
- Tech Talk & Chat– Converting Weak to Strong MIP Formulations, Part II - Gurobi Optimization
The above material is highly based on the content covered there.