New developments in the primal–dual column generation technique
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.
If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Homberger, Jorg & Gehring, Hermann, 2005. "A two-phase hybrid metaheuristic for the vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 162(1), pages 220-238, April.
- Gondzio, Jacek, 1995. "HOPDM (version 2.12) -- A fast LP solver based on a primal-dual interior point method," European Journal of Operational Research, Elsevier, vol. 85(1), pages 221-225, August.
- J. L. Goffin & A. Haurie & J. P. Vial, 1992. "Decomposition and Nondifferentiable Optimization with the Projective Algorithm," Management Science, INFORMS, vol. 38(2), pages 284-302, February.
- Harvey M. Wagner & Thomson M. Whitin, 1958. "Dynamic Version of the Economic Lot Size Model," Management Science, INFORMS, vol. 5(1), pages 89-96, October.
- Gondzio, Jacek, 2012. "Interior point methods 25 years later," European Journal of Operational Research, Elsevier, vol. 218(3), pages 587-601.
- William W. Trigeiro & L. Joseph Thomas & John O. McClain, 1989. "Capacitated Lot Sizing with Setup Times," Management Science, INFORMS, vol. 35(3), pages 353-366, March.
When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:224:y:2013:i:1:p:41-51. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei)
If references are entirely missing, you can add them using this form.