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.