Please use this identifier to cite or link to this item:
|Title:||A Lagrangean relaxation scheme for structured linear programs with application to multicommodity network flows|
Lagrangean heuristic methods
Linear minimum cost multicommodity network flow problem
|Source:||Larsson, T.,Liu, Z. (1997). A Lagrangean relaxation scheme for structured linear programs with application to multicommodity network flows. Optimization 40 (3) : 247-284. ScholarBank@NUS Repository.|
|Abstract:||It is well known that linear programs can generally not be solved by straightforward Lagrangean relaxation and dual subgradient optimization, the reason being that the solutions to the Lagrangean relaxed problems are, normally, infeasible in the original linear program. This property is a consequence of the linearity of the problem and it holds even in the unlikely case that an exact optimal dual solution is found. We show that an optimal solution to the linear program can be obtained by calculating the simple average of the solutions to the relaxed problems which are solved during the subgradient search scheme, provided that the steplengths in this scheme are chosen according to a modified harmonic series. This method is similar to a procedure given earlier by Shor, which utilizes a particular weighted average and holds for any divergent series steplength rule. As an application of these two averaging schemes, we construct an approximate algorithm for the minimum cost multicommodity network flow problem. The algorithm has been implemented for solving multicommodity transportation problems and shows a good performance. The computational results indicate that it may be possible to use Lagrangean relaxation and dual subgradient optimization for constructing efficient special-purpose solution methods for structured large-scale linear programs.|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Mar 10, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.