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.

Lagrangean relaxation, column generation, cutting stock problem, lotsizing, vehicle and crew scheduling
Optimization Techniques; Programming Models; Dynamic Analysis (jel C61), Business Administration and Business Economics; Marketing; Accounting (jel M), Production Management (jel M11), Transportation Systems (jel R4)
ERIM Report Series Research in Management
Erasmus Research Institute of Management

Huisman, D, Jans, R.F, Peeters, M, & Wagelmans, A.P.M. (2003). Combining Column Generation and Lagrangian Relaxation (No. ERS-2003-092-LIS). ERIM Report Series Research in Management. Retrieved from