COIN-OR::LEMON - Graph Library

Changes between Version 4 and Version 5 of AlkMod2017


Ignore:
Timestamp:
10/24/17 23:50:31 (2 years ago)
Author:
Alpar Juttner
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • AlkMod2017

    v4 v5  
    2222== December 6. ==
    2323
     24[attachment:515123.pdf​ Marjan van den Akker, Han Hoogeveen, Steef van de Velde. ''COMBINING COLUMN GENERATION AND LAGRANGEAN RELAXATION ---
     25AN APPLICATION TO A SINGLE-MACHINE COMMON DUE DATE SCHEDULING PROBLEM]
     26
     27Column 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,
     28if 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.
     29
     30Our 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.
     31
    2432== December 13. ==