Videos

The Branch-and-Cut Algorithm for Solving Mixed-Integer Optimization Problems

Presenter
August 10, 2016
Keywords:
  • Mixed-integer programming, branch-and-cut, valid inequalities, cutting planes
MSC:
  • 90C11
Abstract
In this lecture we describe the branch-and-cut algorithm, which is currently the state-of-the-art approach for solving mixed-integer optimization problems. We first describe the basic branch-and-bound framework, where efficiently solvable linear programming relaxations are used to eliminate parts of the search space. We then discuss the impact of formulation choice on such a solution procedure, and finally introduce the concept of valid inequalities (or cutting planes) as a mechanism for automatically improving a formulation. Finally, we discuss how such cuts can be incorporated within a branch-and-bound algorithm to obtain the branch-and-cut algorithm.