Introduction to Cutting-plane Theory (Part 1)
Presenter
August 11, 2016
Keywords:
- Cutting-planes, Gomory mixed integer cut, Disjunctions
MSC:
- 90C10
Abstract
A cutting-plane (cut) is a linear inequality that is valid for all feasible solutions of an integer program, but may separate points from the linear programming relaxation. We will survey some of the main ideas that have been explored to generate cutting-planes for general integer programs. Finally, we will focus on some insights that have been recently obtained on two perspectives on cutting-planes generation, namely subadditive cut-generating functions and intersection cuts based on lattice-free sets.