A two-phase algorithm for the biobjective integer minimum cost flow problem
Author: Raith, Andrea; Ehrgott, Matthias
Publisher: Faculty of Engineering, University of Auckland, New Zealand.
Link to this item using this URL: http://hdl.handle.net/2292/2645
We present an algorithm to compute a complete set of efficient solutions for the biobjective integer minimum cost flow problem. We use the two phase method with a parametric network simplex algorithm in phase 1 to compute all supported non-dominated extreme points. In phase 2, the remaining nondominated points (non-extreme supported and non-supported) are computed using a k best flow algorithm on single-objective weighted sum problems. We implement the algorithm and report run-times on problem instances generated with a modified version of the NETGEN generator and also for some networks with grid structure.
Citation: ["Report University of Auckland School of Engineering 661, (2007)"]