Column generation with a primal-dual method

Jacek Gondzio and Robert 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). A primal-dual logarithmic barrier 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 successfully implemented and used to solve large scale nonlinear multicommodity network flow problems. Numerical results are given to illustrate its efficiency.

Logilab Technical Report 96.6 Section of Management Studies, University of Geneva, 102 Bd Carl Vogt, CH-1211 Geneva 4, Switzerland, June 1996