Article ID: | iaor20105633 |
Volume: | 22 |
Issue: | 3 |
Start Page Number: | 371 |
End Page Number: | 386 |
Publication Date: | Jun 2010 |
Journal: | INFORMS Journal on Computing |
Authors: | Gandibleux Xavier, Ehrgott Matthias, Przybylski Anthony |
Keywords: | programming: multiple criteria |
In this paper, we present two versions of an algorithm for the computation of all nondominated extreme points in the outcome set of a multiobjective integer programme. We define adjacency of these points based on weight space decomposition. Thus, our algorithms generalise the well-known dichotomic scheme to compute the set of nondominated extreme points in the outcome set of a biobjective programme. Both algorithms are illustrated with and numerically tested on instances of the assignment and knapsack problems with three objectives.