Monday, September 25
Invited Lecture: Cutting Planes and Column Generation with the Primal-Dual Interior Point Method
Time: 13:00 - 14:00
Room: L1, Building L
Chair: Jean-Baptiste Hiriart-Urruty, Université Paul Sabatier de Toulouse
Advantages of interior point methods (IPMs) applied in the context of nondifferentiable optimization arising in cutting planes/column generation applications will be discussed. Some of the many false views of the combinatorial optimization community on interior point methods applied in this context will be addressed and corrected. In particular, IPMs deliver a natural stabilization when restricted master problems are solved and guarantee fast convergence, measured with merely a few master iterations needed to localize the solution.
Several new features of the approach such as the use of primal-dual regularization and efficient IPM warm starts will be discussed. Computational experience obtained with the Primal-Dual Column Generation Method (PDCGM) software:
http://www.maths.ed.ac.uk/~gondzio/software/pdcgm.html
will be reported. This is a joint work with Pablo Gonzalez-Brevis and Pedro Munari.
Jacek Gondzio
University of Edinburgh
References:
- J. Gondzio, P. Gonzalez-Brevis and P. Munari, New developments in the primal-dual column generation technique, European Journal of Operational Research 224 (2013) 41-51.
- P. Munari and J. Gondzio, Using the primal-dual interior point algorithm within the branch-price-and-cut method, Computers and Operations Research 40 (2013) 2026-2036.
- J. Gondzio and P. Gonzalez-Brevis, A new warmstarting strategy for the primal-dual column generation method, Mathematical Programming A 152 (2015), pp. 113-146.
- J. Gondzio, P. Gonzalez-Brevis and P. Munari, Large-scale optimization with the primal-dual column generation method, Mathematical Programming Computation 8 (2016), pp. 47-82.