Solving a MIP is NP-hard. It can happen that small or seemingly "easy" instances require a long time to solve, or even to find a feasible solution. Occasionally, a lot of the difficulty in the solving procedure can be attributed to the so-called formulation weakness. Creating weak formulations happens often, especially when they represent the more natural way of thinking about the underlying business problem. It is important to be able to identify having a weak MIP formulation at hand as the plausible cause of poor performance.
A formulation is stronger if its constraints better approximate the convex hull of the integer feasible set. Gurobi has already a lot of built-in features to strengthen a MIP formulation. During presolve, for example, some bound strengthening and probing operations – which are inherently types of cuts – take place to enhance the formulation. However, this might not always be enough. That’s the situation where we need to think about using our model knowledge in certain ways to achieve that.
Suggested workflow
In general, it's hard to tell whether a model can be reformulated to improve performance. That said, the general advice is to approach this endeavor in an organized manner, having a strategy in mind, as opposed to randomly trying out different techniques.
The rule of thumb is to stay as close as possible to the business logic and try to depict that in a mathematical formulation. If it happens to show signs of weakness affecting the performance, try to strengthen the formulation. A formulation is good enough, as long as it serves its purpose.
We suggest the following general workflow:
- Create the initial formulation based on the business logic.
- Give the resulting model to Gurobi and observe the resulting performance.
- Consider at this step to experiment with parameter tuning.
- If the above still yields an unsatisfactory performance, consider strengthening the formulation in an organized approach as follows. It is noteworthy that model reformulations tend to have a greater impact on Gurobi's performance than solver parameters.
The first step to address a weak MIP formulation is to identify the culprit and understand the main reason behind the formulation's weakness. Often, this stems from a particular challenging aspect in the model that triggers a disconnection between the physical systems associated with the MIP model and its LP relaxation. Therefore, it is crucial to have a deep understanding of the formulation and the structure involving the objective and combination of constraints.
Below, we propose some practical measures that can be considered to make the formulation stronger, sorted from easy to difficult.
Consider numerical improvements
Sometimes, ideas for improving the model formulation can come from Gurobi's output. Gurobi generally reports potential numerical instability in the log file by printing corresponding warning messages. See What does "Model contains large matrix coefficient range/objective coefficients/rhs/bounds" mean?
Examining the coefficient statistics is often a good place to start thinking about ways to improve a weak formulation. In particular, large coefficients might already give some hints to the following improvement ideas:
- Changing variable definitions: You might need to think about providing good bounds for your variables using your problem-specific knowledge. Here, it would also make sense to revise the chosen units to express your variables and constraints so that they comply with the recommended ranges for variables and constraints: e.g., using Tons instead of Kgs. For more details, see the documentation on "Tolerances and User Scaling."
- Disaggregating constraints: An idea that might help to bring down the coefficient statistics to the recommended ranges could be to disaggregate a constraint to its component parts. As the disaggregation technique typically adds more constraints to the formulation, its computational advantage can be debatable. See Understanding cutting planes and how to make use of them for a more detailed discussion.
- Tightening big-M values: if the application doesn't provide a reasonable value for M, you might want to consider modeling your constraint(s) as SOS or general constraints to give Gurobi a chance to tighten those values. During presolving, Gurobi can often reformulate SOS constraints as big-M constraints, where the behavior can be controlled by the user via the PreSOS1BigM and PreSOS2BigM parameters. If many SOS constraints remain after presolve, it is worth investigating why. Note that SOS constraints allow the solver to branch on sets of variables instead of individual variables and are not considered within the LP relaxation. As a result, they are more numerically stable, however, they are typically associated with weaker LP relaxations. Big-M constraints are generally more preferred, as long as M is relatively small.
Add valid cuts to the existing model
The most common approach to strengthen a formulation is to introduce additional valid cuts to your model, aiming to cut off uninteresting regions in the feasible space of the LP relaxation in order to get as close as possible to the convex hull of the integer feasible set.
Example ideas of strengthening the formulation through additional cuts comprise: Mixed-Integer Rounding cuts, Clique cuts, resolving disjunctions and disaggregation. see Understanding cutting planes and how to make use of them for concrete examples and a more elaborate explanation of the underlying concepts.
Note that this approach comes at a cost of larger models and conceivably slower solutions of the node relaxations. One must pay attention that finding feasible solutions is not considerably delayed. Lazy constraints or cut callbacks might be of help to keep the relaxation size under control.
Re-visit the logic of the model
If all of the above doesn't help with the model performance, you might want to consider a more drastic reformulation where you attempt to approach the business logic differently. Often, many problem classes have opportunities for strong or weak formulations, e.g., facility location, scheduling, lot sizing etc.
Below, we focus on a classical example, namely the Cutting Stock problem, and consider two possible formulations for it to examine the differences. The goal of this problem is to cut sets of required smaller pieces from larger stock items - master buckets - while minimizing the total number of buckets being used, thus minimizing waste.
Formulation 1:
One straightforward way to formulate this problem is to think in terms of which required element/piece goes into which bucket. Two constraints will have to be satisfied: i) each element should be assigned to one bucket, ii) the bucket should not be exceeded (if used).
This formulation has a caveat that it has a weak LP relaxation. By relaxing integrality, it allows for fractions of elements to be assigned to buckets. Hence, it gives way to unrealistic objectives.
Formulation 2:
An alternative way to think about this problem is to switch the logic from assigning individual elements to the cut patterns of the master buckets, i.e., what are the possible ways in which a bucket could be cut? The decisions would then become which cut patterns to choose and how often? Those cut pattern options would have to be pre-computed and generated a-priori. The LP relaxation associated with this formulation is stronger than that associated with the previous one and famously provides much tighter bounds, as it has moved away from the possibility of violating the units of the individual elements.
Final remedy: change the algorithm
Finally, we can't talk about model with complicating aspects without mentioning decomposition algorithms. If a point is reached where it is not possible to add any more cuts, nor change the formulation any further, it is likely worth considering changing the algorithm and consider more sophisticated ways to solve the problem.
Coming back to the cutting-stock example, even the stronger formulation can be computationally demanding, as it doesn’t scale well; the number of patterns that should be generated could become quite large. A famous solution approach is to consider only a subset of patterns, i.e., the patterns that have the potential to improve the objective function. This is known as Column Generation approach: new cut patterns are generated to be added, by solving a sub-problem - i.e., the pricing problem - using the dual variables after solving the Master Problem.
Here is a notebook in the Gurobi modeling examples to walk the reader through a delayed column generation implementation in Gurobi to solve the cutting stock problem more efficiently. This approach has the potential of working nicely whenever the pricing problem fits a mathematical model that could be solved in a reasonable amount of time. For instance, the pricing problem in this example could be represented as a Knapsack problem.
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 material above is highly based on the content covered there.