Abstract
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.