Article ID: | iaor20164770 |
Volume: | 14 |
Issue: | 1 |
Start Page Number: | 37 |
End Page Number: | 51 |
Publication Date: | Feb 2002 |
Journal: | INFORMS Journal on Computing |
Authors: | Hoogeveen Han, van de Velde Steef, van den Akker Marjan |
Keywords: | column generation, makespan, relaxation methods |
Column generation has proved to be an effective technique for solving the linear programming relaxation ofhuge set covering or set partitioning problems, and column generation approaches have led to state‐of‐the‐art so‐called branch‐and‐price algorithms for various archetypical combinatorial optimization problems. We use a combination of column generation and Lagrangean relaxation to tackle a single‐machine common due date problem, where Lagrangean relaxation is exploited for early termination of the column generation algorithm and for speeding up the pricing algorithm. We show that the Lagrangean lower bound dominates the lower bound that can be derived from the column generation algorithm when applied to the standard linear programming formulation, but we also show how the linear programming formulation can be adapted such that the corresponding lower bound is equal to the Lagrangean lower bound. Our comprehensive computational study shows that the combined algorithm is by far superior to two existing purely column generation algorithms: it solves instances with up to 125 jobs to optimality, while a purely column generation algorithm can solve instances with up to only 60 jobs.