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

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.