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.

Guidance for Your Journey

Gurobi: Always Free for Academics

We make it easy for students, faculty, and researchers to work with mathematical optimization.

Trusted Partners, at Your Service

When you face complex optimization challenges, you can trust our Gurobi Alliance partners for expert services.

We’ve Got Your Back

Our global team of helpful, PhD-level experts are here to support you—with responses in hours, not days.

Gurobi Newsletter

What's
New at Gurobi

News
Gurobi 10.0 Delivers Blazing-Fast Speed, Innovative Data Science Integration, and an Enterprise Development and Deployment Experience
Latest release enables data professionals to easily integrate machine learning models into optimization models to solve new types of problems.
 Learn More
Event
Webinar: What’s New in Gurobi 10.0
In this webinar, attendees will get a first look at our upcoming product release, Gurobi 10.0. We will summarize the performance improvements and highlight some of the underlying algorithmic advances, such as the network simplex algorithm, enhancements in concurrent LP, and optimization based bound tightening.
 Learn More
new content
Cost Savings & Business Benefits for Gurobi Customers
2022 Total Economic Impact™ Study Reveals A 518% ROI with Gurobi
 Learn More