A two-phase algorithm for the biobjective integer minimum cost flow problem

Author: Raith, Andrea; Ehrgott, Matthias

Date: 2007

Publisher: Faculty of Engineering, University of Auckland, New Zealand.

Type: Report

Link to this item using this URL: http://hdl.handle.net/2292/2645

The University of Auckland Library

Abstract

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)"]

Copyright: https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm