New Developments in the Primal-Dual Column Generation Technique

Abstract

The optimal solutions of the restricted master problems typically leads to an unstable behavior 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-centered 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.