Column generation and branch-and-price with interior point methods

Abstract

Column generation and branch-and-price methods are currently essential tools for solving many classes of integer programming and combinatorial optimization problems. This paper addresses how to improve the performance of these methodologies by using the interior point algorithm. The purpose is to summarize the main developments proposed in the thesis “Theoretical and computational issues for improving the performance of linear optimization methods” which has been awarded with the “Doctoral Prize Odelar Leite Linhares” in 2014. As the com- putational experiments indicates, the interior point method is more than an alternative to the simplex method. Indeed, it offers advantageous features which can be used to stabilize the column generation technique and improve the overall performance of the branch-and-price method.