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

Research output: Book/ReportReportAcademic

78 Downloads (Pure)

Abstract

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.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages24
Publication statusPublished - 1998

Publication series

NameMemorandum COSOR
Volume9818
ISSN (Print)0926-4493

Fingerprint Dive into the research topics of 'Combining column generation and Lagrangean relaxation : an application to a single-machine common due date scheduling problem'. Together they form a unique fingerprint.

Cite this