Converting Weak to Strong MIP Formulations: A Practitioner’s Guide

Ed Klotz () and Richard Oberdieck ()
Additional contact information
Ed Klotz: LLC
Richard Oberdieck: LLC

Chapter Chapter 4 in Optimization Essentials, 2024, pp 113-174 from Springer

Abstract: Abstract Enormous progress in Mixed Integer Programming (MIP) solvers has come from synergies involving the increasingly powerful computing environments on which they run and the algorithms they implement. Essential to the algorithmic improvements are mathematical techniques to strengthen weak formulations. The literature contains sophisticated mathematical theory to generate cutting planes that make the branch and bound algorithm most solvers use more effective by tightening the formulation of the model the solver receives. Nonetheless, numerous MIP models remain difficult or impossible to solve to optimality, as evidenced by the hard and open models in the MIPLIB test set. In addition, as larger and more difficult MIPs have become easier to solve, practitioners have responded by creating larger, more granular, and more difficult MIPs that pose new challenges for the solvers. The cuts implemented in the MIP solvers tend to be generic, looking for common structures and characteristics in MIP models from diverse sources. However, some models have more uncommon characteristics that elude the implemented cuts. Leveraging knowledge specific to their models can help practitioners create more customized cuts that strengthen the formulation in ways that significantly improve solver performance. Optimization practitioners with limited familiarity with the theoretical constructs regarding the strength of formulations may conclude that they lack the prerequisites to effectively strengthen their models. In this chapter the authors will argue that, while such knowledge is an extremely valuable asset, it is not always needed to effectively tighten formulations. After reviewing some previous work in this area and discussing some easily remedied common pitfalls that result in slow solver times, the authors will consider how to identify weak formulations based on the contrast between the physical systems modeled by the MIP and that of the LP relaxation that initiates the branch and bound algorithm. Both the algebraic representation of the constraints and a more visual approach will be considered. Practitioners can use an understanding of the weakness of a formulation to strengthen it by customizing cuts tailored to the characteristics of the model at hand. The authors will illustrate this approach by considering some examples involving challenging models drawn from practical business applications.

Keywords: Mixed integer programming; Weak formulations; Strong formulations; Branch and bound; Run time; Tight formulations; Cuts (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-981-99-5491-9_4

Ordering information: This item can be ordered from
http://www.springer.com/9789819954919

DOI: 10.1007/978-981-99-5491-9_4

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().