New Developments in the Primal-Dual Column Generation Technique

Technical Report ERGO-11-001

J. Gondzio, P. González-Brevis, P. Munari

The optimal solutions of the restricted master problems typically leads to an unstable behaviour of the standard column generation technique and, consequently, originates an unnecessarily large number of iterations of the method. To overcome this drawback, variations of the standard approach use interior points of the dual feasible set instead of optimal solutions. In this paper, we focus on a variation known as the primal-dual column generation technique which uses a primal-dual interior point method to obtain well-centred non-optimal solutions of the restricted master problems. We show that the method converges to an optimal solution of the master problem even though non-optimal solutions are used in the course of the procedure. Also, computational experiments are presented using linear-relaxed reformulations of three classical integer programming problems: the cutting stock problem, the vehicle routing problem with time windows, and the capacitated lot sizing problem with setup times. The numerical results indicate that the appropriate use of a primal-dual interior point method within the column generation technique contributes to a reduction of the number of iterations as well as the running times, on average. Furthermore, the results show that the larger the instance, the better the relative performance of the primal-dual column generation technique.

Key words: Column Generation, Interior Point Methods, Linear Programming.

PDF (old) ERGO-11-001.pdf.
PDF (last) ERGO-11-001rev.pdf.

Written: January 24, 2011, revised March 19, 2012 and July 9, 2012.
European Journal of Operational Research 224 (2013) 41-51.
Published online: July 31, 2012. DOI 10.1016/j.ejor.2012.07.024.

Related Software:
HOPDM Higher Order Primal Dual Method.