Combining column generation and Lagrangean relaxation : an application to a single-machine common due date scheduling problem

J.M. Akker, van den, J.A. Hoogeveen, S.L. Velde, van de

Onderzoeksoutput: Boek/rapportRapportAcademic

86 Downloads (Pure)

Samenvatting

Column generation has proved to be an effective technique for solving the linear programming relaxation of huge 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. Usually, if Lagrangean relaxation is embedded at all in a column generation approach, then the Lagrangean bound serves only as a tool to fathom nodes of the branch-and-price tree. We show that the Lagrangean bound can be exploited in more sophisticated and effective ways for two purposes: to speed up convergence of the column generation algorithm and to speed up the pricing algorithm. Our vehicle to demonstrate the effectiveness of teaming up column generation with Lagrangean relaxation is an archetypical single-machine common due date scheduling problem. 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 purely column generation algorithm can solve instances with up to only 60 jobs.
Originele taal-2Engels
Plaats van productieEindhoven
UitgeverijTechnische Universiteit Eindhoven
Aantal pagina's24
StatusGepubliceerd - 1998

Publicatie series

NaamMemorandum COSOR
Volume9818
ISSN van geprinte versie0926-4493

Vingerafdruk

Duik in de onderzoeksthema's van 'Combining column generation and Lagrangean relaxation : an application to a single-machine common due date scheduling problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit