Finding extreme supported solutions of biobjective network flow problems: An enhanced parametric programming approach. (June 2017)

• Record Type: Journal Article
• Authors: Raith, Andrea; Sedeño-Noda, Antonio
• Is Part Of: Computers & operations research. Volume 82(2017)
• Page Start: 153
• Page End: 166
• Publication Date: 2017-06
• Subjects: Biobjective minimum cost flow problem -- Extreme supported efficient solutions -- Network flow algorithm -- Parametric simplex method; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.01.004
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Problem: find complete set of extreme supported efficient solutions of biobjective min cost flow. We show that only a subset of arcs needs to be considered in every parametric simplex iteration. This leads to the proposed improvement of the classical parametric network simplex. We analyse worst-case time and space complexity. Extensive computational experiments compare performance of proposed and standard approaches. 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 + n log n )) 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.