Template-Type: ReDIF-Paper 1.0
Author-Name: Huisman, D.
Author-Name-Last: Huisman
Author-Name-First: Dennis
Author-Person: phu27
Author-Name: Jans, R.F.
Author-Name-Last: Jans
Author-Name-First: Raf
Author-Name: Peeters, M.
Author-Name-Last: Peeters
Author-Name-First: Marc
Author-Name: Wagelmans, A.P.M.
Author-Name-Last: Wagelmans
Author-Name-First: Albert
Title: Combining Column Generation and Lagrangian  Relaxation
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.
Creation-Date: 2003-01-01
File-URL: https://repub.eur.nl/pub/1098/ERS%202003%20092%20LIS.pdf
File-Format: application/pdf
Series: RePEc:ems:eureri
Number: ERS-2003-092-LIS
Classification-JEL: C61, M, M11, R4
Keywords: Lagrangean relaxation, column generation, cutting stock  problem, lotsizing, vehicle and crew scheduling
Handle: RePEc:ems:eureri:1098