J. Gondzio, P. González-Brevis, P. Munari
Abstract
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.