Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1238.90096
Den Akker, Marjan Van; Hoogeveen, Han; De Velde, Steefvan
Combining column generation and Lagrangean relaxation to solve a single-machine common due date problem. (English)
[J] INFORMS J. Comput. 14, No. 1, 37-51 (2002). ISSN 1091-9856; ISSN 1526-5528/e

Summary: 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.

MSC 2000:: *90C08 Special problems of linear programming
90B35 Scheduling theory

Keywords: column generation Lagrangean relaxation set covering linear programming earliness- tardiness scheduling common due date

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]