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
Contact: [email protected]