Graph theory seminar - Laurent Poirrier

A Brief History of Cutting Plane Methods

Abstract:

We will cover the story of MIP cutting planes from their roots with Gomory's cutting plane algorithm to the more recent developments like multirow cuts. Along the way are topics including corner relaxations, disjunctive programming and lift-and-project. Without going too deep into the details, we will strive to give a flavor of each approach, providing a quick survey for someone not familiar with the field. In particular, we will give an overview of the computational impact various cutting plane methods had on MIP solvers throughout the years.