Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959036 | Computers & Operations Research | 2017 | 14 Pages |
Abstract
We address the problem of determining a complete set of extreme supported efficient solutions of biobjective minimum cost flow (BMCF) problems. A novel method improving the classical parametric method for this biobjective problem is proposed. The algorithm runs in O(Nn(mâ+Â nlogn)) time determining all extreme supported non-dominated points in the outcome space and one extreme supported efficient solution associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported non-dominated points in outcome space for the BMCF problem. The memory space required by the algorithm is O(nâ+Â m) when the extreme supported efficient solutions are not required to be stored in RAM. Otherwise, the algorithm requires O(Nâ+Â m) space. Extensive computational experiments comparing the performance of the proposed method and a standard parametric network simplex method are presented.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Andrea Raith, Antonio Sedeño-Noda,