Title: Interior-Point versus Simplex methods for Integer Programming Branch-and-Bound
Presentation Slides


Although, interior-point methods (IPMs) are successful for linear programming, they are not widely employed in branch-and-bound (B&B) algorithms for integer programming, because of the belief that it is cumbersome to reoptimize an LP with an interior-point method after rows or columns have been added(Johnson, Nemhauser and Savelsbergh, Informs JOC, 12:1, 2000).
Most of the success of simplex methods within B&B approaches is due to the effective warm starting of the solution of child nodes based on the optimal basis at the parent node. In this talk, we argue that most of this misconception was due to the fact that IPMs were used as substitutes to simplex methods, and that more effort should be put into integrating IPMs within B&B. We show that this is possible if IPMs are applied in a column generation/cutting plane context. We provide a complete branch-and-bound framework where branching and warm starting are discussed. Numerical results are provided.