Convergent Lagrangian heuristics for nonlinear minimum cost network flows
(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:
https://lup.lub.lu.se/record/1039065
- author
- Marklund, Johan LU ; Larsson, Torbjörn ; Olsson, Caroline and Patriksson, Michael
- organization
- publishing date
- 2008
- 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
- 2016-04-01 11:48:05
- date last changed
- 2023-01-02 23:34:31
@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}},
keywords = {{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}},
doi = {{10.1016/j.ejor.2007.06.005}},
volume = {{189}},
year = {{2008}},
}