Abstract
Although the possibility to combine column generation and Lagrangian relaxation has been known for quite some time, it has only recently been exploited in algorithms. In this paper, we discuss ways of combining these techniques. We focus on solving the LP relaxation of the Dantzig-Wolfe master problem. In a first approach we apply Lagrangian relaxation directly to this extended formulation, i.e. no simplex method is used. In a second one, we use Lagrangian relaxation to generate new columns, that is Lagrangian relaxation is applied to the compact formulation. We will illustrate the ideas behind these algorithms with an application in lot-sizing. To show the wide applicability of these techniques, we also discuss applications in integrated vehicle and crew scheduling, plant location and cutting stock problems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barahona, F. and Anbil, R. (2000). The volume algorithm: Producing primal solutions with a subgradient method. Mathematical Programming Series A, 87:385–399.
Barahona, F. and Jensen, D. (1998). Plant location with minimum inventory. Mathematical Programming, 83:101–112.
Barnhart, C, Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., and Vance, P.H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46:316–329.
Bixby, R.E., Gregory, J.W., Lustig, I.J., Marsten, R.E., and Shanno, D.F. (1992). Very large-scale linear programming: A case study in combining interior point and simplex methods. Operations Research, 40:885–897.
Carraresi, P., Girardi, L., and Nonato, M. (1995). Network models, Lagrangean relaxation and subgradients bundle approach in crew scheduling problems. In: Computer-Aided Transit Scheduling, Proceedings of the Sixth International Workshop (J.R. Daduna, I. Branco, and J.M. P. Paixão, eds.), pp. 188–212. Springer Verlag.
Cattrysse, D.G., Salomon, M., Kuik, R., and Van Wassenhove, L.N. (1993). A dual ascent and column generation heuristic for the discrete lotsizing and scheduling problem with setup times. Management Science, 39:477–486.
Cattrysse, D.G., Salomon, M., and Van Wassenhove, L.N.(1994). A set partitioning heuristic for the generalized assignment problem. European Journal of Operational Research, 72:167–174.
Dantzig, G.B. and Wolfe, P. (1960). Decomposition principle for linear programming. Operations Research, 8:101–111.
Degraeve, Z. and Jans, R. (2003). A new Dantzig-Wolfe reformulation and Branch-and-Price algorithm for the capacitated lot sizing problem with set up times. Technical Report ERS-2003-010-LIS, ERIM, Erasmus University Rotterdam, the Netherlands.
Degraeve, Z. and Peeters, M. (2000). Solving the linear programming relaxation of cutting and packing problems: A hybrid simplex method/subgradient optimization procedure. Technical Report OR0017, Departement Toegepaste Economische Wetenschappen, K.U. Leuven, Belgium.
Degraeve, Z. and Peeters, M. (2003). Optimal integer solutions to industrial cutting-stock problems: Part 2. Benchmark results. INFORMS Journal on Computing, 15:58–81.
Desrosiers, J., Dumas, Y., Solomon, M.M., and Soumis, F. (1995). Time Constrained Routing and Scheduling. In: Network Routing (M.O. Ball, T.L. Magnanti, C.L. Monma, and G.L. Nemhauser, eds.), Handbooks in Operations Research and Management Science, Volume 8, pp. 35–139. North-Holland.
Dzielinski, B.P. and Gomory, R.E. (1965). Optimal programming of lot sizes, inventory and labour allocations. Management Science, 11:874–890.
Fischetti, M. and Toth, P. (1997). A polyhedral approach to the asymmetric traveling salesman problem. Management Science, 43:1520–1536.
Fisher, M.L. (1981). The Lagrangian relaxation method for solving integer programming problems. Management Science, 27:1–18.
Fisher, M.L.(1985). An applications oriented guide to Lagrangian relaxation. Interfaces, 15:10–21.
Freling, R. (1997). Models and techniques for integrating vehicle and crew scheduling. Ph.D. Thesis, Tinbergen Institute, Erasmus University Rotterdam.
Freling, R., Huisman, D., and Wagelmans, A.P.M. (2003). Models and algorithms for integration of vehicle and crew scheduling. Journal of Scheduling, 6:63–85.
Gaffi, A. and Nonato, M. (1999). An integrated approach to extra-urban crew and vehicle scheduling. In: Computer-Aided Transit Scheduling (N.H.M. Wilson, ed.), pp. 103–128. Springer Verlag.
Geoffrion, A.M. (1974). Lagrangean relaxation for integer programming. Mathematical Programming Study, 2:82–114.
Gilmore, P.C. and Gomory, R.E. (1961). A linear programming approach to the cutting stock problem. Operations Research, 9:849–859.
Haase, K., Desaulniers, G., and Desrosiers, J. (2001). Simultaneous vehicle and crew scheduling in urban mass transit systems. Transportation Science, 35:286–303.
Holmberg, K. and Yuan, D. (2003). A multicommodity network flow problem with side constraints on paths solved by column generation. INFORMS Journal on Computing, 15:42–57.
Huisman, D., Freling, R., and Wagelmans, A.P.M. (2003). Multiple-depot integrated vehicle and crew scheduling. Technical Report EI2003-02, Econometric Institute, Erasmus University Rotterdam, the Netherlands. Forthcoming in: Transportation Science.
IBM Corp. Optimization subroutine library: Guide and references. (1995).
Jans, R. and Degraeve, Z. (2004). An industrial extension of the discrete lot sizing and scheduling problem. HE Transactions, 36:47–58.
Kleindorfer, P.R. and Newson, E.F.P. (1975). A lower bounding structure for lot-size scheduling problems. Operations Research, 23:299–311.
Lasdon, L.S. and Terjung, R.C.(1971). An efficient algorithm for multi-item scheduling. Operations Research, 19:946–969.
Lemaréchal, C., Nemirovskii, A.S., and Nesterov, Y.E. (1995). New variants of bundle methods. Mathematical Programming, 69:111–148.
Löbel, A. (1998). Vehicle scheduling in public transit and Lagrangian pricing. Management Science, 44:1637–1649.
Magnanti, T.L., Shapiro, J.F., and Wagner, M.H. (1976). Generalized linear programming solves the dual. Management Science, 22:1195–1203.
Manne, A.S. (1958). Programming of economic lot sizes. Management Science, 4:115–135.
Martin, R.K. (1999). Large Scale Linear and Integer Optimization: A Unified Approach. Kluwer Academic Publishers.
Schrage, L. (1995). LINDO: Optimization Software for Linear Programming. Lindo Systems Inc., Chicago IL.
Sol, M. (1994). Column generation techniques for pickup and delivery problems. Ph.D Thesis, Eindhoven University of Technology.
Trigeiro, W., Thomas, L.J., and McClain, J.O. (1989). Capacitated lot sizing with set-up times. Management Science, 35:353–366.
Van den Akker, J.M., Hurkens, C.A.J., and Savelsbergh, M.W.P. (2000). Time-indexed formulations for machine scheduling problems: Column generation. INFORMS Journal on Computing, 12:111–124.
Vanderbeck, F. (1999). Computational study of a column generation algorithm for bin packing and cutting stock problems. Mathematical Programming Series A, 86:565–594.
Vanderbeck, F. and Wolsey, L.A. (1996). An exact algorithm for IP column generation. Operations Research Letters, 19:151–159.
Wolsey, L.A. (1998). Integer Programming. Wiley.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer Science+Business Media, Inc.
About this chapter
Cite this chapter
Huisman, D., Jans, R., Peeters, M., Wagelmans, A.P. (2005). Combining Column Generation and Lagrangian Relaxation. In: Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds) Column Generation. Springer, Boston, MA. https://doi.org/10.1007/0-387-25486-2_9
Download citation
DOI: https://doi.org/10.1007/0-387-25486-2_9
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-25485-2
Online ISBN: 978-0-387-25486-9
eBook Packages: Business and EconomicsBusiness and Management (R0)