liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Convergent Lagrangian heuristics for nonlinear minimum cost network flows
Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .ORCID iD: 0000-0003-2094-7376
Department of Industrial Management and Logistics, Lund University, SE-221 00 Lund, Sweden.
Department of Radio Physics, Göteborg University, SE-413 45 Gothenburg, Sweden.
Department of Mathematical Sciences, Chalmers University of Technology, SE-412 96 Gothenburg, Sweden, Department of Mathematical Sciences, Göteborg University, SE-412 96 Gothenburg, Sweden.
2008 (English)In: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 189, no 2, 324-346 p.Article in journal (Refereed) Published
Abstract [en]

We consider the separable nonlinear and strictly convex single-commodity network flow problem (SSCNFP). We develop a computational scheme for generating a primal feasible solution from any Lagrangian dual vector, this is referred to as "early primal recovery". It is motivated by the desire to obtain a primal feasible vector before convergence of a Lagrangian scheme, such a vector is not available from a Lagrangian dual vector unless it is optimal. The scheme is constructed such that if we apply it from a sequence of Lagrangian dual vectors that converge to an optimal one, then the resulting primal (feasible) vectors converge to the unique optimal primal flow vector. It is therefore also a convergent Lagrangian heuristic, akin to those primarily devised within the field of combinatorial optimization but with the contrasting and striking advantage that it is guaranteed to yield a primal optimal solution in the limit. Thereby we also gain access to a new stopping criterion for any Lagrangian dual algorithm for the problem, which is of interest in particular if the SSCNFP arises as a subproblem in a more complex model. We construct instances of convergent Lagrangian heuristics that are based on graph searches within the residual graph, and therefore are efficiently implementable, in particular we consider two shortest path based heuristics that are based on the optimality conditions of the original problem. Numerical experiments report on the relative efficiency and accuracy of the various schemes. © 2007 Elsevier B.V. All rights reserved.

Place, publisher, year, edition, pages
2008. Vol. 189, no 2, 324-346 p.
Keyword [en]
Convex programming, Large-scale programming, Network flows
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-50353DOI: 10.1016/j.ejor.2007.06.005OAI: oai:DiVA.org:liu-50353DiVA: diva2:271249
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2017-12-12

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Larsson, Torbjörn

Search in DiVA

By author/editor
Larsson, Torbjörn
By organisation
The Institute of TechnologyOptimization
In the same journal
European Journal of Operational Research
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 343 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf