The classical column generation is based on optimal solutions of the restricted master problems. This strategy frequently results in an unstable behaviour and may require an unnecessarily large number of iterations. To overcome this weakness, variations of the classical approach use interior points of the dual feasible set, instead of optimal solutions. In this paper, we address the primal-dual column generation technique, which relies on well-centred non-optimal solutions of the restricted master problems that are obtained by a primal-dual interior point method. Although good computational results are reported for this technique, it was only applied in a particular class of problems. Moreover, no theoretical analysis to guarantee its convergence is available. Here, we further investigate the primaldual column generation technique and present extensive computational experiments in the context of integer programming, where column generation schemes are widely employed. The results show that the primal-dual technique usually leads to substantial reductions in the number of iterations as well as less running time when compared to the classical and also analytic centre approaches.
Citation
School of Mathematics, University of Edinburgh The King's Buildings, Edinburgh, EH9 3JZ, UK Technical Report ERGO 11-001, January 24, 2011.