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

Wednesday, August 10, 2016 - 11:00am - 12:30pm
Lind 305
Jim Luedtke (University of Wisconsin, Madison)
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.
MSC Code: