Convergent Lagrangian heuristics for nonlinear minimum cost network flows
(2008) In European Journal of Operational Research 189(2). p.324346 Abstract
 We consider the separable nonlinear and strictly convex singlecommodity 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 singlecommodity 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:
http://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, largescale programming
 in
 European Journal of Operational Research
 volume
 189
 issue
 2
 pages
 324  346
 publisher
 Elsevier
 external identifiers

 wos:000254814800003
 scopus:39649100423
 ISSN
 03772217
 DOI
 10.1016/j.ejor.2007.06.005
 language
 English
 LU publication?
 yes
 id
 791ea754558d48cfa388a352ecbe17ec (old id 1039065)
 date added to LUP
 20080227 08:39:46
 date last changed
 20170101 04:33:23
@article{791ea754558d48cfa388a352ecbe17ec, abstract = {We consider the separable nonlinear and strictly convex singlecommodity 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 = {03772217}, keyword = {network flows,convex programming,largescale programming}, language = {eng}, number = {2}, pages = {324346}, 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}, }