Strengthening Mathematical Formulations in Optimization Applications

Picking up where our March 2022 Tech Talk left off, Dr. Steven Edwards, Dr. Ed Klotz, and Dr. Richard Oberdieck hosted our most recent talk to explore three real-world applications that demonstrate how we can identify and strengthen weak MIP formulations to achieve significant speedups.

What Is a Weak MIP Formulation?

In our previous Tech Talk, we learned that a weak MIP formulation is one in which the dual bound moves very slowly.

To understand why a formulation is weak, you can compare the physical systems associated with the MIP and its LP relaxation. If your comparison shows any significant differences or disconnects, this typically implies a weak formulation. You can also consider the algebraic or geometric interpretations, depending on which one yields more insights.

Examining Weak Formulations in Real-World Applications

For our first real-world application, Dr. Edwards examined a customer model that structurally resembled a classic facility location problem and explained why disaggregating the constraints is a good idea in this context.

On multiple occasions at Gurobi, reformulating our customers’ models into disaggregated form has resulted in speeds up to 200 times faster.

Of course, this will not always be the case, and results depend a lot on the objective and structure of the given problem. However, as Dr. Edwards explains, disaggregating your constraints can be a worthwhile experiment if you want the optimal solution and can afford to wait.

Dr. Oberdieck explored the real-world application of offshore wind farm cable design and made the case for a hidden mixed-integer rounding cut. Identifying such hidden structures can bring significant benefits, as we saw in Dr. Oberdieck’s example, where it helped bring the model’s solve time from hours down to seconds. However, care must be taken to understand why such structures exist and whether they are impacted by changes in the business logic.

Finally, in Dr. Klotz’s lot-sizing example, we examined a model currently listed as “hard” on MIPLIB 2017, but which Gurobi 9.5 solved in just 50 minutes, with 8 threads. Dr. Klotz explored how we can do even better by examining the node logs and tightening the model. The result was a 50% reduction in run time for both 8- and 32-thread runs.

Watch the Full Tech Talk

It’s easy (and even common) to create weak formulations, especially when they represent the more natural way of thinking about underlying business problems. But once you’ve identified a weak formulation, digging deeper to understand the source of that weakness is essential in order to strengthen the formulation and achieve a speedup.

In many cases, a bit of performance tuning and parameters might be all you need, especially when you’re working with a state-of-the-art solver like Gurobi. But when that doesn’t work, there are strategies you can use to tighten the existing formulation or reformulate it. For an in-depth exploration of these strategies, be sure to watch our complete June 2022 Tech Talk: Converting Weak to Strong MIP Formulations, Part II.