This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Przybylski, A. Articles by Ehrgott, M.

A Recursive Algorithm for Finding All Nondominated Extreme Points in the Outcome Set of a Multiobjective Integer Programme

LINA (Laboratoire d'Informatique de Nantes Atlantique), Unité Mixte de Recherche Centre National de la Recherche Scientifique 6241, Université de Nantes, 44322 Nantes, France
LINA (Laboratoire d'Informatique de Nantes Atlantique), Unité Mixte de Recherche Centre National de la Recherche Scientifique 6241, Université de Nantes, 44322 Nantes, France
Department of Engineering Science, University of Auckland, Auckland 1142, New Zealand
anthony.przybylski{at}univ-nantes.fr
xavier.gandibleux{at}univ-nantes.fr
m.ehrgott{at}auckland.ac.nz

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.

Key words: multiobjective integer programme; efficient solution; weight space decomposition; nondominated extreme point
History: received February 2007; revised January 2009; accepted April 2009.