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.
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.
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.
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.
We make it easy for students, faculty, and researchers to work with mathematical optimization.
When you face complex optimization challenges, you can trust our Gurobi Alliance partners for expert services.
Our global team of helpful, PhD-level experts are here to support you—with responses in hours, not days.
GUROBI NEWSLETTER
Latest news and releases
Privacy Policy | © Gurobi Optimization, LLC. All Rights Reserved.
Cookie | Duration | Description |
---|---|---|
cookielawinfo-checkbox-advertisement | 1 year | Set by the GDPR Cookie Consent plugin, this cookie is used to record the user consent for the cookies in the "Advertisement" category . |
cookielawinfo-checkbox-analytics | 11 months | This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics". |
cookielawinfo-checkbox-functional | 11 months | The cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional". |
cookielawinfo-checkbox-necessary | 11 months | This cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary". |
cookielawinfo-checkbox-others | 11 months | This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other. |
cookielawinfo-checkbox-performance | 11 months | This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance". |
CookieLawInfoConsent | 1 year | Records the default button state of the corresponding category & the status of CCPA. It works only in coordination with the primary cookie. |
elementor | never | This cookie is used by the website's WordPress theme. It allows the website owner to implement or change the website's content in real-time. |
viewed_cookie_policy | 11 months | The cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data. |
Cookie | Duration | Description |
---|---|---|
__cf_bm | 30 minutes | This cookie, set by Cloudflare, is used to support Cloudflare Bot Management. |
Cookie | Duration | Description |
---|---|---|
CONSENT | 2 years | YouTube sets this cookie via embedded youtube-videos and registers anonymous statistical data. |
Cookie | Duration | Description |
---|---|---|
VISITOR_INFO1_LIVE | 5 months 27 days | A cookie set by YouTube to measure bandwidth that determines whether the user gets the new or old player interface. |
YSC | session | YSC cookie is set by Youtube and is used to track the views of embedded videos on Youtube pages. |