Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/102665
Title: A Lagrangean relaxation scheme for structured linear programs with application to multicommodity network flows
Authors: Larsson, T.
Liu, Z. 
Keywords: Ergodic results
Lagrangean duality
Lagrangean heuristic methods
Linear minimum cost multicommodity network flow problem
Linear programming
Subgradient optimization
Issue Date: 1997
Citation: 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.
Source Title: Optimization
URI: http://scholarbank.nus.edu.sg/handle/10635/102665
ISSN: 02331934
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

33
checked on Nov 2, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.