Column Generation with a Primal-Dual Method

Logilab Technical Report 1996.6

J. Gondzio and R. Sarkissian

A simple column generation scheme that employs an interior point method to solve underlying restricted master problems is presented. In contrast with the classical column generation approach where restricted master problems are solved exactly, the method presented in this paper consists in solving it to a predetermined optimality tolerance (loose at the beginning and appropriately tightened when the optimum is approached). An infeasible primal-dual interior point method which employs the notion of $\mu$-center to control the distance to optimality is used to solve the restricted master problem. Similarly to the analytic center cutting plane method, the present approach takes full advantage of the use of central prices. Furthermore, it offers more freedom in the choice of optimization strategy as it adaptively adjusts the required optimality tolerance in the master to the observed rate of convergence of the column generation process. The proposed method has been implemented and used to solve large scale nonlinear multicommodity network flow problems. Numerical results are given to illustrate its efficiency.

Key words: Column Generation, Restricted Master Problem, Primal-Dual Algorithm, Analytic Center.

PDF TR1996.6.pdf.
Written: June 1996.