Exact Methods For The Determination Of The Pareto Set

The purpose of this task is to develop efficient techniques to solve complex Multi-objective combinatorial optimization (MOCO) problems and to design powerful algorithms for solving “pure” MOCO problems.

Subtask 3.1 Primal-Dual methods
A first primal-dual method for the exact solution of multiobjective linear problems (MOLP) has been proposed by Ehrgott et al. in 2007. This method can be applied to MOCO problems under the assumption that the constraint matrix is totally unimodular (e.g. for network flow problems) to compute the set of supported efficient solutions. The main advantages of this method are its expected efficiency to problems with a specific structure (as in the single-objective case), its ability to deal with problems with more than two objectives, and the decomposition of the weight space obtained simultaneously during the solution process. Even though the computation of supported efficient solutions is often considered as the easy part of the exact solution of MOCO problems, it is important to do it efficiently. Indeed, this computation is required in the two phase method and a weight space decomposition has been a fundamental step in its extension to the three-objective case. Moreover, the computation of supported solutions of sub-problems is intensively used in the branch and bound algorithm.

Subtask 3.2 Multiobjective implicit enumeration schemes
One of the most promising ideas seems to introduce extensions of Branch and Bound / Branch and Cut procedures to the multiobjective case. The main questions are 1) how to construct and maintain efficiently a multidimensional bound on solutions during the search, 2) how to extend recent approaches developed in the biobjective case to higher dimensions. The definition and integration of reduction rules before or during the tree exploration could improve significantly the performances of the method. Such a rule is for instance an additional constraint on the sum of variables as introduced in 2000 by Gandibleux and Fréville. However, few reduction rules have been proposed. Here bounding the remaining space to explore using a technique based on metaheursitics is a promising way as illustrated by the “seek and cut” procedure.