Advanced

Convergent Lagrangian heuristics for nonlinear minimum cost network flows

Marklund, Johan LU ; Larsson, Torbjörn; Olsson, Caroline and Patriksson, Michael (2008) In European Journal of Operational Research 189(2). p.324-346
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
network flows, convex programming, large-scale programming
in
European Journal of Operational Research
volume
189
issue
2
pages
324 - 346
publisher
Elsevier
external identifiers
  • wos:000254814800003
  • scopus:39649100423
ISSN
0377-2217
DOI
10.1016/j.ejor.2007.06.005
language
English
LU publication?
yes
id
791ea754-558d-48cf-a388-a352ecbe17ec (old id 1039065)
date added to LUP
2008-02-27 08:39:46
date last changed
2017-01-01 04:33:23
@article{791ea754-558d-48cf-a388-a352ecbe17ec,
  abstract     = {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.},
  author       = {Marklund, Johan and Larsson, Torbjörn and Olsson, Caroline and Patriksson, Michael},
  issn         = {0377-2217},
  keyword      = {network flows,convex programming,large-scale programming},
  language     = {eng},
  number       = {2},
  pages        = {324--346},
  publisher    = {Elsevier},
  series       = {European Journal of Operational Research},
  title        = {Convergent Lagrangian heuristics for nonlinear minimum cost network flows},
  url          = {http://dx.doi.org/10.1016/j.ejor.2007.06.005},
  volume       = {189},
  year         = {2008},
}