《《2016 Interior point stabilization for column generation》.pdf

Operations Research Letters Operations Research Letters 35 (2007) 660–668 /locate/orl Interior point stabilization for column generation a b ,∗ c Louis-Martin Rousseau , Michel Gendreau , Dominique Feillet a Cirrelt, École Polytechnique de Montréal, Canada b Cirrelt, Université de Montréal, C.P. 6128, Succursale Centre-ville, Montréal, Canada H3C 3J7 cLaboratoire d’Informatique d’Avignon, Canada Received 3 July 2003; accepted 14 November 2006 Available online 20 December 2006 Abstract Interior point stabilization is an acceleration method for column generation algorithms. It addresses degeneracy and convergence difficulties by selecting a dual solution inside the optimal space rather than retrieving an extreme point. The method is applied to the case of the vehicle routing problem with time windows. © 2007 Elsevier B.V. All rights reserved. Keywords: Column generation; Stabilization; Vehicle routing 0. Introduction then becomes a crucial part of the column generation