Group for Research in Decision Analysis

G-98-06

Stabilized Column Generation

, , , and

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

This cahier was revised in June 1998