Groupe d’études et de recherche en analyse des décisions

G-98-06

Stabilized Column Generation

, , et

Column generation is often used to solve large scale optimization problems, and much research has been devoted to improve the convergence of the solution process. We focus on Kelley's algorithm, which frequently exhibits slow convergence, and propose an algorithm that stabilizes and accelerates the solution process while remaining within the linear programming framework. Preliminary numerical results, obtained on air transportation and location problems, show that the stabilized algorithm can be used to improve the solution times for difficult instances and to solve larger ones.

, 12 pages

Ce cahier a été révisé en juin 1998