A Lagrangean heuristic for the capacitated concave minimum cost network flow problem

Larsson, Torbjörn (author): Department of Mathematics, Institute of Technology, Linköping University

Migdalas, Athanasios (author): Department of Mathematics, Institute of Technology, Linköping University

Rönnqvist, Mikael (author): Department of Mathematics, Institute of Technology, Linköping University

(creator_code:org_t)

Elsevier BV, 1994
1994
English.
In: European Journal of Operational Research. - : Elsevier BV. - 0377-2217 .- 1872-6860. ; 78:1, s. 116-129

Related links:: https://urn.kb.se/re...; show more...; https://doi.org/10.1...; show less...

Abstract Subject headings

We propose a heuristic solution technique for the capacitated concave minimum cost network flow problem based on a Lagrangean dualization of the problem. Despite its dual character the algorithm guarantees the generation of primal feasible solutions which are local optima and therefore candidates of being the global optimum. The Lagrangean dual is solved by a subgradient search procedure and provides a lower bound to the optimal value. The lower bound is, in general, stronger than the one obtained by a linear approximation of the original problem. It can be used as a judgement of the quality of the solution or in a branch and bound procedure. Computational results from randomly generated problems are presented

By the author/editor: Larsson, Torbjör ...; Migdalas, Athana ...; Rönnqvist, Mikae ...

About the subject

ENGINEERING AND TECHNOLOGY: ENGINEERING AND ...; and Mechanical Engin ...; and Production Engin ...

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.