Combining Column Generation and Lagrangian Relaxation

This file is part of IDEAS, which uses RePEc data

Combining Column Generation and Lagrangian Relaxation

Author Info

Huisman, D.
Jans, R.F.
Peeters, M.
Wagelmans, A.P.M. (Erasmus Research Institute of Management (ERIM), RSM Erasmus University)

Additional information is available for the following registered author(s):

Dennis Huisman

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 for-mulation. 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.

Download Info
To download:

If you experience problems downloading a file, check if you have the proper application to view it first. Information about this may be contained in the File-Format links below. 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.

Publisher Info
Paper provided by Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam. in its series Research Paper with number ERS-2003-092-LIS Revision_Date: 2009-07-29.

Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Length:
Date of creation: 01 Jan 2003
Date of revision:
Handle: RePEc:dgr:eureri:30001228

Contact details of provider:
Web page: http://www.erim.eur.nl/

For technical questions regarding this item, or to correct its listing, contact: (ERIM Series Handler at the ERIM Office).

Other versions of this item:

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.:

D. Huisman & R. Freling & A.P.M. Wagelmans, 2003. "Multiple-depot integrated vehicle and crew scheduling," Econometric Institute Report 302, Erasmus University Rotterdam, Econometric Institute. [Downloadable!]
Other versions:
- Huisman, D. & Freling, R. & Wagelmans, A.P.M., 2003. "Multiple-Depot Integrated Vehicle and Crew Scheduling," Econometric Institute Report EI 2003-02 Revision_Date:, Erasmus University Rotterdam, Econometric Institute. [Downloadable!]
Freling, R. & Huisman, D. & Wagelmans, A.P.M., 2000. "Models and algorithms for Integration of Vehicle and Crew Scheduling," Research Paper ERS-2000-14-LIS Revision_, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus Uni. [Downloadable!]
Other versions:
- R. Freling & D. Huisman & A.P.M. Wagelmans, 2000. "Models and algorithms for integration of vehicle and crew scheduling," Econometric Institute Report 189, Erasmus University Rotterdam, Econometric Institute. [Downloadable!]
Cattrysse, Dirk. G. & Salomon, Marc & Van Wassenhove, Luk N., 1994. "A set partitioning heuristic for the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 72(1), pages 167-174, January. [Downloadable!] (restricted)

Full references

Cited by:
(explanations, 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.)

Eliashberg, J. & Hegie, Q. & Ho, J. & Huisman, D. & Miller, S.J. & Swami, S. & Weinberg, C.B. & Wierenga, B., 2007. "Demand-Driven Scheduling of Movies in a Multiplex," Research Paper ERS-2007-033-MKT Revision, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus Uni. [Downloadable!]
Other versions:
- Eliashberg, J. & Hegie, Q. & Ho, J. & Huisman, D. & Miller, S.J. & Swami, S. & Weinberg, C.B. & Wierenga, B., 2007. "Demand-driven scheduling of movies in a multiplex," Econometric Institute Report EI 2007-17 Revision_Date:, Erasmus University Rotterdam, Econometric Institute. [Downloadable!]

Statistics

Access and download statistics

Did you know? The RePEc project started in 1997. Its precursor, NetEc, dates back to 1993.

This page was last updated on 2010-1-6.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.