Premium
Approximate solutions of capacitated fixed‐charge minimum cost network flow problems
Author(s) -
Khang Do Ba,
Fujiwara Okitsugu
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210606
Subject(s) - subgradient method , fixed charge , mathematical optimization , lagrange multiplier , upper and lower bounds , relaxation (psychology) , heuristic , linear programming relaxation , mathematics , flow network , flow (mathematics) , simple (philosophy) , minimum cost flow problem , computer science , linear programming , geometry , molecular physics , psychology , mathematical analysis , social psychology , chemistry , philosophy , epistemology
This article proposes two approximate methods to solve capacitated, single‐commodity and fixed‐charge network flow problems. First, relaxed problems obtained by the Lagrange relaxation method are shown to form a minimum spanning tree problem, yielding a lower bound to the original problem. The subgradient optimization technique can be then applied to improve this bound by updating the Lagrange multipliers. The second part of the article presents a new, simple, and efficient heuristic to find a feasible and approximate solution that is also an upper bound to the original problem.