Marek, Renaud Satya

Nathanaël, Anaëlle, Fabien, Lyes, Lydia Ian Florian

Maude, Khalil, Linda, Hiba, Saeed, Mahdi, Yassine Thomas

Keywords: multi-objective optimization, partial preference relation, multi-objective combinatorial optimization problems

Cette thèse n'aurait pu aboutir sans l'aide et le soutien de plusieurs personnes auxquelles je voudrais exprimer ma gratitude dans ces quelques lignes.

Tout d'abord, je tiens à remercier Daniel Vanderpooten, mon directeur de thèse, pour le chemin parcouru pendant ces trois années. J'ai apprécié les nombreux (et parfois très longs!) échanges que l'on a pu avoir durant cette période, et la considération qu'il m'a accordée pendant ces instants. Son encadrement et son expertise m'ont aidé à mener à bien les différents objectifs fixés au départ de cette thèse, mais aussi à évoluer sur le plan personnel.

Je remercie également Jean-Michel Vanpeperstraete, mon encadrant à DCNS, pour m'avoir fait profiter de son savoir sur d'innombrables sujets mais aussi de son impressionnante bibliothèque scientifique. Ses idées, son expertise et sa polyvalence ont largement contribué à ce travail.

Je remercie de nouveau Daniel et Jean-Michel de m'avoir conjointement proposé ce sujet de thèse qui m'a passionné. Je garderai d'excellents souvenirs de notre collaboration.

De même, je remercie Kathrin Klamroth et Olivier Spanjaard, qui ont accepté d'être rapporteurs et qui ont tous deux assisté à certaines de mes présentations. Kathrin a également participé à la pré-soutenance, pour cela je voudrais lui dire "Vielen Dank"! Je remercie également Hassene Aissi et André Rossi pour leur participation à mon jury en tant qu'examinateurs et en particulier Hassene, qui a participé à la relecture de cette thèse et à la pré-soutenance.

J'adresse ma reconnaissance aux chefs de service que j'ai pu côtoyer à DCNS, Christian Audoly et Alain Carof, pour m'avoir intégré à leur équipe. Je remercie mes collègues que j'ai fréquentés quotidiennement dont, notamment, Olivier, qui m'a fait découvrir les environs balnéolais à travers la course à pied, et Quentin, avec qui j'ai partagé le statut de doctorant et à qui je souhaite une dernière année fructueuse. Nos discussions techniques et plus informelles sur nos centres d'intérêts communs ont été extrêmement enrichissantes. Je pense également à Chauk-Mean avec qui j'ai partagé deux grandes activités que sont la course et la guitare. Cela a été des instants rendus sympathiques grâce à son inébranlable bonne humeur. Je n'oublie pas Adrien, Alexandre, Catherine, Dann, Pauline et évidemment Jean-Michel avec qui nous avons eu de nombreuses et plaisantes conversations. Enfin, j'adresse ma gratitude aux équipes administratives et techniques du site DCNS Bagneux, dont notamment Carole, pour les excellentes conditions de travail dont j'ai pu bénéficier.

Les doctorants du Lamsade m'ont accueilli dans leurs bureaux, où j'ai pu passer de plaisantes journées de travail grâce à leur bonne humeur. Pour cela, je remercie les anciens et actuels doctorants avec qui j'ai été amené à passer ces moments :

CONTENTS

Introduction

In many real-world optimization problems, possible outcomes are not evaluated on a single value and decisions are made based on several conflicting criteria. For example, determining the best path between two locations can be based on objectives such as the travel time, the travel cost and the carbon footprint. In this case, the first obvious and interesting paths for the decision maker (DM) would be the optimal solution on each objective taken individually, i.e. the quickest path, the cheapest path or the path with the lowest carbon footprint respectively. Optimizing a single objective usually leads to compute one optimal solution. The DM could also be interested in having a path that is a compromise of all three objectives. The interesting solutions in a multi-objective context have been characterized by the italian economist Vilfredo Pareto. A Pareto-optimal alternative cannot be improved on a criterion without decaying on another. Since the criteria are generally conflicting, there exists no solution that is optimal for all criteria. Instead of a single optimal solution, Pareto-optimality yields a set of "good" solutions, called Pareto-optimal set. In our example, when determining the potentially interesting solutions for the DM, a path that is longer, costs more and has a larger carbon footprint than another path will not be Pareto-optimal, and thus not interesting for the DM. Decision making with multiple criteria has been evolving as an active field of research with two main branches: Multiple Criteria Decision Aid (MCDA) and Multi-Objective Optimization (MOO).

MCDA guides the DM towards alternatives he or she prefers. Pareto-optimality is common to all logical DMs, but when it comes to select an alternative each DM has varying preferences. MCDA provides tools to model preferences based on information given by the DM and proposes the most valuable outcomes in light of the provided preference information. These processes are primarily used on an explicit list of outcomes and emphasize the quality of the proposed solutions. Some of them can be classified as outranking methods [START_REF] Roy | The european school of mcda: Emergence, basic features and current works[END_REF], whose main feature is to compare all feasible alternatives by pair building up some binary relations, and then to exploit them in order to obtain a final decision. The most famous outranking methods are ELECTRE [START_REF] Roy | The outranking approach and the foundations of electre methods[END_REF] and PROMETHEE [START_REF] Brans | Note-a preference ranking organisation method[END_REF]. Other processes belong to the multiattribute utility theory, which establish utility functions representing the DM's preference. The methodological framework for the multiattribute utility theory is presented in [START_REF] Keeney | Decisions with multiple objectives: preferences and value trade-offs[END_REF]. Some decision support systems (see, e.g., MACBETH (Bana e Costa and Vansnick, 1994)) determine the utility function through interactive procedures with the DM. However there are several drawbacks to these approaches. They do not easily handle a large number of alternatives and some methods ask very specific preference information to determine parameter values for the methods.

In contrast with MCDA, MOO focuses on computing the Pareto-optimal set of a multiobjective problem defined by constraints. This branch addresses the computational issues related to the optimization and focuses more particularly on the improvement of the compu-7 CONTENTS tation time of the Pareto-optimal set. MCDA focuses on preference modeling and is used with a limited number of alternatives, while MOO is constrained by the computation time and the size of the Pareto-optimal set with large instances.

Some optimization problems are characterized by a large number of implicitly defined solutions, a large number of objectives and a limited computation time. In this context, the DM is interested in Pareto-optimal solutions, which cannot be improved simultaneously in all criteria, and solving such problems can be performed by two main approaches in MOO:

1. Compute the set of Pareto-optimal solutions; 2. Choose a priori an aggregation model, elicit preference information and determine an optimal solution according to this model.

The first approach exhibits the potentially interesting trade-offs. The main difficulty is related to the large size of the Pareto-optimal set. This often results in prohibitive computation times particularly for exact algorithms. Moreover, most of the solutions presented to the DM are actually irrelevant with respect to his/her preferences.

The second approach consists in using a preference model, which aggregates the criteria using a scalarizing function (weighted sum [START_REF] Gass | The computational algorithm for the parametric function[END_REF][START_REF] Zadeh | Optimality and non-scalar-valued performance criteria[END_REF][START_REF] Geoffrion | Proper efficiency and the theory of vector maximization[END_REF], achievement function [START_REF] Wierzbicki | On the completeness and constructiveness of parametric characterizations to vector optimization problems[END_REF], ordered weighted average [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF], Choquet integral [START_REF] Grabisch | The application of fuzzy integrals in multicriteria decision making[END_REF], etc. This function requires specific parameter values reflecting the DM's preferences. A major difficulty of this approach is the elicitation of precise preference parameters. These parameters are highly dependent on the elicitation methods, which may lead to substantially different results. Interactive approaches, which favor an exploration of the solutions by iteratively optimizing a scalarizing function with evolving preference parameters, reduce these difficulties [START_REF] Gardiner | Interactive multiple criteria procedures: Some reflections[END_REF]. At each iteration the procedure presents several alternatives to the DM. The DM is asked to answer several questions concerning these alternatives. After this dialogue phase with the DM, the algorithm goes back to a calculation phase in order to make new proposals. The process stops when a stopping criterion is reached such as , e.g., the DM wants to stop, the maximum number of iterations is reached, etc. There exists several interactive procedures such as Geoffrion-Dyer-Feinberg or GDF method [START_REF] Geoffrion | An interactive approach for multicriterion optimization, with an application to the operation of an academic department[END_REF], the interactive surrogate worth trade-off method [START_REF] Chankong | The interactive surrogate worth trade-off (iswt) method for multiobjective decision-making[END_REF], the methods by [START_REF] Zionts | An interactive multiple objective linear programming method for a class of underlying nonlinear utility functions[END_REF] for linear problems. The drawback of the interactive approach is that it requires the involvement of the DM during all iterations.

In order to address the issues of these approaches, a third approach newly arised merging MCDA and MOO. In MOO, the Pareto-Optimal set contains solutions that are actually irrelevant with respect to the DM's preferences. Therefore preference integration in multi-objective optimization has been more and more investigated to construct models of partial preference before the optimization step, also called a priori integration. A partial preference model enriches the Pareto dominance relation and reduces incomparability between solutions. Some approaches use the work on domination structure in multi-objective optimization of [START_REF] Yu | Cone convexity, cone extreme points and nondominated solutions in decision problems with multiobjectives[END_REF] and [START_REF] Sawaragi | Theory of Multiobjective Optimization[END_REF] to determine these partial preference models. Among these, the cone-based approach has been widely studied. Cones are constructed with preference information of the DM (see, e.g., [START_REF] Wiecek | Advances in cone-based preference modeling for decision making with multiple criteria[END_REF] for a state of the art). However these approaches also need precise parameter values.

Context of the thesis

This thesis was partly supported by the CIFRE process, initiated by the French Ministry of Higher Education and Research and run by ANRT. The CIFRE process brings together academic research laboratories and companies, in our case DCNS. DCNS is an international high-tech company and one of the few global leaders in defence naval systems whose skills cover the whole of the production chain for complex programmes. The group designs, produces and supports submarines and surface ships. The group also provides services for naval shipyard and bases. In addition, the group offers a wide range of marine renewable energy solutions. DCNS Research is the principal power behind the group's research and technological excellence. Some optimization problems studied by DCNS Research involve a large number of objectives and feasible solutions, like, e.g., the data association problem [START_REF] Hugot | A bi-criteria approach for the data association problem[END_REF] or the sensor management problem [START_REF] Xiong | Multi-sensor management for information fusion: issues and approaches[END_REF]Svensson, 2002, Hero and[START_REF] Hero | Sensor management: Past, present and future[END_REF]. The data association problem consists in associating pieces of information emanating from different sources in order to obtain a better description of the situation under supervision. [START_REF] Hugot | A bi-criteria approach for the data association problem[END_REF] showed that optimizing two objectives instead of one objective improved the accuracy of the proposed solutions. The sensor management problem consists in scheduling and allocating sensing assets to various tasks such that the greatest possible amount of information about the state of the surrounding world is obtained. Several objectives can be defined to represent the information gain to be optimized. The increased complexity of multi-sensor systems motivated the need of helping an operator with automatic and semi-automatic management of sensor resources. These problems illustrate the motivation behind this thesis, which is handling combinatorial problems with several objectives in a limited computation time, while integrating the DM's preferences. DCNS did not define a specific application but was more interested in a prospective study that could be applied to multiple problems. This gave the thesis a high degree of freedom to explore generic innovative approaches in order to reduce the computation time and focus on relevant solutions for the DM.

Scope and goal of the thesis

In discrete MOO, some problems that must be solved in real-time cannot be adressed by an interactive procedure, due to the impossibility of the DM to take part in the optimization process or due to a limited computation time. Therefore, similarly to [START_REF] Spanjaard | Exploitation de préférences non-classiques dans les problèmes combinatoires: modèles et algorithmes pour les graphes[END_REF] and [START_REF] Perny | A preference-based approach to spanning trees and shortest paths problems[END_REF], we study the application of preference relation in MOO. We focus on providing user-oriented frameworks to elicit partial preference information, in order to build preference relations that can be used a priori in MOO with competitive performances. We especially emphasize the application to Multi-Objective Combinatorial Optimization (MOCO) problems since these problems are characterized by a large number of feasible solutions and a large computation time. However, contrary to [START_REF] Spanjaard | Exploitation de préférences non-classiques dans les problèmes combinatoires: modèles et algorithmes pour les graphes[END_REF] and [START_REF] Perny | A preference-based approach to spanning trees and shortest paths problems[END_REF], we do not focus on graph problems and propose other preference relations.

In Chapter 2, we study an original preference relation based on thresholds. This preference relation is based on translated Pareto cones and offers an alternative framework to define tradeoffs. Furthermore, this relation is a union of preference relations. So far, a union of preference relations has never been applied to discrete multi-objective optimization. We adapt a discrete MOO algorithm to compute the set of preferred points and provide numerical results on MOCO problems. This partial preference relation can easily handle heterogeneous objective scales but involves exact parameter values. In the following chapters, we focus on partial preference CONTENTS models requiring less specific preference information from the DM, but that are relevant when the objectives are expressed on the same scale.

In Chapter 3, we study a preference relation based on the weighted sum, whose weights are only partially specified. We present some general properties, and show the link between this preference relation and polyhedral cones. We provide a specific two-stage procedure to improve the computation time on MOCO problems. We show results on several preference elicitation frameworks and their corresponding weight set. The numerical experiments show the applicability of our approach and the relevance of the proposed two-stage procedure.

In Chapter 4, we study a preference relation based on the ordered weighted average operator, whose weights are only partially specified. This preference relation has already been studied but never applied to multi-objective optimization. After presenting some properties, we show the link with the preference relation of Chapter 3. The numerical experiments on MOCO problems also show the applicability of our approach.

We conclude with a summary of the results of this thesis and propose perspectives for future research directions concerning a priori integration of preference information in MOO.

Chapter 1

Notations and preliminary results

Chapter abstract

This chapter introduces the notations and preliminary results used in this thesis. First, we present basic multi-objective optimization concepts, such as dominance and supported/nonsupported points. We then focus on discrete multi-objective optimization and present an algorithm based on the so-called search region and on optimizing several budget constrained programs. We also introduce two types of multi-objective combinatorial optimization problems: multi-objective knapsack problem and multi-objective assignment problem. Finally, we provide well known results on convex sets, including cones, polyhedra and double description of polyhedral cones.

Multi-objective optimization

We introduce in this section the basic concepts and notations related to multi-objective optimization (MOO).

Basic concepts and notations

Consider a multi-objective optimization problem with p ≥ 2 objectives where X ⊆ R n denotes the set of feasible solutions. Each solution x in X is represented in the objective space R p by its corresponding vector f (x) = (f 1 (x), f 2 (x), ..., f p (x)). We assume in the following that each objective is to be minimized, and we formulate our problem as follows.

min f (x) = (f 1 (x), f 2 (x), ..., f p (x)) s.t. x ∈ X (1.1)
Let Y = f (X) denote the set of all feasible points in the objective space.

Y = {y ∈ R p : y = f (x), x ∈ X} (1.2)
Most of the following definitions can be found in textbooks like, e.g., [START_REF] Ehrgott | Multicriteria optimization[END_REF].

Dominance relations

Definition 1.1 (Pareto dominances). Given two feasible solutions x and x ′ , and their corresponding feasible points y = f (x) and y ′ = f (x ′ ), we consider the following dominance relations:

y ≦ y ′ (y weakly (Pareto) dominates y ′ ) ⇔ y i ≤ y ′ i for all i = 1, ..., p y ≤ y ′ (y (Pareto) dominates y ′ ) ⇔ y ≦ y ′ and y = y ′ y < y ′ (y strictly (Pareto) dominates y ′ ) ⇔ y i < y ′ i for all i = 1, ..., p and y = y ′ Definition 1.2 (Efficient solution, Nondominated point). A solution x ∈ X, with its corresponding point y ∈ Y , is called Pareto optimal or efficient, if there does not exist a feasible solution x ′ ∈ X, with its corresponding point y ′ ∈ Y , such that y ′ ≤ y. The corresponding point y in the objective space is called nondominated.

Definition 1.3 (Weakly efficient solution, Weakly nondominated point). A solution x ∈ X, with its corresponding point y ∈ Y , is called weakly efficient, if there does not exist a feasible solution x ′ ∈ X, with its corresponding point y ′ ∈ Y , such that y ′ < y. The corresponding point y in the objective space is called weakly nondominated.

We illustrate the concept of dominance and nondominance in the biobjective case in Figure 1.1.

We denote the set of efficient solutions, also called efficient set, by X E .

X E = {x ∈ X : there exists no x ′ ∈ X such that f (x ′ ) ≤ f (x)} (1.3)

In this thesis, we mainly work with the image of X E in the objective space. The corresponding set of points in the objective space is called the nondominated set of Y and is denoted by N (Y ).

N (Y ) = {y ∈ Y : there exists no y ′ ∈ Y such that y ′ ≤ y} (1.4)

CHAPTER 1. NOTATIONS AND PRELIMINARY RESULTS

f 1 f 2 • • • • y 1 (4, 6)
y 2 (7, 4) y 3 (6, 8) Figure 1.1: y 1 dominates y 3 , y 4 . In particular, y 1 strictly dominates y 3 but not y 4 . y 1 , y 2 are nondominated points, while y 1 , y 2 , y 4 are weakly nondominated points.

In this work, solving probem (1.1) is understood as computing N (Y ) and providing one efficient solution for each nondominated point.

Ideal and nadir point

We introduce the definitions in a context of minimization of the ideal and nadir point of a set Y, denoted by y I and y N respectively. The positive orthant will be denoted by R p ≥ and is defined as follows: R p ≥ = {d ∈ R p : d ≥ 0} Observe that the null vector 0 is not included in the positive orthant.

Weighted sum scalarization

The most widely known scalarization method in MOO is the weighted sum and has been first studied in MOO by [START_REF] Gass | The computational algorithm for the parametric function[END_REF], [START_REF] Zadeh | Optimality and non-scalar-valued performance criteria[END_REF] or [START_REF] Geoffrion | Proper efficiency and the theory of vector maximization[END_REF]. We denote the weighted sum of a point y in Y using a weight w in R p ≥ by the scalar product wy = p i=1 w i y i .

Finding the optimal point for a weighted sum is thus formulated as follows: Weight w i is supposed to reflect the relative importance of objective f i , i = 1, ..., p. Consequently the weighted sum is meaningful when the objectives are expressed on the same scale. We make this assumption in the following. Otherwise, the objectives should first be rescaled conveniently. Note that the scalarized problem (1.5) does not modify the constraints defining the set of feasible solutions X and thus the set of feasible points Y . The weight vector belongs to the positive orthant R ≥ . If we have w i = 0 for at least one i = 1, ..., p, then the optimal point of (1.5) is only weakly nondominated. If all weights w i , i = 1, ..., p, are strictly positive, then the optimal point of (1.5) is nondominated.

Supported and nonsupported points

There exist two types of nondominated points.

Definition 1.5 (Supported and nonsupported points [START_REF] Ehrgott | Multicriteria optimization[END_REF]).

-Supported nondominated points are optimal points of problem (1.5), where w i > 0, i = 1, ..., p. These points are located on the frontier of the convex hull of Y .

-Nonsupported nondominated points are nondominated points that are not supported.

We illustrate these two types of points in Figure 1.3.

Ordered Weighted Average

The ordered weighted average (OWA) operator, introduced by [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF], is a parametrized scalarizing function, whose parameters are weights corresponding to the lowest objective, the second lowest objective, etc. Due to the reordering step needed to apply this operator, OWA is nonlinear. It provides a class of parametrized operators that includes the min, max, median and average operator. In a minimization context, we define the OWA of a point y in Y using a weight w in R p ≥ as the weighted sum of the sorted point y, whose components are ordered by non-decreasing order, using the weight w.

OW A w (y) = The following program yields the optimal point for the OW A with weight w.

min y∈Y OW A w (y) (1.6)
Weight w i is supposed to reflect the relative importance of the i th lowest objective, i = 1, ..., p. Consequently, similarly to the weighted sum, OWA is meaningful when the objectives are expressed on the same scale. We make this assumption in the following. Otherwise, the objectives should first be rescaled conveniently.

The concept of orness [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF] establishes how "or-like" an operator is. The result of an "or" operator is low if at least one value is low, while on the opposite the result of an "and" operator is low if all values are low. The pure "or" and "and" operator are the minimum and the maximum, respectively. The orness measure, also called attitudinal character, and andness measure are defined hereafter.

orness(w)

=

1 p-1 p i=1 (p -i)w i andness(w) = 1 -orness(w) (1.7)
The orness and andness measures take values in the interval [0, 1]. We give examples of well-known aggregation operators being specific cases of the OWA:

• The minimum operator is obtained with w min = (1, ..., 0, 0). The orness measure is orness(w min ) = 1. The result of OW A w min (y) is low if one value of y is low.

• The average operator is obtained with w avg = ( 1 p , ..., 1 p ). The orness measure is orness(w avg ) = 0.5.

• The maximum operator is obtained with w max = (0, 0, ..., 1). The orness measure is orness(w max ) = 0. The result of OW A w max (y) is low if all values of y are low.

OWA operators with orness greater than or equal to 0.5 are considered or-like, whereas OWA operators with orness smaller than or equal to 0.5 are considered and-like.

Preference relation

Typically partial information on the DM's preferences can be represented by a binary preference relation R, such that y R-dominates y ′ if y ′ Ry. We refer to N (Y, R)

as the R-nondominated set of Y . N (Y, R) = {y ∈ Y : there exists no y ′ ∈ Y such that y ′ Ry}
More generally, assuming that N (Y, R) is not empty, we extend the definition of the ideal and nadir points with respect to a relation R.

Definition 1.6. The ideal and nadir point according to a preference relation R, denoted by y I (R) and y N (R) respectively, are defined as follows:

y I i (R) = min y∈N (Y,R) y i ,i = 1, ..., p y N i (R) = max y∈N (Y,R) y i ,i = 1, ..., p

Discrete Multi-objective optimization

Generic algorithm

In discrete MOO, most solution approaches solving problem (1.1) iteratively generate a pool of candidate solutions. This set is updated if a new candidate solution is computed. The candidate solution is either discarded or inserted. In the latter case, several solutions already generated may be dominated by this new solution and removed from the pool. Furthermore, the images of solutions in the pool can guide the enumeration in the objective space. The generated points indicate where remaining nondominated points may lie. The part of the objective space that may still contain nondominated points is called the search region [START_REF] Klamroth | On the representation of the search region in multi-objective optimization[END_REF]. The main steps for the generic algorithm are summarized in Algorithm 1 hereafter.

Search region and search zones

Each time a point y is generated, most of the recent generic discrete MOO algorithms (see, e.g., [START_REF] Sylva | Enumerating the set of non-dominated vectors in multiple objective integer linear programming[END_REF], [START_REF] Kirlik | A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems[END_REF], [START_REF] Tamby | Approches génériques pour la programmation linéaire en nombres entiers multi-objectif[END_REF]) include a procedure which takes y as an input and removes from the search region the part dominated by y, according to

CHAPTER 1. NOTATIONS AND PRELIMINARY RESULTS

the Pareto dominance. The set of generated points is denoted by N and its associated search region by S(N ).

S(N ) = {y ∈ R p : there is no y ′ in N such that y ′ ≦ y}
Moreover, given a point y in Y , we denote by D(y) the part of the objective space dominated by y.

D(y) = {y ′ ∈ R p : y ≦ y ′ }
Thus, updating the search region S(N ) with a point y can be formulated as follows:

S(N ∪ {y}) = S(N )\D(y)
The search region S(N ) can be decomposed as a list of search zones [START_REF] Klamroth | On the representation of the search region in multi-objective optimization[END_REF]. Each search zone is induced by a local upper bound u in R p and is defined as follows.

{y ∈ R p : y i < u i , i = 1, ..., p}
The recent discrete MOO algorithms mentioned above maintain, more or less explicitly, a list of search zones that represents the search region. Generating a nondominated point is done by choosing a search zone in the list and generating a nondominated point in this search zone if it exists. We illustrate Algorithm 1 and the updating step of the search region hereafter.

Example 1.1. In Figure 1.4, the search region is initialized with a search zone induced by u 0 , defined by an upper bound on each objective. The search zone corresponding to u 0 is explored. The algorithm generates y 1 and removes from the objective space the part dominated by y 1 (Figure 1.5a). This creates two search zones induced by two local upper bounds u 1 , u 2 . After exploring the search zone corresponding to u 1 , we observe that it is empty and this search zone is thus discarded from the list of search zones (Figure 1.5b). The search zone corresponding to u 2 is chosen for the next exploration.

f 1 f 2 • • • u 0 y 1 y 2 y 3
f 1 f 2 • • • u 1 u 2 y 1 y 2 y 3 (a) Search zone u 1 is chosen for the exploration. f 1 f 2 • • • u 1 u 2 y 1 y 2 y 3 (b)
Search zone u 1 is discarded from the search region. Search zone u 2 is chosen for the exploration. By exploring the search zone defined by u 2 , we generate y 2 . The part of the objective space dominated by y 2 is removed and two search zones, induced by u 3 , u 4 , are created (Figure 1.6a). These search zones are both empty and, thus, discarded. Consequently, the search region is empty and the algorithm stops (Figure 1.6b).

f 1 f 2 • • • u 1 u 3 u 4 y 1 y 2 y 3 (a)
The search region is updated with y 2 and two search zones u 3 , u 4 are created.

f 1 f 2 • • • u 1 u 3 u 4 y 1 y 2 y 3
(b) Search zones u 3 , u 4 are both empty. The search region is empty and the algorithm stops.

Figure 1.6: Illustration of the updating step (2).

In the following, we focus on the computation of a nondominated point in a search zone represented by its local upper bound u in the objective space.

Exploration of a seach zone

Exploring a search zone can be done by solving the following budget-constrained program with λ a vector of strictly positive weights in R p : CHAPTER 1. NOTATIONS AND PRELIMINARY RESULTS

P u        min p i=1 λ i y i s.t. y ∈ Y y i < u i , i = 1, ..., p
Remark 1.7. Problem P u involves strict inequalities y i < u i , i = 1, ..., p, that must be transformed into large inequalities of the type y i ≤ u iε where ε is a small enough value. In our experiments, the objectives take integer values and we set ε = 1.

Two cases can occur:

• Program P u is infeasible, in which case the search zone corresponding to u is removed from the search region;

• Program P u yields a nondominated point y * and the search region is updated by removing the part of the objective space that y * dominates.

Figure 1.7 depicts the exploration of the search zone induced by u 0 in Example 1.1.

f 1 f 2 • • • u 0 y 1 y 2 y 3 (λ 1 , λ 2 )
Figure 1.7: Exploration of the search zone induced by u 0 with the vector (λ 1 , λ 2 ).

Point y 1 is generated by exploring the search zone induced by u 0 .

Multi-objective combinatorial optimization problems

The multi-objective combinatorial optimization (MOCO) problems are characterized by a complex structure of problems with more than two objectives. The number of nondominated points and the computation time of the exact generation of the nondominated set of MOCO problems may increase exponentially in the size of the instance. We tested our results on two types of MOCO problems: the multi-objective knapsack problem and the multi-objective assignment problem.

Multi-objective knapsack problem

The multi-objective knapsack problem (MOKP) consists in selecting a subset of items out of a set of n items in order to maximize the total profit. Each item i = 1, ..., n is characterized by a weight ω i and p profits denoted by v k i , k = 1, ..., p. The total weight of the selected items cannot exceed the knapsack capacity, denoted by Q. It is assumed that all coefficients v k i , ω i , and Q are non-negative. The total weight and total profit is computed by adding up the weight and profits of every selected items. Decision variable x i denotes whether item i is selected for the knapsack or not. The MOKP is formulated as follows.

(MOKP) max n i=1 v k i x i k = 1, ..., p s.t. n i=1 ω i x i ≤ Q x i ∈ {0, 1} i = 1, ..., n (1.8)
Several types of instances, classified by complexity, can be generated with different levels of correlation between profits and weights. We tested our results on uncorrelated instances, that is we used instances where profits and weights are independent. For all instances, we set

Q = n i=1 ω i 2 .

Multi-objective assignment problem

The multi-objective assignment problem (MOAP) consists in assigning n agents to n tasks in order to minimize the total assignment cost. An agent is assigned to one and only one task and a task is assigned to one and only one agent. Each agent-task assignment (i, j), i, j = 1, ..., n involves p costs c k i,j , k = 1, ..., p. It is assumed that all objective function coefficients c k i,j are non-negative. The total cost of an assignment is computed by adding up the costs of every chosen agent-task assignment. Decision variable x ij denotes wether the agent-task assignment (i, j) is seletected for the total assignment or not.

(MOAP) min n i=1 c k ij x ij k = 1, ..., p s.t. n i=1 x ij = 1 j = 1, ..., n n j=1 x ij = 1 i = 1, ..., n x ij ∈ {0, 1} i, j = 1, ..., n
(1.9)

There exist algorithms that are especially designed for MOKP (e.g. [START_REF] Bazgan | Solving efficiently the 0-1 multi-objective knapsack problem[END_REF]) and MOAP(e.g. [START_REF] Przybylski | A two phase method for multiobjective integer programming and its application to the assignment problem with three objectives[END_REF]). They take advantage of the specific structure of these problems and do not fully use the framework of Algorithm 1.

Convex Sets

After introducing definitions and some results on convex sets, we then focus on polyhedra and cones. Most of the presented definitions and propositions can be found in textbooks like [START_REF] Rockafellar | Convex analysis[END_REF] and [START_REF] Nemhauser | Integer and Combinatorial Optimization[END_REF].

Elements of Linear Algebra

Definition 1.8 (Linear independence). A set of vectors d 1 , ..., d m ∈ R p is said to be linearly independent if m i=1 λ i d i = 0 if and only if λ i = 0 for all i = 1, ..., m Definition 1.9 (Dimension). The dimension of a set S ⊆ R p is denoted by dim(S) and is defined as the maximal number of linearly independent vectors from S.

Definition 1.10 (Affine independence). A set of vectors d 1 , ..., d k ∈ R p is said to be affinely independent if and only if the set of vectors

d 2 -d 1 , ..., d k -d 1 ∈ R p is linearly independent. Definition 1.11 (Affine dimension). The affine dimension of a set S ⊆ R p is defined as k -1,
where k is the maximal number of affinely independent vectors from S, and is denoted by dim af f (S). Definition 1.12 (Matrix rank). The rank of a matrix A ∈ R m×p is denoted by rank(A) and is defined as the maximal number of linearly independent rows or columns of A. Definition 1.13 (Matrix kernel). The kernel of a matrix A ∈ R m×p is denoted by ker(A) and is defined as follows.

ker(A) = {y ∈ R p : Ay = 0}

Theorem 1.14 (Rank-nullity theorem). For a matrix A ∈ R m×p , we have :

rank(A) + dim(ker(A)) = p Definition 1.15 (Convex set). A set S ⊆ R p is said to be convex if λy 1 + (1 -λ)y 2 ∈ S for all y 1 , y 2 ∈ S and 0 ≤ λ ≤ 1
Definition 1.16 (Convex hull). The convex hull of a set S ⊆ R p is the set of all convex combinations of elements of S and is denoted by conv(S). The convex hull of a set S is formulated as follows.

conv(S) = {y ∈ R p : y = k i=1 λ i y i , k ≥ 1, y 1 , ..., y k ∈ S, λ 1 , ..., λ k ≥ 0, and k i=1 λ i = 1} Definition 1.17 (Cone). A set C ⊆ R p is called a cone if λd ∈ C,
d 1 + d 2 ∈ C, for all d 1 , d 2 ∈ C Definition 1.20 (Pointed cone). A cone C ⊆ R p is said to be pointed if for d ∈ C with d = 0, -d / ∈ C
Definition 1.21 (Dual cone). Let S ⊆ R p be a set. The dual cone of S is denoted by S * and is defined as follows

S * = {d ∈ R p : dd ′ ≥ 0 for all d ′ ∈ S} 1.2. CONVEX SETS f 1 f 2 • • A B P • Extreme point

Polyhedra

Definition 1.22 (Polyhedron). A set P is called a polyhedron if there exists a matrix A ∈ R m×p and a vector b ∈ R m such that:

P = {y ∈ R p : Ay ≧ b}
A and b are referred to as the constraint matrix and the right-hand side vector of P , respectively.

Remark 1.23. Observe that an equality constraint A i y = b i , where A i is a vector in R p and b i a scalar in R, can be decomposed into two inequality constraints A i y ≥ b i and -A i y ≥ -b i .

Definition 1.24 (Extreme point). A point y ∈ P is an extreme point of P if there do not exist y 1 , y 2 ∈ P , y 1 = y 2 , such that y = 1 2 y 1 + 1 2 y 2 Definition 1.25 (Ray). A vector r ∈ P is a ray of P if and only if for any point y ∈ P , y + λr ∈ P, λ ≥ 0 Definition 1.26 (Extreme ray). A ray r of P is an extreme ray if there do not exist r 1 , r 2 ∈ P ,

r 1 = λr 2 , λ ≥ 0, such that r = 1 2 r 1 + 1 2 r 2 Definition 1.27 (Polytope). A set P is called a polytope if P is a bounded polyhedron.
Proposition 1.28. A polytope P can be described as the convex hull of its extreme points.

A polyhedral cone can be defined by two representations. Definition 1.29 (Polyhedral cone defined by a representation matrix). A convex, polyhedral cone in R p can be represented as the solution set of a homogeneous system of linear inequalities with a matrix A ∈ R m×p , called the representation matrix. This cone is denoted by C A and is defined as follows.

CHAPTER 1. NOTATIONS AND PRELIMINARY RESULTS

f 1 f 2 • • • • A B C D P • Extreme point Figure 1
.9: Representation of a polytope P defined by 4 inequality constraints in the biobjective case. P is also the convex hull of its four extreme points A, B, C, and D.

C A = {d ∈ R p : Ad ≧ 0} We say that C A is represented by A.
Definition 1.30 (Polyhedral cone defined by a generating matrix). A convex, polyhedral cone in ⊆ R p can be represented as the set of all nonnegative linear combinations of vectors {r 1 , ..., r q }. These vectors can be arranged in the columns of a matrix R ∈ R p×q , called the generating matrix.

C = {d ∈ R p : d = Rλ, λ ≧ 0}
We say that C is generated by R.

Proposition 1.31 (Dual of a polyhedral cone). Let A be a matrix in R m×p and C A be a polyhedral cone in R p represented by A. Then, the dual cone C * A of C A is generated by the rows of matrix A.

In Definition 1.29, observe that if ker(A) = {0}, there exists d ∈ R p \ {0} such that Ad = A(-d) = 0, that is d and -d belong to C A . Therefore cases with empty nondominated set could occur. For instance, let Y = {y, y ′ } such that yy ′ = d, and thus y ′y = -d. Then, we both have y dominates y ′ , and y ′ dominates y according to the cone C A (Definition 1.18). This leads to an empty nondominated set according to the cone C A . Therefore, we work with an alternative definition of polyhedral cone. Definition 1.32 (Polyhedral cone). A convex, polyhedral cone in R p can be represented as the solution set of a homogeneous system of linear inequalities with a matrix A ∈ R m×p , called the representation matrix. This cone is denoted by C A and is defined as follows.

C A = {d ∈ R p : Ad ≧ 0, d / ∈ ker(A)}
This is equivalent to:

C A = {d ∈ R p : Ad ≥ 0}
We say that C A is represented by A.

Proposition 1.33. A polyhedral cone C A ⊆ R p is pointed if and only if rank A = p.

Remark 1.34. Note that if a cone C A is pointed, Definition 1.32 only excludes the zero vector from the cone C A .

Theorem 1.35 (Minkowski-Weyl's Theorem for polyhedral cones). For any matrix A ∈ R m×p , there exists a matrix R ∈ R p×q , 0 < q < +∞ such that the cone represented by A is generated by R.

For any matrix R ∈ R p×q , there exists a matrix A ∈ R m×p , 0 < m < +∞ such that the cone generated by R is represented by A.

Theorem 1.35 states that each polyhedral cone is generated by a finite number of vectors and represented by a finite number of inequalities. A polyhedral cone is represented in an equivalent way by its representation matrix or by its generating matrix. This suggests two problems, that are:

• Construct a minimal generating matrix R from a given representation matrix A, also called extreme ray enumeration problem;

• Construct a minimal representation matrix A from a given generating matrix R;

These two problems have been studied by many researchers in the fields of mathematics, operations research and computational geometry. Several algorithms have been proposed such as the Double Description method [START_REF] Motzkin | The double description method[END_REF], the Chernikova's algorithm [START_REF] Chernikova | Algorithm for finding a general formula for the non-negative solutions of a system of linear inequalities[END_REF] or the beneath-and-beyond method (Mulmuley, 1994[START_REF] Edelsbrunner | Algorithms in combinatorial geometry[END_REF]. These methods are useful in order to select the most suited representation at every step of an optimization algorithm involving a polyhedral cone.

Chapter 2

Partial preference models: defining trade-offs using translated cones

Chapter abstract

This chapter presents an original preference relation based on trade-offs. It proposes an alternative framework, based on trading improvement and deterioration between objectives. A point is preferred to another if it meets required improvement values on a coalition of objectives and its performance on the remaining objectives does not exceed acceptable deterioration values. These improvement and deterioration values can either be constant or variable and represent different situations of compensation. The preference relation is not necessarily transitive and corresponds to a union of translated Pareto dominance cones. We adapted a discrete multiobjective optimization algorithm based on the concept of search region. We provide numerical experiments on the multi-objective assignment problem in the three objective case.

This chapter is adapted from [START_REF] Kaddani | Partial preference models using translated cones in discrete multi-objective optimization[END_REF] and is a joint work with Satya Tamby.

Motivations

In MOO, Pareto dominance does not permit any trade-offs between objectives. Therefore, in order to make compromises, preference integration always carries a notion, implicit or not, of trade-offs between objectives [START_REF] Keeney | Decisions with multiple objectives: preferences and value trade-offs[END_REF]. With scalarization methods, trade-off rates have been studied for the weighted sum by [START_REF] Li | Quantitative parametric connections between methods for generating noninferior solutions in multiobjective optimization[END_REF] and [START_REF] Sakawa | Trade-off rates in the hyperplane method for multiobjective optimization problems[END_REF], the epsilon-constraint method [START_REF] Chankong | Multiobjective decision making: theory and methodology[END_REF] or the Weighted-Chebyshev norm [START_REF] Yano | Trade-off rates in the weighted chebyshev norm method[END_REF]. The notion of trade-offs is also inherent to the use of convex cones to model the DM's preference (see, e.g., [START_REF] Engau | Tradeoff-based decomposition and decision-making in multiobjective programming[END_REF] and [START_REF] Hunt | Relative importance of criteria in multiobjective programming: A cone-based approach[END_REF]).

In a majority of these approaches the domination structure representing the DM's preference is constant. However variable preferences have been justified in several publication such as [START_REF] Basmann | A theory of demand with variable consumer preferences[END_REF] and [START_REF] Hammond | Changing tastes and coherent dynamic choice[END_REF], and applied by [START_REF] Engau | Variable preference modeling with ideal-symmetric convex cones[END_REF] or [START_REF] Eichfelder | Optimality conditions for vector optimization problems with variable ordering structures[END_REF]. In our approach, we propose an alternative framework to model trade-offs, that can be either constant or variable, between objectives. The proposed preference relation extends Pareto dominance by defining additional cases of dominance with values representing a requirement or a tolerance on the criterion vector. A point dominates another one if, in spite of requirement thresholds on some criteria and thanks to tolerance thresholds on others, it is considered better. This is similar to the type of information required by some interactive procedures, e.g. in [START_REF] Miettinen | Interactive multiobjective oprimization system wwwnimbus on the internet[END_REF], where the DM is asked to indicate the objectives to be increased and those to be decreased. This preference relation presents numerous advantages. The trade-offs can easily take into account the notion of non-compensation. Moreover the DM can define several cases where he/she can set requirement and tolerance values to establish dominance, and thus integrate different points of view. The requirement and tolerance thresholds can either be determined as constant or variable. Each threshold being defined on the scale of its corresponding criterion, this approach easily handles heterogeneous criterion scales. Furthermore, the preference relation is not necessarily transitive. Since it adds additional cases of dominance, the number of nondominated points according to this preference relation is smaller than the Pareto nondominated set. We present how to apply a priori this preference relation in discrete multi-objective optimization.

The preference relation is presented in Section 2.2. After explaining the adaptation to a discrete multi-objective optimization algorithm in Section 2.3, we show the performance of our approach on MOCO problems in Section 2.4. Conclusions and perspectives are provided in Section 2.5.

Presentation of the preference relation

The preference relation defines additional cases of dominance by translating the Pareto dominance cone, using positive (requirement) or negative (tolerance) thresholds on each objective. After giving the definition of a threshold vector and the general preference relation, we propose an interpretation of this relation and give some particular cases.

Definitions

The threshold vector can either be defined as constant or variable.

Definition 2.1. Let y be a point in R p , ∆(y) be a threshold vector in R p and g : R p -→ Rp be a function in Rp , where R = R ∪ {-∞}. Then, we have CHAPTER 2. TRANSLATED CONES

∆ i (y) = g i (y), i = 1, ..., p
For the sake of simplicity, we define ∆(y) as a linear function of y. We propose a formulation with two parameters a, b as follows.

Definition 2.2. Let y be a point in R p , ∆(y) be a threshold vector in Rp and a, b be two vectors in R p and Rp respectively, where R = R ∪ {-∞}. Then, we have

∆ i (y) = a i y i + b i , i = 1, ..., p
If a i = 0, i = 1, ..., p, then the threshold vector ∆(y) is constant. Definition 2.2 includes thresholds being constant or calculated as a percentage of a criterion value. We give the definition of the preference relation hereafter.

Definition 2.3. Let y, y ′ be two points of Y and ∆(y) be a threshold vector in R p . yR ∆ y ′ if and only if y + ∆(y) ≦ y ′ and y = y ′ .

where y + ∆(y) is the vector of components y i + ∆ i (y), i = 1, ..., p.

The threshold vector ∆(y) is always defined by the left component of the pair (y, y ′ ). Therefore, by a slight abuse of notation, the threshold vector will be denoted by ∆ from this point. The following result exhibits an inclusion property between two threshold vectors.

Proposition 2.4. Let ∆, ∆ ′ be two threshold vectors in R p such that ∆ ≦ ∆ ′ for all y in Y . Then, we have:

N (Y, R ∆ ) ⊆ N (Y, R ∆ ′ ) Proof. Let y ∈ N (Y, R ∆ ).
Then, there exists no y ′ ∈ Y such that y ′ + ∆ ≦ y. Since ∆ ≦ ∆ ′ , there exists no y ′ ∈ Y such that y ′ + ∆ ′ ≦ y and y ∈ N (Y, R ∆ ′ ).

From Definition 2.3, the preference relation R ∆ can be represented by a translated Pareto cone and is a generalization of several known approaches:

• ∆ = (0, ..., 0). R ∆ is equivalent to the Pareto dominance and N (Y, R ∆ ) = N (Y ).

• ∆ ≤ (0, ..., 0). R ∆ is equivalent to an epsilon approximation [START_REF] White | Epsilon efficiency[END_REF].

• ∆ ≥ (0, ..., 0). R ∆ is equivalent to an approach presented in [START_REF] Engau | Exact generation of epsilon-efficient solutions in multiple objective programming[END_REF].

From Proposition 2.4 and the previous remarks, we extend the already known inclusion property between the epsilon approximated set, the nondominated set and the approach by Engau and [START_REF] Wiecek | Advances in cone-based preference modeling for decision making with multiple criteria[END_REF].

Corollary 2.5. Let ∆, ∆ ′ be two threshold vectors in R p such that ∆ ≦ (0, ..., 0) ≦ ∆ ′ for all y in Y . Then, we have:

N (Y, R ∆ ) ⊆ N (Y ) ⊆ N (Y, R ∆ ′ ) Proof. From Proposition 2.4.
In these already known approaches, coordinates of ∆ are either all positive, all negative or all zero. We present hereafter cases where ∆ may contain positive, zero and negative components.

Interpretation

We illustrate a case where defining a constant threshold vector with positive and negative values is relevant with Example 2.1.

Example 2.1. Let Y = {y 1 , y 2 , y 3 } with y 1 = (11, 9, 15), y 2 = (10, 10, 18) and y 3 = (15, 13, 12). The DM establishes that if a point y is significantly better than another point y ′ on the first two objectives and the difference on the third objective is not too important, then y is preferred to y ′ . To model this situation, we set constant requirement values of 2 on objectives f 1 and f 2 and a constant tolerance value of 5 on objective f 3 , resulting in a threshold vector ∆ = (2, 2, -5). Using this threshold, we have y 1 R ∆ y 3 in accordance with the preference information provided by the DM (see Figure 2.1a). As a consequence, y 3 does not belong to the R ∆nondominated set. Observe finally that we do not have y 2 R ∆ y 3 because, in spite of better scores for y 2 on objective f 1 and f 2 , y 2 is largely worse than y 3 on objective f 3 (see Figure 2.1b). There are no other cases of R ∆ -dominance. Therefore, we have N (Y, R ∆ ) = {y 1 , y 2 } whereas N (Y ) = {y 1 , y 2 , y 3 }.

f 1 f 2 f 3 y 3 y 1 y 1 + ∆ (a) y 1 R ∆ -dominates y 3 (Example 2.1). f 1 f 2 f 3 • • • • • • y 1 y 2 y 2 + ∆ (
The negative threshold implies that the relation R ∆ is not necessarily transitive. We illustrate such a case with Figure 2.2 in a biobjective space. Non-transitive preferences can occur quite naturally in some cases. For instance, in Figure 2.2, y 1 is preferred to y 2 since the advantage of y 2 on objective f 2 is judged negligible whereas the advantage of y 1 on objective f 1 is judged significant. Similarly y 2 is preferred to y 3 . It appears, however, that y 1 is not preferred to y 3 since the advantage of y 3 on objective f 2 is no longer negligible.

When comparing two points, a deterioration on some objectives can be compensated by a relatively good improvement on other objectives. In Example 2.1, this deterioration is limited by a finite negative threshold. However it is possible not to constrain this deterioration. Indeed, the DM could determine that large improvements on a group of objectives are significant enough and the remaining objectives do not take part in the comparison. With Example 2.2, we illustrate that R ∆ can be useful to represent this notion of non-compensation.

CHAPTER 2. TRANSLATED CONES

f 1 f 2 • • • • • y 1 y 1 + ∆ y 2 y 2 + ∆ y 3 Figure 2.2: A case where y 1 R ∆ y 2 and y 2 R ∆ y 3 but not (y 1 R ∆ y 3 ).
Example 2.2. Let y 1 , y 2 , y 3 be the points defined in Example 2.1 and y 4 be a point of Y such that y 4 = (20, 21, 6). The DM declares that a large improvement on objectives f 1 and f 2 cannot be compensated by any performance on objective f 3 . The threshold for the first two objectives is then greater than before and evaluated to 10. By defining ∆ = (10, 10, -∞), we get the following results:

y 2 + ∆ =    20 20 -∞    ≦    20 21 6    = y 4
Therefore we can conclude that y 2 R ∆ -dominates y 4 even if y 4 has a much better performance on the last objective.

We introduce the following notation for projection of points and sets in a lower dimensional objective space. Let I be a set of objective indices, then the point y and the set of points Y projected in the objective space defined by f i , i ∈ I, are denoted by y I and Y I , respectively. We define y I and Y I hereafter.

y I = (y i 1 , ..., y i k ) with {i 1 , ..., i k } = I Y I = {y ′ ∈ R |I| : there exists y ∈ Y such that y ′ = y I }
Given a threshold ∆ ∈ R p , we denote by I > and I < the subsets of indices i such that ∆ i > 0 and ∆ i < 0 for all y in Y , respectively. Proposition 2.6. Let Y be a set of points and ∆ be a threshold vector in R p . Then, we have:

N (Y I> ) ⊆ N (Y, R ∆ ) I> Proof. Assume by contradiction that there exists y in Y such that y I> ∈ N (Y I> ) but y I> / ∈ N (Y, R ∆ ) I> . Therefore there exists y ′ ∈ Y such that y ′ i + ∆ i ≤ y i , i = 1, ..., p. Consequently, y ′ i < y i , i ∈ I > , that is y ′ I> < y I> , which contradicts y I> ∈ N (Y I> ).
Hence the proposition.

The R ∆ -nondominated points can be classified into three categories. With Proposition 2.6, we outline that using threshold vectors yields R ∆ -nondominated points that are Pareto nondominated considering objectives in I > . These points form the first category (Category I ) and correspond to N (Y I> ). The second category (Category II ) corresponds to points that are not too "far" from N (Y I> ) and is defined by the requirement thresholds. Requirement thresholds set a "maximum distance" between R ∆ -nondominated points belonging to this category and the set N (Y I> ). The third category (Category III ) corresponds to points that are "far" from N (Y I> ) but with significantly better performances on objectives in I < , and is defined by the tolerance thresholds. Tolerance thresholds defines a "minimum distance" between R ∆ -nondominated points belonging to this category and the set of points dominating them on objectives in I < . When we have ∆ i = -∞, i ∈ I < , there is no R ∆ -nondominated point belonging to Category III. We illustrate these three types of points hereafter.

Example 2.3. Let y 1 , y 2 , y 3 , y 4 be the points defined in Example 2.1 and 2.2, and let y 5 be a point of Y such that y 5 = (12,11,14). Let ∆ be defined as in Example 2.1, that is ∆ = (2, 2, -5). We have I > ={1, 2}. We illustrate hereafter the set Y I> with Figure 2 and y 2 correspond to points that are Pareto nondominated points of the projected set Y I> (Category I). Category II is represented by y 5 , which is good enough on objectives in I > , so that neither y 1 nor y 2 meets the requirement threshold on both objectives. Category III is represented by y 4 , which is significantly worse than y 1 , y 2 on objectives in I > but has a significantly better performance on f 3 than points that dominate it on objectives in I > .

.3. y 1 f 1 f 2 + + + + • • + ◮ ◭ y 1 I> y 2 I> y 3 I> y 4 I> y 5 I> + R ∆ -dominated point R ∆ -nondominated point • Category I (N(Y I> )) ◭ Category II ◮ Category III
The R ∆ -nondominated set of a MOO problem can contain dominated points. We illustrate such a case in Example 2.4.

Example 2.4. Let y, y ′ be two points of Y such that y = (11,11,17) and y ′ = (10, 11, 9), and ∆ be a constant threshold vector such that ∆ = (2, 2, -6). We have y ′ ≤ y but not (y ′ R ∆ y) since

y ′ + ∆ =    12 13 3    ≦    11 11 17    = y
Thus y and y ′ belong to the R ∆ -nondominated set even if y is a dominated point.

In order to exclude Pareto dominated points from our set N (Y, R ∆ ), we introduce another preference relation, which is the union of Pareto dominance and R ∆ .

Union of preference relations

We first introduce a result on the nondominated set of a union of preference relations.

Proposition 2.7. Let R, R j , j = 0, 1, ..., m, be binary relations, such that R = m j=0 R j . Then, we have:

N (Y, R) = m j=0 N (Y, R j ).
Proof. Let y be a point of N (Y, R). Then, there is no point y ′ in Y , such that y is R j -dominated by y ′ , j = 0, 1, ..., m. Therefore y is in N (Y, R j ), j = 0, 1, ..., m. The converse is also true.

In addition to use the Pareto dominance, by setting R 0 = ≤, the DM could also be able to define more than one situation where he/she is able to establish a preference between two points. In a context of group decision making, several DMs are involved in the decision making process. Each DM could be able to propose a threshold vector so that all points of view are taken into account. Therefore we define a preference relation R U as follows.

Definition 2.8. Let y, y ′ be two points of Y and ∆ i be threshold vectors in R p , i = 1, ..., m. yR U y ′ if and only if y ≤ y ′ or yR ∆ i y ′ for some i = 1, ..., m.

We ensure with the following corollary of Proposition 2.7 that the R U -nondominated set does not contain dominated points.

Corollary 2.9. Let Y be a set of points. Then, we have:

N (Y, R U ) ⊆ N (Y ).
Proof. From Proposition 2.7, where R 0 is the Pareto dominance.

With Corollary 2.9, we also show that the R U -nondominated set contains fewer points than the nondominated set and justifies the integration of preference information.

Corollary 2.10. Let Y be a set of points in R p and R U be defined with m thresholds ∆ i , i = 1, ...m, and ∆ m+1 be a threshold vector in R p . Then, we have:

N (Y, R U ∪ R ∆ m+1 ) ⊆ N (Y, R U ).
Proof. From Proposition 2.7.

With Corollary 2.10, we show that the more you use preference information the less you have R U -nondominated points. However there could be cases where the R U -nondominated set is empty. We illustrate such a case in the following example.

Example 2.5. Let Y be a set of points in R p containing two nondominated points y 1 , y 2 such that y 1 = (10, 10, 18) and y 2 = (15, 13, 12). Let ∆ 1 = (2, 2, -6) and ∆ 2 = (-5, -4, 4) be two threshold vectors. Since

y 1 R ∆ 1 y 2 and y 2 R ∆ 2 y 1 , N (Y, R U ) is empty.
As shown in Proposition 2.11, a sufficient condition for the existence of the R Unondominated set is: Condition 1. There exists an objective j ∈ {1, ..., p} such that for each threshold ∆ i , i = 1, ..., m, ∆ i j > 0.

Condition 1 imposes the existence of at least one criterion that cannot be deteriorated in any preference situation. We introduce the following result on N (Y, R U ) under Condition 1.

Proposition 2.11. Let Y be a set of points in R p and R U be a preference relation defined by m thresholds. Under Condition 1, we have N (Y, R U ) = ∅.

Proof. Under Condition 1, let I > = {j}. Then, by Proposition 2.6, we have that

N (Y I> ) ⊆ N (Y, R ∆ i ) I> for all i = 1, ..., m. Using Proposition 2.7 and since N (Y I> ) = ∅, we get that N (Y I> ) ⊆ N (Y, R U ) I> and thus N (Y, R U ) = ∅.

Elicitation framework for thresholds

The elicitation of a threshold vector ∆ can be performed by identifying specific preference situations as in Example 2.1. In each of these situations, the DM can determine two groups of criteria, being the group of the most and the least important criteria, respectively. The thresholds corresponding to the most important criteria are positive, while thresholds corresponding to the least important criteria are negative. This reflects the fact that one is more demanding on the most important criteria, whereas one is more tolerant on the least important criteria.

We propose a framework to establish different cases of dominance between two points. The DM is asked to evaluate different levels (e.g. small, average, large) of improvement and deterioration on each criterion. After determing these values (variable or constant), the definition of thresholds can be performed by listing typical situations, combining improvements and deteriorations, where a preference is clearly established. This approach easily handles heterogeneous criterion scales since the DM is asked to establish dominance based on strengths of improvement and deterioration. We give an example of the elicitation procedure with variable thresholds in the following.

Example 2.6. We introduce hereafter a situation with three objectives, where the DM defines two groups M = {1, 2}, and L = {3}, such that the DM considers objectives in M to be more important than the objective in L. Therefore the DM is interested in even moderate improvements for objectives in M , while only large improvements are considered for the objective in L. The values of improvements and deteriorations for each objective are illustrated in Figure 2.4. First, the DM determines that a point y is preferred to another point y ′ if the performances of y on the criteria in M reflect at least a small improvement compared to y ′ and provided that the difference on the objective in L is not greater than a strong deterioration. To model this, we can define the threshold vector ∆ 1 = (10%, 10%, -70%), which is represented by the thick line in Figure 2.4. Furthermore, the DM states that a point y is preferred to another point y ′ if the performances of y on the criteria in M reflect at least an average improvement compared to y ′ on both objectives in M , irrespective of the performances on the objective in L. Difference on the objective in L is thus not taken into account. Consequently, we introduce the threshold vector ∆ 2 = (30%, 30%, -∞).

f 1 f 2 f 3 10% 30% 70% 100% 10% 30% 70% -70% small improvement average improvement large improvement large deterioration infinite deterioration -∞ -∞ -∞ ∆ 1
However, the DM also prefers points that are good on at least two objectives. If a point y ′ is good on only one objective, namely 1 (respectively 2), there could exist a point y, whose performances on objectives 2, 3 (respectively 1, 3) are much better than for y ′ . This corresponds to large improvements of y ′ on objectives 2, 3 (respectively 1, 3). In these cases, y is preferred to y ′ . Large improvements on these pairs of objectives are modeled by the following threshold vectors ∆ 3 = (70%, -∞, 100%), ∆ 4 = (-∞, 70%, 100%). Observe that, since objectives 1, 2 are more important than objective 3, an improvement on these objectives is more important than an improvement on the last objective. Therefore the value of large improvement on these objectives is smaller than the one on the last objective.

In the following, we present a framework to compute the R U -nondominated set in discrete MOO algorithms. After reminding the general principles of these algorithms, we explain the additional steps to compute the R U -nondominated set.

Adaptation to discrete multi-objective algorithms

A trivial approach to compute the R U -nondominated set would be to use a classic MOO algorithm to generate the nondominated set (see Section 1.1.5) and filter this set using pairwise comparisons in order to obtain the R U -nondominated set (Corollary 2.9). However the computation time of the nondominated set increases with the size of the instance. Therefore we use the preference information to guide the search within the objective space, in order to have a gain in computation time. We adapt the main steps of Algorithm 1, presented in Section 1.1.5, to directly compute the R U -nondominated set. Such methods iteratively find a nondominated point and then update the search region. We first present the adaptation of the updating step when a point is generated (Section 2.3.1). Then, we present the adaptation of the generating step of a R U -nondominated point (Section 2.3.2).

Updating the search region

Most approaches designed to generate the nondominated set iteratively update a search region containing the remaining nondominated points. Given any generated point y in Y , they provide a procedure to remove from the search region the part that y dominates according to the Pareto dominance. Extending the definition of the search region, presented in Section 1.1.5, to the case of a relation R, we denote by S R (N ) and D R (y) the search region associated to the preference relation R and the part of the objective space that y R-dominates, respectively.

S R (N ) = {y ∈ R p : there is no y ′ ∈ N such that y ′ Ry} D R (y) = {y ′ ∈ R p : yRy ′ }
Thus, updating the search region S R (N ) by a newly generated point y can be reformulated as follows:

S R (N ∪ {y}) = S R (N )\D R (y)
We introduce a trivial result concerning the region R ∆ -dominated by a point y. We recall that D(y) denotes the part of the objective space that y Pareto dominates.

Proposition 2.12. Let y be a point in Y and ∆ be a threshold vector in R p . Then, we have D R ∆ (y) = D(y + ∆).

Proof. Trivial from the definition of R ∆ .

The following corollaries are deduced from Proposition 2.12. CHAPTER 2. TRANSLATED CONES Corollary 2.13. Let y be a point in Y , ∆ be a threshold vector in R p , and R U =≤ ∪R ∆ . Then, we have:

D R U (y) = D(y) ∪ D(y + ∆)
Therefore we introduce the following formulation for the search region S R U (N ) associated to the preference relation R U .

Corollary 2.14. Let y be a point in Y , ∆ be a threshold vector in R p , R U =≤ ∪R ∆ , and N be a set of points in R p . Then, we have:

S R U (N ∪ {y}) = S R U (N )\( D(y) ∪ D(y + ∆) )
Each time a point y is generated, most of the recent generic discrete MOO algorithms (see, e.g., [START_REF] Kirlik | A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems[END_REF], [START_REF] Sylva | Enumerating the set of non-dominated vectors in multiple objective integer linear programming[END_REF]) include a procedure which takes y as an input and removes from the search region the part of the objective space that y dominates according to Pareto dominance. From Corollary 2.14, updating the search region associated to R U =≤ ∪R ∆ can be done with the same procedure by not only updating with the original point y but also updating with an artificial point y + ∆. We illustrate the result above with Figure 2.5. Extending this procedure to several thresholds ∆ 1 , ..., ∆ m is straightforward. After generating a point y, the search region is updated with y and m artificial points y + ∆ 1 , ..., y + ∆ m . We now focus on the generation of a new R U -nondominated point.

f 1 f 2 • • y y + ∆

Generating a R U -nondominated point

The search region can be decomposed as a list of search zones [START_REF] Klamroth | On the representation of the search region in multi-objective optimization[END_REF]. Each search zone is induced by a local upper bound u in R p and is defined as follows.

{y ∈ R p : y i < u i , i = 1, ..

., p}

The recent discrete MOO algorithms mentioned above maintain, more or less explicitly, a list of search zones that represents the search region. Generating a nondominated point is done by choosing a search zone in the list and generating a nondominated point in this search zone if it

f 1 f 2 • • • u 1 u 2 y 1 y 2 y 3 (a)
The part of the objective space Pareto dominated by y is removed from the search region.

f 1 f 2 • • • • u 1 u 3 u 4 y 1 y 1 + ∆ y 2 y 3 (b)
The part of the objective space Pareto dominated by y + ∆ is removed from the search region. exists. In the following, we focus on the computation of a R U -nondominated point in a search zone denoted by its local upper bound u in the objective space.

Exploring a search zone can be done by solving the following program with λ a vector of strictly positive weights in R p (see Section 1.1.5):

P u        min p i=1 λ i y i s.t. y ∈ Y y i < u i , i = 1, ..., p
Two cases can occur:

• Program P u is infeasible, in which case the search zone corresponding to u is removed from the search region;

• Program P u yields a Pareto nondominated point y * . However y * can be R ∆ i -dominated, i = 1, ..., m, by a point outside the search zone u as illustrated in Figure 2.7.

For the sake of clarity, we first present the generation of a R U -nondominated point with one threshold vector ∆ and then explain the extension to several threshold vectors ∆ i , i = 1, ..., m.

Case with one threshold

Proposition 2.15. Let y * be the optimal point of P u , λ be a vector of strictly positive weights in R p and P * ∆ be the following program:

P * ∆        min p i=1 λ i y i s.t. y ∈ Y y i + ∆ i ≤ y * i , i = 1, ..., p 1. If P * ∆ is infeasible, then y * ∈ N (Y, R U ); f 1 f 2 • • • u ′ u y ′ y ′ + ∆ y * Figure 2.7: y * is RU -dominated by y ′ ,
which does not belong to the zone induced by u.

If P

* ∆ is feasible, then y * / ∈ N (Y, R U ).
Proof.

1. If P * ∆ is infeasible, there exists no point y ′ in Y such that y ′ + ∆ ≦ y * . Therefore y * is R U -nondominated. 2. If P * ∆ is feasible and y ′ is its optimal point, y ′ + ∆ ≦ y * . Therefore y * is R ∆ -dominated by y ′ .
Remark 2.16. Observe that using a constant objective function does not change Proposition 2.15. However program P * ∆ would possibly yield a point y ′′ dominated by another point y ′ . Since y ′ ≤ y ′′ then, for a i ≥ -1, i = 1, ..., p, we have

y ′ i + ∆ i ≤ y ′′ i + ∆ i .
Therefore, in the case where a i ≥ -1, for all i = 1, ..., p, y ′ + ∆ ≤ y ′′ + ∆ and the part of the objective space R ∆ -dominated by y ′′ is smaller than the part R ∆ -dominated by y ′ . This would possibly slow the algorithm since the updating step would discard less points at each iteration. Note that, in the numerical experiments, we only used ∆ with a i ≥ -1, for all i = 1, ..., p.

Proposition 2.15 provides two rules when generating a nondominated point y * .

• If y * is R ∆ -nondominated, then y * is added to N and the search region S R U (N ) is updated with y * and y * + ∆ (Section 2.3.1).

• If y * is R ∆ -dominated by a point y ′ , then y * is not added to N but the search region S R U (N ) is updated with y ′ + ∆ to avoid enumerating y * again, and y * + ∆ since there could be points that are R ∆ -dominated by y * but not by y ′ (see Figure 2.8).

In the worst case, this procedure checks the R U -nondominance for all points in N (Y ). Since the point generated at each step is discarded from the search region in both cases, each point is generated only once and this procedure is thus finite.

Remark 2.17. Note that using y * to update the search region is redundant with using y ′ + ∆. Observe also that y ′ can still be generated in further iterations since y ′ + ∆ does not prune y ′ .

Remark 2.18. The linear formulation of ∆ (Definition 2.2) is helpful, since it only adds linear constraints to the problem.

f 1 f 2 • • • • • • u 1 u 2 u 3 y ′ y ′ + ∆ y * y * + ∆ y ′′ Figure 2.8: The point y ′′ is RU -dominated by y * , even if y * is also RU -dominated.

Case with several thresholds

We extend the generating step for several threshold vectors ∆ i , i = 1, ..., m. We check for each threshold

∆ i , i = 1, ..., m, if the point is R ∆ i -dominated by solving the problem P * ∆ i
described in Proposition 2.15. There are two possible situations:

• If for all i = 1, ..., m, there exists no feasible point for all P * ∆ i , then y * is R U -nondominated. Therefore we add y * to the R U -nondominated set. The search region is updated with y * , y * + ∆ 1 , ..., y * + ∆ m .

• If, for some k = 1, ..., m the point y * is R ∆ k -dominated by a point y ′ , y * is not added to the R U -nondominated set . Programs P * ∆ k+1 , ..., P * ∆ m are not solved since y * is already proven to be R U -dominated. The search region is updated with y ′ + ∆ 1 , ..., y ′ + ∆ m and also y * + ∆ 1 , ..., y * + ∆ m for the same reason as in the specific case with one threshold vector (see Figure 2.8).

Observe that both updating the search region and computing a R U -nondominated point require a larger computational burden than for the Pareto nondominated set. Indeed with m threshold vectors, updating the search region requires m additional updates and 1 to m additional optimizations. However the preference information conveyed by these thresholds usually leads to a R U -nondominated set which is substantially smaller than the Pareto nondominated set. This is illustrated in Section 2.4.

Numerical experiments

We performed our experiments using the generic algorithm presented in [START_REF] Tamby | Approches génériques pour la programmation linéaire en nombres entiers multi-objectif[END_REF], which refines Algorithm 1 and maintains a list of search zones to describe the search region. This algorithm generates all nondominated points for discrete MOO problems. We have generated our results on the Multi-Objective Assignment Problem (MOAP) presented in Section 1.1.6. The objective costs are random integers uniformly drawn in the interval [1,20].

CHAPTER 2. TRANSLATED CONES

For MOAP, we used the following instance sizes:

• p = 3 and n = 30 (3-MOAP30); andn = 40 (3-MOAP40); • p = 3 andn = 50 (3-MOAP50).

• p = 3
The thresholds used for the experiments are the one used in Example 2.1. The parameters a and b correspond to the parameters of Definition 2.2:

• ∆ 1 with a 1 = (10%, 10%, -70%) and b 1 = (0, 0, 0);

• ∆ 2 with a 2 = (30%, 30%, 0) and b 2 = (0, 0, -∞);

• ∆ 3 with a 3 = (70%, 0, 100%) and b 3 = (0, -∞, 0);

• ∆ 4 with a 4 = (0, 70%, 100%) and b 4 = (-∞, 0, 0).

We computed the Pareto nondominated set and the R U -nondominated set with R U being the union of the Pareto dominance and

R ∆ 1 , R ∆ 2 , R ∆ 3 , R ∆ 4 .
A computer with a Linux Debian operating system, 3.2 GHz processor and a 16 GB memory limit has been used for the experiments. The implementation has been written in Haskell and calls the IBM Ilog Cplex(TM) 12.6 solver using the Concert(TM) technology in C++. We used 10 instances for each problem size to compute our results. We report the average CPU time (s), the average size of the different R-nondominated set, denoted by |N (Y, R)|, R being either Pareto dominance or R U . Since R U does not satisfy Condition 1, we also give the number of empty R U -nondominated sets (# Empty) in Tables 2.1, 2.2, and2 We observe that for all instances the gain in computation time is significant. The number of R U -nondominated points is also reduced compared to the Pareto nondominated set. The ratio concerning the difference of size of each nondominated set does not correspond to the ratio on the difference of computation time. Indeed, there are between 1 and 4 additional optimizations to check for R U -dominance. Therefore the time spent for each generated R U -nondominated point is larger than the time spent for a Pareto nondominated point. Observe that even if ∆ 1 , ∆ 2 , ∆ 3 , and ∆ 4 do not satistfy Condition 1, there is no empty set in all instances.

In order to evaluate the quality of the returned R U -nondominated set, and its consistency with the threshold vectors, we compare it with the Pareto nondominated set. For this purpose, after computing these two sets, we take as indicators the minimum and maximum values on each objective over each of these two sets. These values correspond to the ideal and nadir point values, respectively. We report the results on one 3-MOAP40 instance in Table 2.4.

3-MOAP40 instance

Ideal Nadir Several observations can be made on this instance. The threshold vectors ∆ 1 , ∆ 2 , ∆ 3 and ∆ 4 represent a situation where f 1 and f 2 are more important than f 3 . Indeed, the maximum value on f 1 and f 2 have significantly decreased, while the maximum performance on f 3 has only slightly decreased. On the contrary, the ideal point has only slightly increased on f 1 and f 2 in comparison with f 3 . This underlines the fact that good performances on f 3 are less considered. Observe that the deterioration on f 1 and f 2 is the consequence of avoiding points being good on only one objective. Finally, note that the modifications of the ideal and nadir point on f 1 and f 2 are comparable, which seems natural since objectives f 1 and f 2 are both considered of similar importance.

f 1 f 2 f 3 f 1 f 2 f 3 Pareto

Conclusions and perspectives

We presented an original preference relation based on requirement and tolerance values, that translate the Pareto dominance. This not necessarily transitive preference relation can have a variable preference structure and integrates the notion of non-compensation. To use this preference relation, we based our approach on a general scheme of multi-objective discrete optimization algorithms. After testing on several instances of MOCO problems, we observe that the results are promising.

This work offers several research directions such as eliciting methods for the thresholds or use a set of thresholds defined by constraints. Applying this preference relation with approximation algorithms such as, e.g., multi-objective evolutionary algorithms could be useful in the case where the computational effort is too demanding for exact algorithms. Covering sets ( [START_REF] Vanderpooten | Covers and approximation in multiobjective optimization[END_REF] could also be studied in this framework when the nondominated set according to the preference relation is empty.

Chapter 3

Partial preference on weights: a preference relation based on the weighted sum

Chapter abstract

This chapter presents a preference relation based on the weighted sum and partial information on weights. This preference relation has already been studied in various publications but we especially study the application of this relation in multi-objective optimization. Properties are presented in the general case and in the case where the weight set is defined as a polytope. In the latter case, a transformation of the objective functions, based on the extreme weights of the weight set, leads to compute the nondominated set corresponding to the preference relation. We introduce a two-stage procedure for weight sets having a large number of extreme weights. Some preference elicitation frameworks are then studied. Numerical experiments are conducted on several instances of the multi-objective knapsack problem and on the multiobjective assignment problem. These experiments show the applicability of the approach, the relevance of our two-stage procedure and also interesting results concerning the qualitative nature of the generated set.

This chapter is adapted from [START_REF] Kaddani | Weighted sum model with partial preference information: application to multi-objective optimization[END_REF] which has been accepted for publication.

Motivations

The weighted sum is a simple and well-known scalarizing function, which has been widely used to propose interesting solutions to the DM. A major difficulty of this approach is to obtain precise parameter values. There exist numerous methods to elicit the weight vector. Among these, we can cite the max entropy weight [START_REF] Jaynes | Information theory and statistical mechanics[END_REF], the ratio method [START_REF] Edwards | How to use multiattribute utility measurement for social decisionmaking[END_REF], rank-sum [START_REF] Stillwell | A comparison of weight approximation techniques in multiattribute utility decision making[END_REF], rank-order centroid [START_REF] Barron | Selecting a best multiattribute alternative with partial information about attribute weights[END_REF], the swing weighting method [START_REF] Edwards | Decision analysis and behavioral research[END_REF], the trade-off method [START_REF] Keeney | Decisions with multiple objectives: preferences and value trade-offs[END_REF] or the pricing out method [START_REF] Keeney | Decisions with multiple objectives: preferences and value trade-offs[END_REF]. Although a large number of elicitation procedures to assess these values are available, they are demanding for the DM. Furthermore, the final weights depend on the elicitation procedure used (Hutton [START_REF] Hutton Barron | Decision quality using ranked attribute weights[END_REF].

Assuming that precise weights could be defined, using a weighted sum usually leads to a single point, while DMs are often willing to be presented with a few alternatives of interest in order to make their choice. Another limitation of this approach is that it only yields supported nondominated points. Rather than using one single weight, partial preference information can be used to define a set of possible weights [START_REF] Fishburn | Analysis of decisions with incomplete knowledge of probabilities[END_REF].

The approaches exploiting the weight set defined by partial preference information on weights can be classified into two categories. Some authors, like [START_REF] Sarin | Elicitation of subjective probabilities in the context of decision making[END_REF], focus on points called potentially optimal. Potentially optimal points are points that are optimal for a weighted sum in the weight set. By definition, these points correspond to supported nondominated points. This approach has been studied in [START_REF] Hannan | Obtaining nondominated priority vectors for multiple objective decisionmaking problems with different combinations of cardinal and ordinal information[END_REF], [START_REF] Insua | A framework for sensitivity analysis in discrete multiobjective decision-making[END_REF], Athanassopoulos and [START_REF] Athanassopoulos | Dominance and potential optimality in multiple criteria decision analysis with imprecise information[END_REF] or more recently in [START_REF] Benabbou | On possibly optimal tradeoffs in multicriteria spanning tree problems[END_REF]. The concept of potential optimality is justified by stating that, if a DM is able to determine the exact value of the weights, the optimal solution will be supported. From a decision viewpoint, nonsupported nondominated points are not less interesting than the supported ones, and should not be discarded owing to the choice of a specific scalarizing function. Moreover, focusing only on potentially optimal solutions may lead to discard solutions of interest. For instance, a point that is not optimal for any weight in the weight set but is the second best for most possible weights in the weight set might be quite relevant.

We adopt a second approach as in [START_REF] Kmietowicz | Decision theory, linear partial information and statistical dominance[END_REF], [START_REF] Kofler | Decision making with linear partial information (l.p.i.)[END_REF], [START_REF] Kirkwood | Ranking with partial information : A method and application[END_REF], [START_REF] Carrizosa | Multi-criteria analysis with partial information about the weighting coefficients[END_REF], [START_REF] Athanassopoulos | Dominance and potential optimality in multiple criteria decision analysis with imprecise information[END_REF]. After determining a set of possible weights representing the DM's preferences, a solution is nondominated if there is no solution with better weighted sum value for every possible weight in the weight set. This approach has also been studied in [START_REF] Podinovskii | Decision under multiple estimates for the importance coefficients of criteria and probabilities of values of uncertain factors in the aim function[END_REF], who showed the correspondance with polyhedral cones when the weight set is defined as a polytope. Typically the set of weights is determined by constraints reflecting ordinal information on the weights (e.g. ranking of the weights by order of importance, categorization of criteria into groups of different importance) or cardinal information (e.g. lower and upper bounds for each criterion weight), see [START_REF] Park | Mathematical programming models for characterizing dominance and potential optimality when multicriteria alternative values and weights are simultaneously incomplete[END_REF] for a literature review. Preference elicitation is much less demanding than when requiring precise values. This can also facilitate agreement on a set of weights within a group of DMs. Weights are supposed to reflect the importance of the objectives. Consequently this preference relation is meaningful when the objectives are expressed on the same scale. We make this assumption in the following. Otherwise, the criteria should first be rescaled conveniently. [START_REF] Sarin | Elicitation of subjective probabilities in the context of decision making[END_REF] formulates a mathematical program to determine dominance between two known alternatives. When the constraints determining the weight set are linear, the set of weights can be represented by its extreme weights. Given various types of ranking, [START_REF] Kirkwood | Ranking with partial information : A method and application[END_REF] provide rules for pairwise comparison of alternatives, based on extreme weights of the weight set to check for preference. [START_REF] Kofler | Decision making with linear partial information (l.p.i.)[END_REF], [START_REF] Kmietowicz | Decision theory, linear partial information and statistical dominance[END_REF] extend these rules to arbitrary subsets of weights.

This approach uses a priori preference information to generate a substantially smaller number of potentially interesting solutions for the DM with a great computational time saving. This partial preference relation has the advantage of being based on the widely known weighted sum. However, in contrast with the classic weighted sum model, nonsupported solutions are not necessarily pruned with this preference relation. To the best of our knowledge, the preference relation has only been applied to a given set of solutions and to continuous multi-objective optimization problems [START_REF] Mármol | The use of partial information on weights in multicriteria decision problems[END_REF]. We especially focus on its application to multiobjective optimization and MOCO problems, which involve a large nondominated set, although the presented concepts are more general. We present a generic approach based on polyhedral cones to deal with an arbitrary weight polytope constructed from the DM's preferences. The approach consists in generating the nondominated set of a new multi-objective optimization problem, where the number of objectives corresponds to the number of extreme weights of the weight polytope. When the number of extreme weights is larger than the original number of objectives, the computation time may increase, even if the number of returned solutions is substantially smaller than for the (Pareto) nondominated set of the original multi-objective problem. In this case, we propose a two-stage procedure to improve the computation time.

The preference relation and its properties are presented in Section 3.2. The computation of the corresponding nondominated set is studied in Section 3.3. Then, several preference elicitation frameworks are presented in Section 3.4. After showing the numerical results in Section 3.5, Section 3.6 provides conclusions and further possible work directions.

Presentation of the preference relation

In terms of preference representation, we do not consider here that the DM's preferences are represented by a weighted sum with precisely defined weights, which would imply that nonsupported points are irrelevant. Instead, we introduce a preference relation which is not limited to supported nondominated points, even if it is based on the weighted sum. Rather than using one single weight, we use partial preference information to define a set of possible weights. Similarly to [START_REF] Kmietowicz | Decision theory, linear partial information and statistical dominance[END_REF], [START_REF] Kofler | Decision making with linear partial information (l.p.i.)[END_REF], [START_REF] Kirkwood | Ranking with partial information : A method and application[END_REF], [START_REF] Carrizosa | Multi-criteria analysis with partial information about the weighting coefficients[END_REF], [START_REF] Athanassopoulos | Dominance and potential optimality in multiple criteria decision analysis with imprecise information[END_REF], [START_REF] Greco | Ordinal regression revisited: multiple criteria ranking using a set of additive value functions[END_REF], [START_REF] Podinovskii | Decision under multiple estimates for the importance coefficients of criteria and probabilities of values of uncertain factors in the aim function[END_REF], we define the following binary relation. Definition 3.1. Let W be a weight set in R p ≥ and Y be a set of points in the objective space. For any y, y ′ in Y , yR W y ′ if and only if for all w in W , wy ≤ wy ′ and there exists w ′ in W such that w ′ y < w ′ y ′ .

In Example 3.1 we illustrate the case with p = 2, where the DM expresses his/her preferences for balanced solutions and the weighted sum scalarization is not able to propose the solution offering the best compromise.

Example 3.1. We consider a situation where 5 alternatives, evaluated on a scale [0, 20], are presented to the DM. Each of these are represented in a bi-objective space by their respective points (see Figure 3.1). We assume that the DM considers that both criteria, to be minimized, are equally important and prefers balanced solutions. w = (0.5, 0.5)

+ + + + + f 1 f 2 y 1 (17, 0)
y 2 (10, 1)

y 3 (5, 8)
y 4 (1, 11) y 5 (0, 13) Figure 3.1: Illustration of Example 3.1. y 3 is a nonsupported solution that cannot be optimal for any weighted sum with positive weights.

By choosing a weight w = (0.5, 0.5) the weighted sum outputs y 2 as the most preferred alternative. Clearly y 3 is a balanced alternative and should be proposed to the DM. Unfortunately y 3 is a nonsupported nondominated point and cannot be obtained by optimizing any weighted sum. Assume now that we translate the information that both criteria have the same importance by defining the following set of weights.

W = {w ∈ R 2 : 0.4 ≤ w 1 ≤ 0.6, 0.4 ≤ w 2 ≤ 0.6, w 1 + w 2 = 1}.
A solution y is preferred to another solution y ′ if the weighted sum of y is better than the weighted sum of y ′ for all weights in the set W , with at least one strict inequality.

Figure 3.2a shows the value of the weighted sum for each point y i with w in W . From this representation we see that y 1 and y 5 are worse than y 2 and y 4 respectively, for any weight in W . Therefore they are dominated according to R W . However neither y 2 nor y 4 are better than y 3 for all weights in W . We also observe in Figure 3.2b that when no restriction is made on the set of weights, the R W -nondominated set coincides with the standard nondominated set since for all points y i , i = 1, ..., 5, there is no other point y j , j = 1, ..., 5, such that y j R W y i . This is true in general (see Corollary 3.5). The R W -nondominated sets are listed below in Table 3.1 depending on the chosen weights or subset of weights.

Note that y 3 belongs to the nondominated set if W is used instead of a single weight, even if y 3 is nonsupported.

Example 3.1 illustrates how a partial preference model for weights circumvents some limits of the weighted sum scalarization while reducing the size of the nondominated set. We present hereafter some general properties of relation R W (Section 3.2.1) and also some specific properties when W is defined by linear inequalities (Section 3.2.2).

• • • • • • • • • • • • • • • • • • • • w 1 wy i 0.4 0.6 1 0 | | + (b)
Weighted sum value of wy i with w 1 between 0 and 1. Information on weights Nondominated sets none {y 1 , y 2 , y 3 , y 4 , y 5 } w = (0.5, 0.5) {y 2 } w = (0.4, 0.6) {y 2 } w = (0.6, 0.4) {y 4 } w ∈ W {y 2 , y 3 , y 4 } Table 3.1: Nondominated points of Example 3.1 depending on the chosen weights or subset of weights.

General case

In the absence of any information, the maximal set of weights is R p ≥ , since choosing a weight vector outside the positive orthant would yield dominated points. Moreover, w.l.o.g., we restrict the maximal set to the standard simplex K p :

K p = {w ∈ R p ≥ : p i=1 w i = 1}, (3.1)
The equality constraint p i=1 w i = 1 will be referred to as the normalization constraint.

Any weight set W is a subset of K p . An illustration of K p and W are given in the threedimensional case in Figures 3.3a and 3.3b respectively.

Standard weighted sum with weights in K p only guarantee to yield weakly nondominated points. A weakly nondominated point can be dominated by another point but has the same value on at least one criterion. This occurs when the chosen weight has a zero value on one of

• • • 1 1 1 w 1 w 2 w 3 (a) The standard simplex K 3 in R 3 . • • • • • w 1 w 2 w 3 w 4 w 5 w 1 w 2 w 3 (b) A constrained weight set W in R 3 .
W has 5 extreme points. its components. To avoid this situation, it is common to use a small but strictly positive value on weights that were originally equal to zero. Instead of imposing all weights of the weight set W to only have strictly positive components, we introduce below a less restrictive assumption on W , in order to ensure that the R W -nondominated set does not contain any dominated point.

Assumption 3.1 (Consistency). Let W ⊆ K p be a set of weights, for each criterion k = 1, ..., p, W contains at least one weight w k such that w k k > 0. Assumption 3.1 is not restrictive since otherwise a criterion is never taken into account in W , and can thus be removed. The following result shows that all R W -nondominated points are nondominated. Proposition 3.2. Let Y be a set of points in R p and W ⊆ K p be a set of weights verifying Assumption 3.1. Then, we have:

N (Y, R W ) ⊆ N (Y )
Proof. Let y, y ′ be two points in Y such that y ≤ y ′ . Then we have y j ≤ y ′ j for all j = 1, ..., p, which implies that for all weights in W , we have wy ≤ wy ′ . Moreover, there exists k ∈ {1, ..., p} such that y k < y ′ k . By Assumption 3.1, there exists

w k ∈ W such that w k k > 0, which implies w k y < w k y ′ . Hence for W ⊆ K p , y R W -dominates y ′ . Thus we have ≤ ⊆ R W , which implies N (Y, R W ) ⊆ N (Y, ≤) = N (Y ).
In the following we denote by dim af f (W ) the affine dimension of W .

Proposition 3.3. Let Y be a set of points in R p and W 1 , W 2 ⊆ K p be two sets of weights such that W 1 ⊆ W 2 and dim af f (W 1 ) = dim af f (W 2 )
. Then, we have:

N (Y, R W 1 ) ⊆ N (Y, R W 2 )
Proof. Suppose by contradiction that there exists a point y ∈ Y such that y ∈ N (Y, R W 1 ) and y / ∈ N (Y, R W 2 ). Then, there exists y ′ ∈ Y such that y ′ R W 2 y and not y ′ R W 1 y. Since y ′ R W 2 y and W 1 ⊆ W 2 , we have for all w ∈ W 1 wy ′ ≤ wy. Since y ′ is not R W 1 -preferred to y, we have wy = wy ′ for all w ∈ W 1 . Therefore, we have dim af f (W 1 ) ≤ dim af f (W 2 ) -1, which leads to a contradiction.

The following example shows that the condition on the equal dimension of weight sets cannot be eliminated in the above proposition.

Example 3.2. Let Y be a set of points in R 3 containing two points y and y ′ , that is Y = {y, y ′ }. Let W 1 = {w ∈ K 3 : wy = wy ′ } and W 2 = {w ∈ K 3 : wy ≤ wy ′ } be two sets of weights represented in Figure 3.4 by the thick segment [AB] and the trapezoidal area ABCD respectively.

Clearly W 1 is included in W 2 and dim af f (W 1 ) < dim af f (W 2 ). We have y ′ ∈ N (Y, R W 1 ) and y ′ / ∈ N (Y, R W 2 ), even if W 1 ⊆ W 2 . • D • • C • B • A w 3 w 1 w 2 wy < wy ′ wy > wy ′ Figure 3.4: A counter example for the inclusion property in R 3 (Example 3.2).
The next result shows that N (Y, R W ) may correspond to the nondominated set.

Proposition 3.4. Let Y be a set of points in R p , W ⊆ K p be a set of weights containing all unit vectors e i , i = 1, ..., p. Then, we have:

N (Y, R W ) = N (Y )
Proof. Let W ′ = {e 1 , ..., e p }. yR W ′ y ′ if and only if e i y ≤ e i y ′ for all i = 1, ..., p and there exists e j such that e j y < e j y ′ , which corresponds to y ≤ y ′ . Thus,

N (Y, R W ′ ) = N (Y, ≤) = N (Y ). Since dim af f (W ′ ) = dim af f (W ), we get, by Proposition 3.2 and 3.3, N (Y ) = N (Y, R W ′ ) ⊆ N (Y, R W ) ⊆ N (Y ). Hence, N (Y, R W ) = N (Y ).
In particular when no constraint is imposed on the set of weights, the R W -nondominated set coincides with the nondominated set.

Corollary 3.5. N (Y, R Kp ) = N (Y ).
We show with Proposition 3.6 that considering the weight set or its convex hull is equivalent. Proposition 3.6. Let Y be a set of points in R p , W ⊆ K p be a set of weights and W ′ = conv(W ) be the convex hull of W . Then, we have:

N (Y, R W ) = N (Y, R W ′ ) 3.2. PRESENTATION OF THE PREFERENCE RELATION 53 Proof. By Proposition 3.3, since W ⊆ W ′ and dim af f (W ) = dim af f (W ′ ), we have N (Y, R W ) ⊆ N (Y, R W ′ ). Therefore we must prove that N (Y, R W ′ ) ⊆ N (Y, R W ). Suppose by contradiction that there exists a point y ∈ Y such that y ∈ N (Y, R W ′ ) and y / ∈ N (Y, R W ).
Then, there exists y ′ such that y ′ R W y and not y ′ R W ′ y. Therefore there exists w * in conv(W ) \ W such that w * y < w * y ′ . Consequently there exist weights

w k ∈ W, k = 1, ..., q, such that w * = q k=1 λ k w k , q k=1 λ k = 1, λ k ≥ 0. Since w k ∈ W , we have w k y ′ ≤ w k y, k = 1, ..., q and thus q k=1 λ k w k y ′ = w * y ′ ≤ w * y = q k=1 λ k w k y. This contradicts w * y < w * y ′ , therefore N (Y, R W ′ ) ⊆ N (Y, R W ) and N (Y, R W ′ ) = N (Y, R W ).
Suppose two DMs define two disjoint weight sets W 1 , W 2 (Figure 3.5a). In order to take into account both DMs, we define the weight set W as the union of both weight sets, that is we define W = W 1 ∪ W 2 . With Proposition 3.6, computing the R W -nondominated set amounts to considering weights in the convex hull of W (Figure 3.5b), that are compromises of weights in W 1 and of weights in W 2 , although they were not defined by any DM.

w 1 w 2 w 3 W 1 W 2 (a) Weight set W = W 1 ∪ W 2 .
W 1 and W 2 are disjoint.

w 1

w 2 w 3 W 1 W 2 (b) Convex hull of W = W 1 ∪ W 2 .
Figure 3.5: Representation of W = W 1 ∪ W 2 and its convex hull.

Specific case: Weight set defined by linear inequalities

Suppose now that W is defined by linear inequalities. Therefore W is a polytope, as illustrated in Figure 3.3b. Every element of W can be expressed as a convex combination of its extreme points, denoted by w i . The enumeration of the extreme points of a polytope has been investigated in the field of Computational Geometry with algorithms such as the Double Description Method or the Primal-Dual method [START_REF] Bremner | Primal-dual methods for vertex and facet enumeration[END_REF]). The binary relation R W is reformulated in Proposition 3.7.

Proposition 3.7. Let Y be a set of points in R p such that y, y ′ ∈ Y and W ⊆ K p be a set of weights such that W is a polytope where w i are its extreme weights. Then, we have: yR W y ′ if and only if for all extreme weights w i we have w i y ≤ w i y ′ and there exists an extreme weight w j such that w j y < w j y ′ .

Proof.

⇒ Since we have wy ≤ wy ′ for any w ∈ W , it remains valid for any subset of W . By assumption there exists a weight w * such that w * y < w * y ′ . Since W is a polytope, w * can be expressed as a convex combination of the extreme weights of W . Thus there exists an extreme weight w j of W such that w j y < w j y ′ .

⇐ Since W is a polytope, every weight w in W is a convex, and thus positive, combination of the extreme weights w i . If y is at least better than y ′ on all extreme weights and strictly better on at least one extreme weight w j , we can conclude that for all w in W , wy ≤ wy ′ and there exists w in W , at least w = w j , such that wy < wy ′ .

In light of Proposition 3.7 the preference relation R W can be expressed with a matrix A ∈ R m×p , such that:

yR W y ′ if and only if Ay ≤ Ay ′ , where A =       w 1 1 w 1 2 ... w 1 p w 2 1 w 2 2 ... w 2 p . . . . . . . . . . . . w m 1 w m 2 ... w m p      
and w i = (w i 1 , ..., w i p ), i = 1, ..., m, are the extreme weights of W .

(3.2)

In the following, we show that the dominance relation R W corresponds to a cone relation.

Representation by a dominance cone

We focus on polyhedral cones and one of its algebraic representations.

Definition 3.8. A convex, polyhedral cone C A ⊆ R p can be represented as the solution set of a homogeneous system of linear inequalities with the m × p representation matrix A.

C A = {d ∈ R p : Ad ≥ 0}
Definition 3.9. Let y, y ′ be two points of Y and C A be a convex, polyhedral cone. Then, y dominates y ′ with respect to the dominance cone C A if and only if y ′y ∈ C A , which is equivalent to Ay ≤ Ay ′ . The nondominated set according to the dominance cone

C A is denoted by N (Y, C A ).
Therefore, as presented in [START_REF] Podinovskii | Decision under multiple estimates for the importance coefficients of criteria and probabilities of values of uncertain factors in the aim function[END_REF], the preference relation R W defines a polyhedral dominance cone C A , whose representation matrix A is the matrix of extreme weights associated to W , defined by (3.2). The set W is related to the dual cone C * A of C A (see Definition 1.21). Indeed, for all feasible points y, y ′ such that y R W -dominates y ′ and y ′y belongs to the cone C A , we know that for all

d ′ in C * A , d ′ (y ′ -y) ≥ 0. Therefore, for all feasible points y, y ′ such that y R W -dominated y ′ , C * A contains all vectors d ′ in R p such that d ′ y ≤ d ′ y.

Consequently we can say that y R C *

A -dominates y ′ and W is the section of C * A defined by the normalization constraint (3.1). Observe that since the normalization constraint sections C * A , the extreme weights of W are extreme rays of C * A and Proposition 1.31 is verified. We illustrate the relation between R W and polyhedral cones in R 2 in Figure 3.6. The weights w 1 and w 2 are the extreme weights of the weight set W , corresponding to the thick line in Figure 3.6a. The weighted sum of y with the extreme weights w 1 and w 2 are represented by two hyperplanes passing through y. Point y ′ is worse according to the weighted sum on both weights, which is equivalent for the direction y ′y to belong to the cone C A .

w 1 w 2 w 1 w 2 C * A + + W 1 1 (a) The dual cone C * A corresponding to relation R W with extreme weights w 1 , w 2 , in R 2 . f 1 f 2 + y +y ′ w 1 w 2 C A d (b) The cone C A corresponding to relation R W with extreme weights w 1 , w 2 , in R 2 . Figure 3.6: Illustration in R 2 of the cone C A and its dual cone C * A corresponding to relation R W with extreme weights w 1 , w 2 .
Most publications in the cone literature use information on trade-offs (e.g. [START_REF] Hunt | Relative importance of criteria in multiobjective programming: A cone-based approach[END_REF], [START_REF] Noghin | Relative importance of criteria: a quantitative approach[END_REF]), while R W proposes an alternative framework based on the weighted sum and partial preference information on weights to build polyhedral preference cones. An interesting research direction would be to revert this idea by translating polyhedral cones into a weight set W , that is, given a polyhedral cone C A with representation matrix A, compute the following set:

W = {w ∈ C * A : w ∈ K p }
The constraints of W would provide a new interpretation of the preference of the DM.

We present in the following how to apply preference relation R W in multi-objective optimization when the weight set is a polytope.

Application to multi-objective optimization

We introduced above the correspondance between relation R W and polyhedral cones when weight set W is a polytope. In the case where W is a polytope, we present two approaches to compute the R W -nondominated set: the direct procedure and the two-stage procedure. [START_REF] Sawaragi | Theory of Multiobjective Optimization[END_REF] provides the following result for pointed polyhedral dominance cones: Theorem 3.10 [START_REF] Sawaragi | Theory of Multiobjective Optimization[END_REF]). Let C A be a pointed, convex, polyhedral dominance cone with A ∈ R m×p its representation matrix.

Direct procedure

A[N (Y, C A )] = N (A[Y ]) with A[Y ] = {z|z = Ay, y ∈ Y }
Theorem 3.10 requires the dominance cone to be pointed. Therefore we impose conditions on the weight set W in order for the corresponding dominance cone to be pointed. First, we recall the following well known result on pointed polyhedral cones.

Theorem 3.11 (see, e.g., [START_REF] Bertsimas | Introduction to Linear Optimization[END_REF]

). Let C A be a nonempty convex polyhedral cone in R p with A ∈ R m×p its representation matrix. Then, C A is pointed if and only if rank(A) = p.
W is defined by a system of linear constraints, which are either equalities or inequalities. Besides explicit equality constraints, like the normalization constraint, the system may contain inequality constraints that induce implicit equality constraints. We say that W satisfies no additional equality constraint if it satisfies the normalization constraint and no additional explicit or implicit equality constraint. Proposition 3.12. Let W be a weight polytope in K p , A ∈ R m×p be its associated matrix of extreme weights, defined by (3.2), and C A ⊆ R p be a polyhedral cone with representation matrix A. Then, C A is pointed if and only if W satisfies no additional equality constraint.

Proof. We denote the kernel of A by ker(A) = {v ∈ R p : Av = 0}.

⇒ Assume by contradiction that C A is pointed and W satisfies an additional equality constraint. This equality constraint has the following expression p i=1 a i w i = b, with a ∈ R p , b ∈ R, that is not equivalent to p i=1 w i = 1. Thus there exists i = 1, ..., p such that ba i = 0. By using both equalities, we get p i=1 bw i = p i=1 a i w i and thus p i=1 (ba i )w i = 0, for all w in W . In particular for all extreme weights w j , j = 1, ..., m, of W , we get p i=1 (ba i )w j i = 0 which implies ker(A) = {0}. By the rank-nullity theorem, we have rank(A) < p, which implies by Theorem 3.11 that C A is not pointed. Hence the contradiction.

⇐ Assume by contradiction that W satisfies no additional equality constraint and C A is not pointed. By Theorem 3.11, rank(A) < p and by the rank-nullity theorem, ker(A) does not only contain the zero vector. Therefore for all extreme weights w j , j = 1, ..., m of W , there exists a in R p such that p i=1 a i w j i = 0. Since all weights w in W are a convex combination of the extreme weights, we have p i=1 a i w i = 0 for all w in the weight set W . Therefore W satisfies an additional equality constraint. Hence the contradiction.

We can now reformulate Theorem 3.10 using the preference relation R W based on a weight set W . Proposition 3.13. Let W be a weight polytope in K p and A ∈ R m×p be its associated matrix of extreme weights defined by (3.2). If W satisfies no additional equality constraint, then we have:

A[N (Y, R W )] = N (A[Y ]) with A[Y ] = {z|z = Ay, y ∈ Y }
Proof. From Theorem 3.10 and Proposition 3.12.

Proposition 3.13 is used in [START_REF] Carrizosa | Multi-criteria analysis with partial information about the weighting coefficients[END_REF], [START_REF] Kmietowicz | Decision theory, linear partial information and statistical dominance[END_REF], [START_REF] Kofler | Decision making with linear partial information (l.p.i.)[END_REF], [START_REF] Mármol | The use of partial information on weights in multicriteria decision problems[END_REF] when computing the preferred set corresponding to the nondominated set with respect to relation R W . Precisely, in order to obtain the R W -nondominated set for multi-objective problem (1.1), we just need to compute the Pareto nondominated set of the following multi-objective problem, where A is the matrix of extreme weights associated to W :

     min Af (x) = (A 1 f (x), A 2 f (x), ..., A m f (x)) s.t. x ∈ X
where A i is the i th row of A.

(3.3)
Therefore, the computation of the R W -nondominated set can be performed using any algorithm enumerating the nondominated set of the multi-objective optimization problem described in problem (1.1). We illustrate Proposition 3.13 with Example 3. the arcs composing the path. For our example, the MOSP problem consists in generating all nondominated paths from a to e. One algorithm to solve such problems is to calculate labels for each node [START_REF] Climaco | A bicriterion shortest path algorithm[END_REF]. Each node has several labels corresponding to nondominated paths from a to this node. Since the graph does not contain circuits, the labels of a node i can be calculated when the preceding neighbours of i have been labeled. They are calculated by adding up the labels of the preceding neighbours j of i with the cost of the arc (j, i). Once all labels of a node are calculated, we discard the dominated labels by making pairwise comparisons with the other labels of the node. The algorithm stops when e is labeled.

We observe that there are two nondominated paths As illustrated in Example 3.3, the matrix of extreme weights A is not composed of integer coefficients. Some MOO algorithms benefit from the integer nature of the objectives (see, e.g., Remark 1.7) and could thus not be used in the transformed objective space. However it is possible to use an equivalent matrix A ′ such that A ′ only has integer coefficients. Proposition 3.14. Let y, y ′ be two points in Y , W be a weight polytope in K p , A ∈ R m×p be the matrix of extreme weights associated to W , λ be a vector in R m > and A ′ ∈ R m×p be a matrix such that

A ′ i = λ i A i , i = 1, ...,
N (A[Y ]) = N (A ′ [Y ])
Proof. We have yR W y ′ if and only if Ay ≤ Ay ′ (Definition 3.7). For all i = 1, ..., m, A i y ≤ A i y ′ and there exists j = 1, ..., m, such that A j y < A j y ′ . Since λ only has strictly positive components, we also have for all i = 1, ..., m,

λ i A i y ≤ λ i A i y ′ and λ j A j y < λ j A j y ′ . Consequently, yR W y ′ is equivalent to A ′ y ≤ A ′ y ′ and y ′ -y ∈ C A ′ , hence the result.
With Proposition 3.14, we observe that the dominance cone C A ′ , with a representation matrix A ′ ∈ R m×p being the extreme weights of W multiplied by a strictly positive scalar, is equivalent to relation R W . We assume that the coefficients of the linear constraints of the weight set are rational numbers, therefore the coordinates of the extreme weights of W are also rational numbers. Consequently, it is possible to create another matrix A ′ with only integer coefficients, in order to use it in Proposition 3.13 and use MOO algorithms that are based on integer values. In Example 3.3, the matrix of extreme weights associated to the weight set is reminded hereafter. A = 0.4 0.6 0.6 0.4

Instead of A, we could also have used the following matrix A ′ , which only has integer coefficients.

A ′ = 4 6 6 4
Observe that solving problem (3.3) to determine the R W -nondominated set must be performed in a new objective space with m objectives.We give the following result on m. Proposition 3.15. Let W be a weight polytope in K p and A ∈ R m×p be its associated matrix of extreme weights defined by (3.2). Then if W satisfies no additional equality constraint, the multi-objective optimization problem described in (3.3) has at least p criteria.

Proof. For all matrices A ∈ R m×p , rank(A) ≤ min(m, p). From Theorem 3.11 and Proposition 3.12, if W satisfies no additional equality constraint, we have rank(A) = p, which implies m ≥ p for problem (3.3).

The computation of the R W -nondominated set in a larger objective space may be costly, even if this R W -nondominated set is substantially smaller than the Pareto nondominated set. Therefore, we introduce a two-stage procedure to improve the computation time.

Two-stage procedure

Presentation

The two-stage procedure is based on Proposition 3.3 and should be applied when W has a large number m of extreme weights. The details are given as follows:

Stage 1. Select a superset W ′ of a set W with the same affine dimension as W . The weight set W ′ should have less extreme weights than W , ideally p, and not be too large compared to W . We compute the R W ′ -nondominated set with the direct procedure using Proposition 3.13. The R W ′ -nondominated set may be easier to compute than the R Wnondominated set and is a superset of the R W -nondominated set by Proposition 3.3.

Stage 2. For each point y in the R W ′ -nondominated set, we compute its weighted sum value on all extreme weights of W , that is we compute Ay. These points are filtered by making pairwise comparisons: for any two points y and y ′ from the R W ′ -nondominated set, if Ay ≤ Ay ′ , then y ′ is R W -dominated by y and y ′ is discarded from the list of points.

Remark 3.16. Given the relation between R W and polyhedral cones, this two-stage procedure can also be applied for pointed polyhedral cones defined by a large number of inequalities. Every weight set has a superset with p extreme weights, which is the standard unit simplex K p defined by (3.1). In this particular case, the first stage amounts to computing the Pareto nondominated set (Corollary 3.5) and the two-stage procedure is equivalent to an a posteriori integration of the DM's preferences.

Supersets of specific weight sets W are introduced in Section 3.4 and the performance of this two-stage procedure is illustrated in Section 3.5. Both stages could suffer from a too large number of points in N (Y, R W ′ ). Several supersets can be used in the two-stage procedure and could lead to different size of R W ′ -nondominated set. We give hereafter a construction method to determine supersets of weight sets and provide an indicator to a priori assess their performance.

Superset construction methods

In this section, we focus on generating supersets with p extreme weights. This corresponds to supersets that do not increase the number of objectives for the first stage of the two-stage procedure. Therefore, they seem more interesting than other supersets in terms of computation time. A weight polytope W is defined by a constraint system. A constraint of this system is redundant if removing it does not change W . The system is irredundant if it has no redundant constraint. Based on the standard result on the maximum number of basic solutions in linear programming [START_REF] Bertsimas | Introduction to Linear Optimization[END_REF], we introduce the following result.

Proposition 3.17. Let W be a non-empty polytope of weights in K p defined by an irredundant system of p inequality constraints and satisfying no additional equality constraint. Then, the number of extreme weights is p.

Proof. By Proposition 3.15, W has at least p extreme weights. Since W is defined by an irredundant system of p inequalitity constraints and one equality constraint (the normalization constraint), the result on the maximum number of basic solutions in linear programming states that there are at most p p-1 = p extreme weights. Thus, the number of extreme weights is p.

In light of Proposition 3.17, the weight set W has p extreme weights when it is defined by p inequalities and satisfies no additional equality constraint. The weight set W is restricted to K p , therefore there are already p inequalities, w i ≥ 0, i = 1, ..., p, that cannot be omitted. The problem of computing supersets for W with p extreme weights can be stated as follows: construct a weight set W ′ defined by an irredundant system of p inequality constraints and the normalization constraint, such that W ′ is a subset of K p , which contains W . There can be an infinite number of such supersets W ′ . In the following, we propose two methods to compute some of them.

By removing constraints

Given a polytope W with a number of extreme weights larger than p, several supersets can be created by removing some inequalities until p or less inequalities remain. By deleting a sufficient number of constraints , superset W ′ will be defined by an irredundant system of p inequality constraints and will have p extreme weights (Proposition 3.17). The description of a weight set can be decomposed into three types of constraints: the non-negativity constraints, the normalization constraint and the remaining constraints. Note that the non-negativity constraints and the normalization constraint cannot be removed in order for W ′ to be included in K p . Consequently only the remaining constraints are involved in the removing step. All combinations of p or less constraints from the remaining constraints are tested. The extreme weights of the combinations are computed [START_REF] Bremner | Primal-dual methods for vertex and facet enumeration[END_REF]. If a combination corresponds to a superset W ′ with a number of extreme weights larger than p, W ′ is not defined by an irredundant system of p inequality constraints, therefore another constraint is discarded, etc. Several supersets of W are thus created and we discard the ones that contain others since they will generate at least as many points as other supersets and be thus less interesting (Proposition 3.3). Observe that removing constraints does not create any additional equality constraint and the result of Proposition 3.13 still holds.

We illustrate this method for the weight set of Figure 3.11a. Several possible supersets are created by deleting constraints. These constraints are indicated by a cross in the following figures. In Figure 3.12, the three deleted constraints lead to the superset illustrated in Figure 3.11b. This superset has 3 extreme weights and is thus an interesting candidate for the two-stage procedure.

w 1 w 2 w 3 × × × w 1 w 2 w 3 Figure 3
.12: Illustration of the construction of a superset by removing constraints of W .

In Figure 3.13, the three deleted constraints construct a weight set with 4 extreme weights. Therefore, it should be a less interesting candidate than the previous one in a two-stage procedure. To reduce the number of extreme weights of the weight set in Figure 3.13, we remove another constraint of the weight set as depicted in Figure 3.14. The constructed superset has now 3 extreme weights. In Figure 3.15, the superset has also 3 extreme weights. Therefore, this superset is an interesting candidate for the two-stage procedure. Moreover, this superset is included in the superset illustrated in Figure 3.14. Consequently, by Proposition 3.3, the superset of Figure 3.14 will yield more R W ′ -nondominated points than the superset of Figure 3.15 and is thus discarded.

By creating constraints

Another method to generate a superset W ′ consists in creating an irredundant system of p inequality constraints, that are valid for the weight set W . These p inequality constraints do not take part in the definition of W . We propose to compute the following weight set W ′ :

W ′ = {w ∈ K p : w i ≥ l i , i = 1, ..., p} (3.4)
Proposition 3.18. Let W ′ be a weight set in K p defined by (3.4). Then, W ′ has p extreme weights.

Proof. W ′ is defined by an irredundant system of p inequality constraints and one equality constraint. Consequently, by Proposition 3.17, W ′ has p extreme weights.

To generate the smallest possible weight set W ′ , we need to compute the lower bound on each weight coordinate in the weight set W . Either a linear program can be solved on W , or they can be directly computed from the extreme weights of W , if they are known. Note that since W is included in K p , l i is larger than or equal to zero for i = 1, ..., p. We illustrate this procedure hereafter. Suppose we have the weight set W depicted in Figure 3 in Figure 3.17. We can also propose another superset for the two-stage procedure, using the method based on creating constraints. After computing the lower bound on each weight, we obtain the following superset defined by three inequalities w i ≥ l i , i = 1, 2, 3, indicated by thick lines on the right side of Figure 3.18. This superset also has p = 3 extreme weights, therefore the generated superset W ′ is added to the list of candidates already computed by the previous method based on removing constraints. Both methods are interesting because, depending on the weight set W , one method will generate a superset closer to the original weight set than the other. There exists an infinite number of possible supersets for a weight set and the proposed methods only compute some of them. This part offers several work directions in the construction of supersets based, e.g., on the optimization of an estimator of performance.

w 1 w 2 w 3 w 1 w 2 w 3 w 1 ≥ l 1 w 3 ≥ l 3 w 2 ≥ l 2

Superset performance estimation

Since a weight set W can admit several candidate supersets W ′ , we need to select one of these. From Proposition 3.3, a more constrained weight set W ′ leads to a smaller R W ′nondominated set. It is thus natural to select supersets based on their size, even if this is only an a priori indication. The size of a weight set W ′ can be approximated by uniformly drawing random weights in K p . We recall the algorithm hereafter [START_REF] Rubinstein | Simulation and the Monte Carlo Method[END_REF]. output: A random weight vector w r over K p .

1 Generate p -1 independent random variables U 1 , ..., U p-1 from the standard uniform distribution U (0, 1) ;

2 Sort U 1 , ..., U p-1 into the order statistics U (1) , ..., U (p-1) ; 3 Define w r ∈ K p by:

• w r 1 = U (1) ; • w r 2 = U (2) -U (1) ; • . . . • w r p = 1 -U (p-1)
; and return the weight vector w r Algorithm 2: Generating a random vector over K p [START_REF] Rubinstein | Simulation and the Monte Carlo Method[END_REF].

After generating a large number of random vectors in K p with Algorithm 2, we compute the percentage of random weights in W ′ . We illustrate this procedure in Figure 3.19. With a sufficiently large sample size, the approximated size is a good estimate and has also the advantage of being easy to implement and adaptable to less specific weight sets. With a slight abuse of language, we will denote the approximated size of weight set W by the size of W . We illustrate the relevance of this estimator with numerical results on several supersets in Section 3.5.

Preference elicitation frameworks

Preference information can be elicited using several frameworks [START_REF] Park | Mathematical programming models for characterizing dominance and potential optimality when multicriteria alternative values and weights are simultaneously incomplete[END_REF]. The preference information can take the form of rankings [START_REF] Fishburn | Analysis of decisions with incomplete knowledge of probabilities[END_REF], ratio intervals [START_REF] Hazen | Partial information dominance and potential optimality in multiattribute theory[END_REF], bounds [START_REF] Sarin | Elicitation of subjective probabilities in the context of decision making[END_REF], holistic judgments [START_REF] Malakooti | Ranking and screening multiple criteria alternatives with partial information and use of ordinal and cardinal strength of preferences[END_REF], etc. We present some of them hereafter with results on their number of extreme weights. Most of them are based on ordinal information as the DM generally prefers to avoid precise parameter values. Some presented frameworks are then applied in Section 3.5 to illustrate particular points of the direct and two-stage procedure.

Ranking

Criteria ranking

A classic situation is when the DM cannot provide cardinal information on the weights but is able to rank the criteria by order of importance. This preference elicitation framework has been presented in [START_REF] Sarin | Elicitation of subjective probabilities in the context of decision making[END_REF], [START_REF] Kofler | Decision making with linear partial information (l.p.i.)[END_REF]. We assume, without loss of generality, that the criteria are indexed by decreasing value of importance. The associated set of weights W 1 is defined below.

W 1 = {w ∈ K p : w 1 ≥ w 2 ≥ ... ≥ w p } (3.5)
The number of extreme weights of W 1 has already been presented in [START_REF] Sarin | Elicitation of subjective probabilities in the context of decision making[END_REF], [START_REF] Kofler | Decision making with linear partial information (l.p.i.)[END_REF]. We recall the result and give a simple proof for the sake of completeness.

Proposition 3.19. The number of extreme weights of W 1 is p.

Proof. W 1 is defined by an irredundant system of p inequality constraints w p ≥ 0 and w i ≥ w i+1 , i = 1, ..., p -1 and the normalization constraint. The result follows by Proposition 3.17.

Using Proposition 3.13, it follows from Proposition 3.19 that the number of criteria is not increased. The extreme weights of W 1 are the feasible basic solutions of polytope W 1 . A basic solution is the solution of a system composed of p -1 constraints of W 1 set to equality completed by the normalization constraint. We get the extreme weights by solving these p systems. The extreme weights of W 1 are given below.

A 1 =         1 0 0 ... 0 1 2 1 2 0 ... 0 1 3 1 3 1 3 ... 0 . . . . . . . . . . . . . . . 1 p 1 p 1 p ... 1 p        

Group ranking

In this model, the DM partitions the criteria in two sets M and L that denote the set of relatively most important and relatively least important criteria, respectively. This offers an interesting preference elicitation framework for group decision making, since the decision for each criterion would be to classify it as most or least important criterion. The corresponding set of weights is defined below.

W 2 = {w ∈ K p : ∀l ∈ L, ∀m ∈ M, w m ≥ w l } (3.6)
W 2 contains W 1 if all criteria in M are ranked higher than the criteria in L in W 1 . The number of extreme weights of W 2 is given in Proposition 3.20 and their analytic expression is given in the proof. Proposition 3.20. Let n M and n L denote the number of most and least important criteria respectively. If n M ≥ 1, the number of extreme weights of W 2 is n M + 2 n L -1.

Proof. We assume in the following that criteria f i , i = 1, ..., n M and f j , j = n M + 1, ..., n M + n L are the set of most and least important criteria respectively. Let w = (w 1 , w 2 , ..., w n M , w n M +1 , w n M +2 , ..., w n M +n L ) be a weight in W 2 such that :

w n M +1 ≥ w n M +2 ≥ ... ≥ w n M +n L (3.7)
We exhibit weights of W 2 that can express every w respecting (3.7) as a convex combination.

A 2 =                    M 1 0 ... 0 0 1 ... 0 . . . . . . . . . . . . 0 0 ... 1 1 n M +1 1 n M +1 ... 1 n M +1 1 n M +2 1 n M +2 ... 1 n M +2 . . . . . . . . . . . . 1 n M +n L 1 n M +n L ... 1 n M +n L L 0 0 ... 0 0 0 ... 0 . . . . . . . . . . . . 0 0 ... 0 1 n M +1 0 ... 0 1 n M +2 1 n M +2 ... 0 . . . . . . . . . . . . 1 n M +n L 1 n M +n L ... 1 n M +n L                    We express λ such that λ.A 2 = w. λ = w 1 -w n M +1 ,...,wn M -w n M +1 , M (n M +1)(w n M +1 -w n M +2 ),(n M +2)(w n M +2 -w n M +3 ),...,(n M +n L )(w n M +n L ) L
Since w is in W 2 and w respects equation (3.7), λ ≥ 0 and p i=1 λ i = 1. Therefore weights of A 2 are sufficient to express all weights w respecting equation (3.7) as a convex combination. However we focused on a specific case of w, therefore we must take into account all possible orders of weights in L to compute the set of sufficient extreme weights. Although there are n L ! possible orders, some extreme weights will be computed for several ones. For example, the same extreme weight will be computed for all orders having w n M +1 as the largest value. The same extreme weight will be computed for all orders having w n M +1 and w n M +2 as the two largest values, etc. Thus, we list all possibilities hereafter:

• There are one out of n L possibilities, n L 1 , for the index i in L with the largest value w i . Thus, there must be n L 1 extreme weights to express every possibility;

• There are two out of n L possibilities, n L 2 , for the indices i, j in L with the two largest values w i , w j . Thus, there must be n L 2 extreme weights to express every possibility;

• . . .

• There is one possibility, n L n L , for the indices with the n L largest values. Thus, there is

n L n L = 1 possible extreme weight.
The first n M extreme weights of A 2 do not depend on w. Thus, there are

n M + L i=1 n L i =
n M + 2 n L -1 weights to express every weight w in W 2 (Binomial Theorem). We showed above that the weights are sufficient. Each weight is also necessary since it cannot be expressed as a convex combination of other weights and is thus an extreme weight of W 2 . All extreme weights of W 2 are expressed in A 2 below.

A 2 =                                    M 1 0 ... 0 0 1 ... 0 . . . . . . . . . . . . 0 0 ... 1 1 n M +1 1 n M +1 ... 1 n M +1 1 n M +1 1 n M +1 ... 1 n M +1 . . . . . . . . . . . . 1 n M +1 1 n M +1 ... 1 n M +1 1 n M +2 1 n M +2 ... 1 n M +2 1 n M +2 1 n M +2
...

1 n M +n L 1 n M +n L ... ...
The first observation is that the number of extreme weights increases exponentially with the number of criteria n L . In the case where there is one criterion in L, the number of extreme weights is equal to p. We introduce an example for the superset construction method based on removing constraints in the case where p = 4 and n M = n L = 2.

Example 3.4. Assume that criteria f 1 , f 2 and f 3 , f 4 are identified as the most and least important ones, respectively. The corresponding weight set W 2 in K 4 is defined as follows:

W 2 =                            w 3 ≤ w 1 (1 ) w 4 ≤ w 1 (2 ) w 3 ≤ w 2 (3 ) w 4 ≤ w 2 (4 ) 0 ≤ w 3 (5 ) 0 ≤ w 4 (6 ) 4 i=1 w i = 1 (7 )

PREFERENCE ELICITATION FRAMEWORKS

69

W 2 is defined by 6 inequality constraints and, by Proposition 3.20, we know that W 2 has 5 extreme weights. Therefore using the two-stage procedure could improve the computation time of the corresponding R W -nondominated set.

By using the method presented in Section 3.3.2 based on removing constraints, we compute 4 available supersets with 4 extreme weights. We only examine two of these since the others are "symmetric", meaning that they can be constructed by a permutation on the weights w 3 and w 4 . The two different supersets are:

W a 2 =                  w 3 ≤ w 1 (1 ) w 4 ≤ w 2 (4 ) 0 ≤ w 3 (5 ) 0 ≤ w 4 (6 ) 4 i=1 w i = 1 (7 ) (3.8) , W b 2 =                  w 3 ≤ w 1 (1 ) w 3 ≤ w 2 (3 ) 0 ≤ w 3 (5 ) 0 ≤ w 4 (6 ) 4 i=1 w i = 1 (7 ) (3.9)
Each superset has p = 4 extreme weights by Proposition 3.17. There are two possibilities for the two-stage procedure. In order to assess the size of each superset, we used the algorithm proposed in [START_REF] Rubinstein | Simulation and the Monte Carlo Method[END_REF] and draw a sample of 5.0 × 10 6 random weights in K 4 (see Table 3.2).

Weight set

The size of W b

2 is larger than the size of W a 2 and we might suppose that using W a 2 in a two-stage procedure will give better results. Experimental results, given in Section 3.5, confirm this assumption.

When p = 3 and n M = 1, the weight set has 4 extreme weights. We introduce an example, in this case, of the superset construction method based on creating constraints.

Example 3.5. Assume that criteria f 1 and f 2 , f 3 are identified as the most and least important ones respectively. The corresponding weight set W 2 in K 3 is defined as follows:

W 2 =                  w 1 ≥ w 2 w 1 ≥ w 3 w 2 ≥ 0 w 3 ≥ 0 3 i=1 w i = 1
By Proposition 3.20, we know that W 2 has 4 extreme weights. We give the extreme weights of W 2 hereafter (see the proof of Proposition 3.20).

A 2 =      1 0 0 1 2 1 2 0 1 2 0 1 2 1 3 1 3 1 3     
(3.10) Therefore using the two-stage procedure could improve the computation time of the corresponding R W -nondominated set. We observe by looking at the extreme weights of W 2 (3.10), that the lower bounds of w 1 , w 2 , w 3 are 1 3 , 0, 0, respectively. By using the superset construction method based on creating constraints (Section 3.3.2), we obtain one candidate superset, denoted by W c 2 .

W c 2 =              w 1 ≥ 1 3 w 2 ≥ 0 w 3 ≥ 0 3 i=1 w i = 1 (3.11)
By using the superset construction method based on removing constraints (Section 3.3.2), we obtain one candidate superset, denoted by W d 2 .

W d 2 =              w 1 ≥ w 2 w 2 ≥ 0 w 3 ≥ 0 3 i=1 w i = 1 (3.12)
In order to assess the size of each superset, we draw a sample of 5.0 × 10 6 random weights in K 3 (see Table 3.3). The size of W d 2 is larger than the size of W c 2 and we might suppose

Weight set Size (%) W c 2 44.44 W d 2 49.96 K 3 100.00
Table 3.3: Approximate size of supersets W c 2 , W d 2 when p = 3 and M = 1, compared to the size of K 3 . that using W c 2 in a two-stage procedure will give better results. Experimental results, given in Section 3.5, confirm this assumption.

A natural extension of the previous framework is to use more than two groups. Each group is a subset of criteria that are not comparable and all groups are ranked by order of importance. We assume without loss of generality that the groups of criteria G i are indexed by decreasing value of importance. All criteria in G 1 have a higher weight than criteria in G 2 etc. Thus W 2 is defined as follows:

W 2 = {w ∈ K p : ∀k ∈ G i , ∀k ′ ∈ G j , with i < j, w k ≥ w k ′ } (3.13)
The number of extreme weights is expressed in Proposition 3.21 and their analytic expression is given in the proof.

Proposition 3.21. Let n G and n i denote the number of groups and the number of criteria in group i respectively. If there are at least two groups, the number of extreme weights for

W ′ 2 is n 1 + n G i=2 2 n i -(n G -1).
Proof. The proof is similar to the proof of Proposition 3.20. Only the number of possible combinations changes for a group k: The necessary and sufficient number of extreme weights to take into account all possible orders of weights in

G k , k = 2, ..., n G , is n k j=1 n k j = 2 n k -1. The number of extreme weights for G 1 is still n 1 . Therefore there are n 1 + n G i=2 n i j=1 n i j = n 1 + n G i=2 2 n i -(n G -1) extreme weights (Binomial Theorem).
Similarly to proof of Proposition 3.20, the weights are sufficient but also necessary and are thus the extreme weights of the weight set. For the sake of clarity, we provide the analytic expression of the extreme weights hereafter. We only express the non-zero columns of the extreme weights. First, we give the analytic expression of the extreme weights having non-zero coordinates only for objectives in G 1 and G 2 . Then, we give the analytic expression

      G 1 1 0 ... 0 0 1 ... 0 . . . . . . . . . . . . 0 0 ... 1 1 n 1 +1 1 n 1 +1 ... 1 n 1 +1 1 n 1 +1 1 n 1 +1 ... 1 n 1 +1 . . . . . . . . . . . . 1 n 1 +1 1 n 1 +1 ... 1 n 1 +1 1 n 1 +2 1 n 1 +2 ... 1 n 1 +2 1 n 1 +2 1 n 1 +2 ... 1 n 1 +2 . . . . . . . . . . . . 1 n 1 +2 1 n 1 +2 ... 1 n 1 +2 . . . . . . . . . . . . 1 n 1 +n 2 1 n 1 +n 2 ... 1 n 1 +n 2 G 2 0 .
1 n 1 +1 1 n 1 +2 1 n 1 +2 0 ... 0 1 n 1 +2 0 1 n 1 +2 ... 0 . . . . . . . . . . . . . . . 0 0 0 ... 1 n 1 +2 . . . . . . . . . . . . . . . 1 n 1 +n 2 1 n 1 +n 2 ... ...       G 1 ...G j-1 1 j-1 i=1 n i +1 1 j-1 i=1 n i +1 ... 1 j-1 i=1 n i +1 1 j-1 i=1 n i +1 1 j-1 i=1 n i +1 ... 1 j-1 i=1 n i +1 . . . . . . . . . . . . 1 j-1 i=1 n i +1 1 j-1 i=1 n i +1
...

1 j-1 i=1 n i +1 1 j-1 i=1 n i +2 1 j-1 i=1 n i +2
...

1 j-1 i=1 n i +2 1 j-1 i=1 n i +2 1 j-1 i=1 n i +2
...

1 j-1 i=1 n i +2 . . . . . . . . . . . . 1 j-1 i=1 n i +2 1 j-1 i=1 n i +2
...

1 j-1 i=1 n i +2 . . . . . . . . . . . . 1 j i=1 n i 1 j i=1 n i ... 1 j i=1 n i G j 1 j-1 i=1 n i +1 0 ... ... 0 0 1 j-1 i=1 n i +1 ... ... 0 . . . . . . . . . . . . . . . 0 0 ... ... 1 j-1 i=1 n i +1 1 j-1 i=1 n i +2 1 j-1 i=1 n i +2 0 ... 0 1 j-1 i=1 n i +2 0 1 j-1 i=1 n i +2 ... 0 . . . . . . . . . . . . . . . 0 0 0 ... 1 j-1 i=1 n i +2 . . . . . . . . . . . . . . . 1 j i=1 n i 1 j i=1 n i ... ...

Bounds

This framework is the one used in Example 3.1. The DM is able to provide a lower and/or an upper bound, l i and u i respectively, for the weight assigned to a criterion f i , i = 1, ..., p. The associated set of weights W B is defined below.

W B = {w ∈ K p : ∀i, 1 ≤ i ≤ p, l i ≤ w i ≤ u i } (3.14)
In order for W B not to be empty or reduced to a singleton, there are two conditions on the parameters:

p i=1 l i < 1 and p i=1 u i > 1.
The maximum number of extreme weights of the set W B may be very large. In order to apply a two-stage procedure, we consider two possible supersets W l B , W u B which have both p extreme weights. The supersets only impose lower and upper bounds respectively. The choice of the most promising superset will be made regarding their respective size. We consider W l B , superset of W B and defined by lower bounds on weights.

W l B = {w ∈ K p : ∀i, 1 ≤ i ≤ p, l i ≤ w i } (3.15)
Corollary 3.22. The number of extreme weights of W l B is p. Proof. From Proposition 3.18.

The extreme weights of W l B are the feasible basic solutions of polytope W l B . A basic solution is the solution of a system composed of p -1 constraints of W l B set to equality completed by the normalization constraint. We get the extreme weights by solving these p systems. The extreme weights of W l B are given below.

A B,l =               1 - p j=2 l j l 2 ... l p l 1 1 - p j=1 j =2 l j ... l p . . . . . . . . . . . . l 1 l 2 ... 1 - p-1 j=1 l j              
We also consider W u B , superset of W B and defined by upper bounds on the weights.

W u B = {w ∈ K p : ∀i, 1 ≤ i ≤ p, w i ≤ u i } (3.16)
Proposition 3.23. Assuming that p j=1 j =i u j ≤ 1, i = 1, ..., p, the number of extreme weights of

W u B is p.
Proof. For any weight w ∈ W u B , we have, for i = 1, ..., p, w i = 1 -

p j=1 j =i w j ≥ 1 - p j=1 j =i u j ≥ 0.
Therefore, W u B is defined by an irredundant system of p inequality constraints w i ≤ u i , i = 1, ..., p, and the normalization constraint. The result follows by Proposition 3.17.

The extreme weights of W u B are the basic solutions of polytope W u B . A basic solution is the solution of a system composed of p -1 constraints of W u B set to equality completed by the normalization constraint. We get the extreme weights by solving these p systems. The extreme weights of W u B are given below.

A B,u =               1 - p j=2 u j u 2 ... u p u 1 1 - p j=1 j =2 u j ... u p . . . . . . . . . . . . u 1 u 2 ... 1 - p-1 j=1 u j              
A specific case is the following framework where each criterion weight is guaranteed to be close to a reference weight w ref according to a parameter 0 < α < 1.

W ref B = {w ∈ K p : ∀i, 1 ≤ i ≤ p, w ref i (1 -α) ≤ w i ≤ w ref i (1 + α)} (3.17)
The reference weight w ref determines the relative importance of each objective, while the parameter α controls the desired diversification of the corresponding R W -nondominated set around this reference weight.

We propose to study the case where the DM is interested in balanced points with

w ref = ( 1 p , ..., 1 p ). W 3 = {w ∈ K p : ∀i, 1 ≤ i ≤ p, 1 p (1 -α) ≤ w i ≤ 1 p (1 + α)} (3.18)
We illustrate the variation of the corresponding R W -nondominated set with different values of α in Section 3.5. The number of extreme weights of W 3 is given in Proposition 3.24 and their analytic expression is given in the proof.

Proposition 3.24. The number of extreme weights of W 3 is:

• p p 2
, when p is even;

• p p-1 2 × p+1 2 , when p is odd.
Proof. W 3 is defined by an irredundant constraint system of 2p inequalities and the normalization constraint. Every extreme weight is a feasible basic solution of polytope W 3 . A basic solution of W 3 is the solution of a system composed of p -1 constraints of W 3 set to equality completed by the implicit equality of W 3 . There are two inequalities for each w i , i = 1, ..., p and only one can be set to equality if α > 0. Either the constraint for the lower bound l = (1α) 1 p or the constraint for the upper bound u = (1 + α) 1 p can be active. Let n l and n u be the number of weights w i equal to l and u respectively, therefore n l + n u = p -1. Suppose that n un l ≥ 0. We assume that the coordinate that is not determined by any equality yet is w j , j = 1, ..., p. Then,

w j = 1 - p i=1 i =j w i = 1 -[n l (1 -α) 1 p + n u (1 + α) 1 p ] = 1 -1 p [n u + n l + (n u -n l )α] = 1 -1 p [p -1 + (n u -n l )α]
Three cases are possible:

n u > n l + 1. Then w j < (1 -α) 1
p and the corresponding weight w, which is a basic solution of W 3 , is not feasible.

n u = n l + 1. Then w j = (1-α) 1 p . Since p-1 = 2n l +1, p-1 is odd and p is even. Furthermore, n u + n l = p -1 implies that n u = p 2 .
The basic solutions have p 2 coordinates equal to u and p 2 coordinates equal to l and are thus feasible. Therefore when p is even, there are p

p 2 × p 2 p 2 = p p 2
feasible basic solutions.

n u = n l . Then w j = 1 p . Since p -1 = 2n u , p -1 is even and p is odd. Furthermore, n u = n l = p-1
2 . The basic solutions have p-1 2 coordinates equal to u, p-1 2 , the last coordinate w j equal to 1 p and are thus feasible. Therefore when p is odd, there are

p p-1 2 × p+1 2 p-1 2 = p p-1 2
× p+1 2 feasible basic solutions.

When n ln u > 0, the proof is similar and computes the same basic feasible solutions. All basic feasible solutions of W 3 are extreme weights of W 3 , hence the number of extreme weights of W 3 is:

• p p 2
, when p is even;

• p p-1 2 × p+1
2 , when p is odd.

We give herafter the analytic expression of the extreme weights.

• when p is even, the extreme weights are all permutations of the following vector:

( p 2 (1-α) 1 p (1-α) 1 p ... (1-α) 1 p (1-α) 1 p p 2 (1+α) 1 p (1+α) 1 p ... (1+α) 1 p (1+α) 1 p )
• when p is odd, the extreme weights are all permutations of the following vector:

( p-1 2 (1-α) 1 p (1-α) 1 p ... (1-α) 1 p (1-α) 1 p 1 p p-1 2 (1+α) 1 p (1+α) 1 p ... (1+α) 1 p (1+α) 1 p )
Set W 3 defined by (3.18) has 6, 6 and 30 extreme weights for p = 3, 4, 5 respectively. Therefore we used the two-stage procedure in certain cases to compute the set N (Y, R W 3 ) in the numerical experiments. We proposed two supersets W l B , W u B for weight set W B (3.14). We introduce the following corollary of Proposition 3.22 for weight set W l 3 .

W l 3 = {w ∈ K p : ∀i, 1 ≤ i ≤ p, 1 p (1 -α) ≤ w i } (3.19)
Corollary 3.25. The number of extreme weights of W l 3 is p.

Proof. Since α > 0, we have

p i=1 l i = 1 -α < 1. From Corollary 3.22, W l 3 has p extreme weights.
We also introduce the following corollary of Corollary 3.23 for weight set W u 3 .

W u 3 = {w ∈ K p : ∀i, 1 ≤ i ≤ p, w i ≤ 1 p (1 + α)} (3.20)
Corollary 3.26. Assuming that α ≤1 p-1 , the number of extreme weights of W u 3 is p.

Proof. Since α > 0, we have

p i=1 u i = 1 + α > 1. Furthermore if α ≤ 1 p-1 , then p j=1 j =i u j = p-1 p (1 + α) ≤ 1, i = 1, ..., p.
From Proposition 3.23, W u 3 has p extreme weights. Since we used two parameter values α = 10% and α = 20% and p = 3, 4, 5 in our numerical experiments, from Corollary 3.25 and Corollary 3.26, both supersets W l 3 (3.19) and W u 3 (3.20) have p extreme weights. Consequently they are interesting candidates for a two-stage procedure with these parameter values. However they have the same size and we cannot a priori prefer one to the other. We illustrate their performances in a two-stage procedure in Section 3.5.3.

Numerical experiments

We performed our experiments using the generic algorithm presented in [START_REF] Kirlik | A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems[END_REF]. This algorithm generates all nondominated points for multi-objective discrete optimization problems. We used the code provided by the authors 1 . We have generated our results on two MOCO problems: the Multi-Objective Knapsack Problem (MOKP) and the Multi-Objective Assignment Problem (MOAP) presented in Section 1.1.6. The parameters used to generate instances of MOKP and MOAP are described as follows:

• We tested on uncorrelated instances of MOKP and weights and profits of items are random integers uniformly drawn in the interval [1, 1000]. Let ω i , i = 1, ..., n, denote the weights of the items, the weight capacity of the knapsack is set to

n i=1 ω i 2 .
• The objective costs of MOAP instances are random integers uniformly drawn in the interval [1,20].

For MOKP we used the following instance sizes:

• p = 3 and n = 100 (3-MOKP100),

• p = 4 and n = 40 (4-MOKP40),

• p = 5 and n = 30 (5-MOKP30).

For MOAP we used the following instance sizes:

• p = 3 and n = 50 (3-MOAP50),

• p = 4 and n = 30 (4-MOAP30).

We also use several preference elicitation frameworks:

• No information on weights. This framework is equivalent to use K p as weight set and to compute the Pareto nondominated set (Corollary 3.5). It is therefore denoted by Pareto in the different tables;

• The group ranking framework with two criteria groups M and L is denoted by Group ranking (M = i) where i is the number of criteria in group M . The superset of a twostage procedure is denoted by Group ranking (M = i) superset. • The criteria ranking framework is denoted by Criteria ranking;

• The bounds framework is denoted by Bounds-α%, where α is the parameter used in (3.18). We use both supersets W l 3 , W u 3 presented in Section 3.4.2 that are denoted by LowerBounds-α% and UpperBounds-α% respectively.

A computer with a Linux Debian operating system, 3.7 GHz processor and a 32 GB memory limit has been used for the experiments. CPLEX 12.5.1 is the solver provided for the algorithm. We used 10 instances for each problem size to compute our results. Several observations are made regarding quantitative information -computation time denoted by CPU time and number of preferred points denoted by |N (Y, R W )|-and qualitative information -consistency of the weight sets and percentage of supported and nonsupported points, resp. denoted by %N S (Y, R W ) and %N N S (Y, R W ). For the sake of clarity we split the results in several parts.

Approximated size of weight sets

We computed the approximated size of weight sets for p = 3, 4, 5. We used Algorithm 2 to draw 5.0 × 10 6 random weights in K p .

We first observe that Bounds-20% and Bounds-10% have smaller weight sets than the other frameworks. Therefore, the computation time and size of the corresponding R W -nondominated sets should also be smaller. Similarly, the supersets Group ranking (M=1) superset c and Group ranking (M=1) superset d do not have the same size and the former should have a better computation time than the latter. set has p extreme weights, the computation time of the most restricted set is lower than the least restricted one since there are fewer points to compute. More generally the weight sets having lower sizes tend to have lower computation time and number of R W -nondominated points. For example, Criteria ranking weight set has a larger size than Bounds-10% weight set. For every problem type and size, Bounds-10% has a lower CPU time even if there is no inclusion between the weight sets.

Since the computation time is reduced, we computed the R W -nondominated set for 5-MOKP30 and 4-MOAP30. These problem sizes cannot be addressed in reasonable time when generating the standard Pareto nondominated set. We chose to apply the most restrictive models (Criteria ranking, Bounds-20%, Bounds-10%). The computation times remain competitive while the optimization is still multi-objective. However in large instances, not every elicitation framework can be used. Indeed, Group ranking(M = 3) has a poor computation time in 4-MOAP30 instances.

Performance of the two-stage procedure

Difference with the direct procedure Tables 3.8 and 3.9 show that the two-stage procedure reduces the running time in most cases. We give for each instance type and weight set, the computation time and size of R Wnondominated sets of the different approaches in the following order: the direct procedure that directly considers the full set of weights constructed by the DM, the two-stage procedure and the first stage of the two-stage procedure.

With Bounds-α%, two supersets could be used to compute these results, LowerBounds-α% and UpperBounds-α%. The size of each weight set is equal. We report results when using LowerBounds-α% in this section, because contrary to UpperBounds-α%, there is no required condition on the parameters. The comparison between these possible supersets is made in Section 3.5.3.

When p = 3, the number of extreme weights is 6 for both values of α. For every instance type, the direct approach, that directly computes the R W -nondominated set, has a larger CPU time than the two-stage procedure with LowerBounds-α%. Although the number of R Wnondominated points is small, the computation time is important due to the optimization in a 6-dimensional space while LowerBounds-α% only has p = 3 extreme weights (Corollary 3.25). The above observations do not hold when p = 4. The number of extreme weights is still 6, therefore the difference between the two possible dimensions for the optimization is smaller than when p = 3. The direct approach has a poor computation time in 4-MOAP30 instances when α = 20%. For the other cases, the performances are similar. In 4-MOAP30 instances with Bounds-10%, the direct approach even shows a two times faster computation time than the two-stage procedure. This may come from the low number of R W -nondominated points and the ratio (≈ 4) on the size between the R W -nondominated set (8.3) and the superset (33.4). For the same instances, Bounds-20% leads to different results. The ratio on the size between the R W -nondominated set and the superset is still important (≈ 3), but the two-stage procedure is approximately 18 times faster. We observe that cases where the two-stage procedure is slower arise in instances with low computation time and the magnitude of performance remains similar. Finally, when p = 5, we could not perform the direct approach on 5-MOKP instances since the corresponding weight set has 30 extreme weights and would imply an optimization in a 30-dimensional space. Therefore, the two-stage procedure is the only method that is able to compute the corresponding R W -nondominated set when p = 5. Remark 3.27. There are 2 and 1 instances in 3-MOAP50 and 4-MOAP30 instances respectively where Bounds-20% could not be solved with the direct approach with this generic algorithm due to a large required memory size. We did not take them into account to compute the average performance of the direct approach, contrary to the average two-stage procedure performance. Indeed, the two-stage procedure is able to compute the corresponding R W -nondominated set in each instance. The average performance remains competitive. This underlines the fact that the two-stage procedure is also interesting in cases where the direct approach cannot be performed.

In light of the above observations and Remark 3.27, the two-stage procedure should always be preferred to the direct approach.

In the following we compare the two-stage approach with the Group ranking framework. Two supersets could be used when p = 4 and M = 2 (Example 3.4). We chose to use the smallest weight set, W a 2 , to perform the two-stage procedure. When p = 5, the required memory size for the algorithm is too large in 5-MOKP30 instances for Group ranking for both the direct approach and the two-stage procedure, therefore we could not compare them on these instances. For all instance types, the two-stage procedure has a significantly lower computation time. The number of extreme weights is only p + 1 in each case but since the R W -nondominated sets are large, the increased dimension has a more important impact on computation time. This confirms the trend that the two-stage procedure is always interesting when the size of the R W -nondominated set is important. We also observe in 3-MOAP50 instances that the two-stage procedure suffers from a large number of points in both the first and second stage. This justifies the need of a priori assessing the performance of supersets.

3-MOKP100

Remark 3.28. Observe that the duration of the second stage of the two-stage procedure is often small in Table 3.8 (≈ 0.01s). This is due to the small number of points at the end of the first stage in most instances. When the superset of the R W -nondominated set is relatively large (see, e.g., Table 3.9), the duration of the second stage increases significantly (e.g. 186.70s on average for 3-MOAP50).

Difference between supersets

We discuss here the difference of performance when different supersets are used for the first stage of the two-stage procedure. This analysis is based on two elicitation frameworks:

• Bounds-α%. This case involves two supersets of equal size, LowerBounds-α% and UpperBounds-α%;

• Group ranking with M = 1 and p = 3 and M = 2 and p = 4. These cases each involve two supersets with different size, superset c and superset d for M = 1 and p = 3 and superset a and superset b for M = 2 and p = 4. The sizes of superset b and superset d are larger than the sizes of superset a and superset c , respectively.

In Table 3.10, the computation time and size of R W -nondominated sets are mostly similar between LowerBounds-α% and UpperBounds-α% for both values of α. There are three cases where there is an important difference. In 5-MOKP instances, one instance is particularly hard and UpperBounds-20% is three times worse than LowerBounds-20%. UpperBounds-20% and LowerBounds-20% have lower computation time in 3-MOAP50 and 4-MOAP30 instances respectively. These notable differences could depend on the parameters of the instances. The similar size of the weight sets only indicates that the performances will be similar in most cases. However differences of performance arise in instances with a large number of R W -nondominated points, therefore the case where α = 20% is more subject to these variations. This observation could imply that the more the size of the weight sets is small, the more their performances are likely to be similar.

The following experiments involve two supersets of different size for Group ranking (M = 1) and Group ranking (M = 2). The size of each superset is reminded hereafter.

In Table 3.11, we see that the CPU time and the number of R W -nondominated points are more important with the weight set with the largest size (superset b and superset d ). The variation of the size also indicates the order of magnitude between two supersets. Indeed, the difference of size between superset a and superset b is larger than between superset c and superset d and the corresponding computation time and number of R W -nondominated points vary accordingly. When there is a significant difference on the size of the weight sets, even though the number of R W -nondominated points is data dependent, the size of a weight set is an interesting indicator of the future performance of the two-stage procedure.

Evaluation of the preferred sets

In order to provide an evaluation of the returned preferred sets, we assess their consistency with the weight set (Section 3.5.4) and compute the proportion of nonsupported points (Section 3.5.4).

3-MOKP100

Consistency of the weight set

To evaluate the consistency of a returned R W -nondominated set with the corresponding weight set, we take as indicators the minimum and maximum values on each objective over this set. Remark 3.29. We did not give results for 5-MOKP30 and 4-MOAP30 instances, since the nondominated set cannot be computed with the generic algorithm [START_REF] Kirlik | A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems[END_REF].

3-MOKP100

Conclusions and perspectives

In this chapter, we presented a preference relation based on the weighted sum aggregation and a set of possible weights defined by partial preference information. We showed noteworthy properties in the general case. In the specific case where the weight set is a polytope, we proposed a generic way to use this preference relation with an a priori approach in multi-objective optimization problems. We also introduced a two-stage procedure in order to efficiently compute the corresponding nondominated set. Several preference elicitation frameworks are discussed with some results on their number of extreme weights and instanciated on MOCO problems. They show competitive results both in terms of quantitative information (CPU time and number of preferred points) and qualitative information (percentage of supported and nonsupported points). This shows the efficiency of integrating a priori preference information in multi-objective optimization algorithms. The two-stage procedure is tested on several instance types. The experimental results are promising in most cases and show that our approach with the two-stage procedure should always be preferred. Nevertheless this suggests several directions for future work. Determining the most appropriate supersets for the two-stage procedure should be investigated. Furthermore, additional preference elicitation frameworks or enumer-

Motivations

The ordered weighted averaging (OWA) operator, introduced by [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF], is a parametrized scalarizing function, whose parameters are weights associated to the smallest criterion value, the second smallest criterion value, etc. Due to the reordering step needed to apply this operator, OWA is nonlinear. It provides a class of parametrized operators that includes the min, max, median and average operator. This operator has been applied to various field such as portfolio selection [START_REF] Ogryczak | On efficient WOWA optimization for decision support under risk[END_REF], bandwith allocation [START_REF] Ogryczak | A multi-criteria approach to fair and efficient bandwidth allocation[END_REF], location problems [START_REF] Nickel | Location theory: a unified approach[END_REF], data mining [START_REF] Torra | OWA operators in data modeling and reidentification[END_REF], etc. With different weights, an OWA operator can represent several attitudes of the DM towards risk, equitability, etc., depending on the context of the decision making process. [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF] proposes to measure the attitudinal character of the DM, also called "orness" measure, to establish how "orlike" an OWA operator is. The result of an "or" operator is low if at least one value is low, while on the opposite the result of an "and" operator is low if all values are low. The pure "or" and "and" operator are the minimum and the maximum, respectively. The most common method is to determine the weights under a given level of orness. The desired level of orness is formulated with a constraint on the weights and different criteria can be optimized to obtain a weight vector (see [START_REF] Liu | A review of the OWA determination methods: Classification and some extensions[END_REF] for a detailed literature review). A first criterion consists in maximizing the entropy under a given level of orness [START_REF] Filev | Analytic properties of maximum entropy OWA operators[END_REF]. There are other criteria such as the minimum variance [START_REF] Fullér | On obtaining minimal variability OWA operator weights[END_REF], the minimum distance to the vector of maximal entropy [START_REF] Wu | A linear programming model for determining ordered weighted averaging operator weights with maximal Yager's entropy[END_REF] or the minimax disparity criterion [START_REF] Wang | A minimax disparity approach for obtaining OWA operator weights[END_REF]. There also exist different techniques based on machine learning to determine weights for an OWA operator [START_REF] Filev | On the issue of obtaining OWA operator weights[END_REF][START_REF] Beliakov | How to build aggregation operators from data[END_REF][START_REF] Beliakov | Learning weights in the generalized OWA operators[END_REF]. These numerous methods are not easy to understand for the DM and choosing among them does not facilitate the decision making process.

More recently, similarly to the weighted sum, the OWA operator with partial information on weights has also been studied. An operator called uncertain OWA introduced by [START_REF] Xu | The ordered weighted geometric averaging operators[END_REF] considers range or domain for both weights and alternative values in order to represent uncertainty on the values, and use a technique called interval numbers. An interval number is a k-tuple, that contains the minimum and maximum value and possibly a subinterval with the highest probability. [START_REF] Ahn | The OWA aggregation with uncertain descriptions on weights and input arguments[END_REF] defines a pairwise dominance rule where a solution is preferred to another one if its OWA value is better for every possible weight in the weight set. The author focuses primarily on weights being constrained by lower and upper bounds. A mathematical program is formulated to check for pairwise dominance. However this program is nonlinear when the alternatives are not known. Similarly Yager and Alajlan (2014) study imprecise parameters for the Choquet integral. After eliciting the set of parameters according to the preference of the DM, they determine for each alternative the interval of its Choquet integral value on this set. After this step, each alternative is represented by an interval and they present techniques to select one alternative based on this representation. [START_REF] Ahn | Parameterized OWA operator weights: an extreme point approach[END_REF] studies the extreme weights of a set constructed with an uncertain attitudinal character. However the extreme weights are not used for the pairwise comparison.

Our approach consists in generating the nondominated set of an implicit set of points with respect to the following partial preference relation. After determining a set of possible weights representing the DM's preferences, a solution is preferred to another one if its OWA value is better for every possible weight in the weight set. Typically the set of weights is determined by constraints reflecting ordinal information on the weights (e.g. ranking of the weights by order of importance). Preference elicitation is much less demanding than when requiring precise values. Choosing this preference relation based on OWA with imprecise weights rather than the preference relation based on the weighted sum with imprecise weights depends on the preference information given by the DM and the context of the optimization. Either the DM wants to consider objectives anonymously or the DM does not. In the former case, the DM gives information on the worst objective, second worst, etc., while in the latter case, the DM is able to give information on specific objectives. Compared with the Pareto nondominated set, we generate a substantially smaller set of potentially interesting solutions for the DM with a great computational time saving. We especially focus on MOCO problems although the presented concepts are more general. After studying some properties of this preference relation, we present an approach based on the previous work on the weighted sum in Chapter 3 to deal with an arbitrary weight polytope constructed from the DM's preferences. Numerical experiments illustrate the practical applicability of our approach.

Presentation of the preference relation

As well as for other aggregation functions, obtaining precise weights for the OWA operator is burdensome for the DM. Although there exist several OWA weights determination methods in the literature (see, e.g., [START_REF] Liu | A review of the OWA determination methods: Classification and some extensions[END_REF] for a literature review), the involved frameworks can be complex. Assuming that precise weights could be defined, using an OWA usually leads to a single point, while DMs are often willing to be presented with a few alternatives of interest in order to make their choice. Furthermore, similarly to the weighted sum with nonsupported points, there exist nondominated points that cannot be optimal for any OWA. These points are characterized in Section 4.2.2. In order to circumvent this drawback, instead of using one single weight, we use partial preference information to define a set of possible weights. Similarly to [START_REF] Xu | The ordered weighted geometric averaging operators[END_REF] or [START_REF] Ahn | The OWA aggregation with uncertain descriptions on weights and input arguments[END_REF], we define the following binary preference relation. W y ′ if and only if for all w in W , OW A w (y) ≤ OW A w (y ′ ) and there exists w ′ in W such that OW A w (y) < OW A w (y ′ ).

In Example 4.1, we illustrate a case with p = 2 where the DM expresses his/her preferences as neither "pessimistic" nor "optimistic" by selecting an orness of 0.5. OWA is not able to propose all solutions offering an interesting compromise.

Example 4.1. We consider a situation where 5 alternatives, evaluated on a scale [0, 20], are presented to the DM. Each of these are represented in a bi-objective space by their respective points as depicted in Figure 4.1.

By choosing orness(w) = 0.5, that is w = (0.5, 0.5), OWA outputs y 3 as the most preferred alternative. Clearly y 2 and y 5 are also interesting alternatives and should be proposed to the DM. Assume now that we choose orness(w) = 0.4 and orness(w) = 0.6, OWA outputs y 2 and y 3 as most preferred alternative respectively (Figure 4.1). Assume now that we model the neither optimistic nor pessimistic attitude of the DM by defining the following set of weights.

W = {w ∈ R 2 : 0.4 ≤ orness(w) ≤ 0.6, w 1 + w 2 = 1} (4.1)
orness(w) = 0.4 orness(w) = 0.5 orness(w) = 0.6 A solution y is preferred to another solution y ′ if the OWA value of y is better than the OWA value of y ′ for all weights in W , with at least one strict inequality.

+ + + + + f 1 f 2 y 1 (
OWA w (y 1 ) OWA w (y 2 ) OWA w (y 3 ) OWA w (y 4 ) OWA w (y 5 ) OWA w (y 1 )

OWA w (y 2 ) OWA w (y 3 ) OWA w (y 4 ) OWA w (y 5 ) • • • • • • • • • • w 1 OWA w (y i ) 0.4 0.6 | |
(a) Value of OW A w (y i ) with w 1 between 0.4 and 0.6.

OWA w (y 1 )

OWA w (y 2 ) OWA w (y 3 ) OWA w (y 4 )

OWA w (y 5 )

OWA w (y 1 )

OWA w (y 2 )

OWA w (y 3 ) OWA w (y 4 )

OWA w (y 5 )

• • • • • • • • • • • • • • • • • • • • w 1 OWA w (y i ) 0.4 0.6 1 | | | (b) Value of OW A w (y i )
with w 1 between 0 and 1. Figure 4.2a shows the value of OWA for each point for all w in W . From this representation, we see that y 1 , which is a nondominated point, is worse than y 2 for all weights w in W .

CHAPTER 4. OWA MODEL WITH PARTIAL INFORMATION

Therefore y 1 is R O W -dominated by y 2 . However neither y 2 nor y 3 is better than y 5 for all weights w in W . Figure 4.2b shows the value of the OWA for each point for all possible weights w. Alternative y 5 , which is nondominated even after reordering the criterion values, cannot be obtained by any OWA operator. Either y 2 or y 3 is optimal depending on the chosen weight. We also observe that y 4 , which is a dominated point, is worse than y 2 for all possible weights. The R O W -nondominated sets are listed below in Table 4.1 depending on the chosen weights or subset of weights.

Information on weights Nondominated sets w = (0.5, 0.5)

{y 3 } w = (0.4, 0.6) {y 3 } w = (0.6, 0.4) {y 2 } w ∈ W
{y 2 , y 3 , y 5 } Table 4.1: Nondominated points of Example 4.1 depending on the chosen weights or subset of weights.

General case

In the absence of any information, the maximal set of weights is R p ≥ , since choosing a weight vector outside the positive orthant would yield dominated points. Moreover, w.l.o.g., we restrict the maximal set to the standard simplex K p :

K p = {w ∈ R p ≥ : p i=1 w i = 1}, (4.2)
The equality constraint p i=1 w i = 1 will be referred to as the normalization constraint.

Any weight set W is a subset of K p . An illustration of K p and W is given in the threedimensional case in Figures 4.3a and 4.3b respectively. We study the link between the OWA operator and dominated points. Standard OWA with weights in K p only guarantee to yield weakly nondominated points. A weakly nondominated point can be dominated by another point but has the same value on at least one criterion. This occurs when the chosen weight has a zero value on one of its components. To avoid this situation, it is common to use a small but strictly positive value on weights that were originally equal to zero. Instead of imposing all weights of the weight set W to only have strictly positive components, we introduce below a less restrictive assumption on W , in order to ensure that the R O W -nondominated set does not contain any dominated point.

• • • 1 1 1 w 1 w 2 w 3 (a) Illustration of the standard simplex K 3 in R 3 . • • • • • w 1 w 2 w 3 w 4 w 5 w 1 w 2 w 3 (b) Illustration of a constrained weight set W in R 3 . W has 5 extreme points.
Assumption 4.1. Let W ⊆ K p be a set of weights, for each criterion k = 1, ..., p, W contains at least one weight w k such that w k k > 0.

The following result shows that all R O W -nondominated points are nondominated.

Proposition 4.2. Let Y be a set of points in R p and W ⊆ K p be a set of weights verifying Assumption 4.1. Then, we have:

N (Y, R O W ) ⊆ N (Y )
Proof. Let y, y ′ be two points in Y such that y ≤ y ′ . Then we have y j ≤ y ′ j for all j = 1, ..., p, and thus y (j) ≤ y ′ (j) for all j = 1, ..., p. This implies that for all weights w in W , we have OW A w (y) ≤ OW A w (y ′ ). Moreover, there exists q ∈ {1, ..., p} such that y q < y ′ q and thus, there exists k ∈ {1, ..., p} such that y (k) < y ′ (k) . By Assumption 4.1, there exists

w k ∈ W such that w k k > 0, which implies OW A w k (y) < OW A w k (y ′ ). Hence for W ⊆ K p , y R O W -dominates y ′ . Thus we have ≤⊆ R O W , which implies N (Y, R O W ) ⊆ N (Y, ≤) = N (Y ).
In the following we denote by dim af f (W ) the affine dimension of W .

Proposition 4.3. Let Y be a set of points in R p and W 1 , W 2 ⊆ K p be two sets of weights such that W 1 ⊆ W 2 and dim af f (W 1 ) = dim af f (W 2 ) . Then, we have:

N (Y, R O W 1 ) ⊆ N (Y, R O W 2 )
Proof. Suppose by contradiction that there exists a point

y ∈ Y such that y ∈ N (Y, R O W 1 ) and y / ∈ N (Y, R O W 2 ). Then, there exists y ′ ∈ Y such that y ′ R O W 2 y and not y ′ R O W 1 y. Since y ′ R O W 2 y and W 1 ⊆ W 2 , we have for all w ∈ W 1 , OW A w (y ′ ) ≤ OW A w (y)
and wy ′ (.) ≤ wy (.) . Since y ′ is not R O W 1 -preferred to y, we have wy (.) = wy ′ (.) for all w ∈ W 1 . Therefore, we have

dim af f (W 1 ) ≤ dim af f (W 2 ) -1, which leads to a contradiction.
The following example shows that the condition on the equal dimension of weight sets cannot be eliminated in the above proposition.

Example 4.2. Let Y be a set of points in R 3 containing two points y and y ′ , that is Y = {y, y ′ }. Let W 1 = {w ∈ K 3 : wy (.) = wy ′ (.) } and W 2 = {w ∈ K 3 : wy (.) ≤ wy ′ (.) } be two sets of weights represented in Figure 4.4 by the thick segment [AB] and the trapezoidal area ABCD respectively. Clearly W 1 is included in W 2 and dim af f (W 1 ) < dim af f (W 2 ). We have

y ′ ∈ N (Y, R O W 1 ) and y ′ / ∈ N (Y, R O W 2 ), even if W 1 ⊆ W 2 . • D • • C • B • A w 3 w 1 w 2 wy (.) < wy ′ (.)
wy (.) > wy ′ (.)

Relation with the weighted sum

We introduce the following notation.

Y (.) = y (.) ∈ R p : y (.) = (y (1) , ..., y (p) ) is a permutation of y ∈ Y such that y (1) ≤ y (2) ≤ ... ≤ y (p)
The set Y (.) is the set of "ordered" points. Observe that if a point y is a permutation of another point y ′ , that is y (.) is equal to y ′ (.) , there is only one element of Y (.) representing both y and y ′ . Therefore we call an element of Y (.) a representative. The nondominated set of Y (.) is denoted by N (Y (.) ) and is described as follows:

N (Y (.) ) = {y (.) ∈ Y (.) : there is no y ′ (.) in Y (.) such that y ′ (.) ≤ y (.) } Example 4.1 presented two specific cases where a nondominated point y could not be optimal with any OWA. The first case (y 1 in Example 4.1) is related to the reordering step that introduces dominance between representatives. For example, in a context where objectives represent several clients, the clients satisfaction could be considered anonymously. Therefore by ordering the clients satisfaction, this corresponds to a situation where each i th client of a solution is less satisfied than the i th client of another solution, i = 1, ..., p.

The second case (y 5 in Example 4.1) is related to nonsupported nondominated points that cannot be obtained with any weighted sum. Indeed nondominated points having their representative lying in the interior of the convex hull of Y (.) cannot be optimal for any OWA. This corresponds to nonsupported points of N (Y (.) ). However these points can be R O W -nondominated. We illustrate these two cases in Example 4.3. Since y 1 (.) is dominated by y 5 (.) , the OWA value of y 1 is always worse than the OWA value of y 5 for any weight w in K p (Figure 4.2b). We also observe that y 5 (.) does not lie on the frontier of the convex hull of Y (.) . Consequently, y 5 will not be optimal for any OWA, as illustrated in Figure 4.2b. We showed, however, in Example 4.1, Table 4.1, that y 5 belongs to the R O W -nondominated set when W is defined by (4.1). The following result ensures that all nondominated representative points of Y (.) , that is N (Y (.) ), correspond to nondominated points. Proof. Let y (.) be an ordered representative point of N (Y (.) ) and y be any corresponding point in Y . Suppose by contradiction that y is dominated. Then, there exists y ′ ∈ Y such that y ′ ≤ y. Therefore, we have y ′ (.) ≤ y (.) , which leads to a contradiction. Thus, y ∈ N (Y ) and y (.) ∈ N (Y ) (.)

The equality may not be valid in the above proposition. For instance, in Example 4.3, we have N (Y (.) ) = {y 2 , y 3 , y 5 }, whereas N (Y ) (.) = {y 1 , y 2 , y 3 , y 4 , y 5 }.

The following result shows the relation between N (Y ) (.) and N (Y (.) ).

Proposition 4.5. Let Y be a set of points in R p . Then, N (N (Y ) (.) ) = N (Y (.) ).
Proof.

N(Y (.) ) ⊆ N(N(Y) (.) ). Let y (.) be a point of N (Y (.) ). By Proposition 4.4, y (.) belongs to N (Y ) (.) . Suppose by contradiction that y (.) does not belong to N (N (Y ) (.) ). Therefore there exists y ′ in Y such that y ′ (.) ≤ y (.) , contradicting y (.) ∈ N (Y (.) ).

N(N(Y)

(.) ) ⊆ N(Y (.) ). Let y (.) be a point of N (N (Y ) (.) )
. By definition of a nondominated set, there exists no y ′ (.) in N (Y ) (.) , and therefore in N (Y (.) ) (Proposition 4.4), such that y ′ (.) ≤ y (.) . Therefore y (.) belongs to N (Y (.) ).

In Chapter 3, we studied a preference relation, similar to R O W , based on the weighted sum with partial information on the weights. The definition of this preference relation is reminded hereafter. Definition 4.6. Let W be a weight set in R p ≥ and Y be a set of points in the objective space. For any y, y ′ in Y , yR W y ′ if and only if for all w in W , wy ≤ wy ′ and there exists w ′ in W such that w ′ y < w ′ y ′ .

The next results show the relation between R O

W and R W .

Proposition 4.7. Let Y be a set of points in R p and W be a set of weights in K p . Then, we have: ) . By definition, there is no y ′ in Y such that OW A w (y ′ ) ≤ OW A w (y), for all weights w in W , and OW A w ′ (y ′ ) < OW A w ′ (y), for at least one weight w ′ in W . Equivalently, there is no y ′ (.) in Y (.) such that wy ′ (.) ≤ wy (.) , for all weights w in W , and w ′ y ′ (.) < w ′ y (.) , for at least one weight

N (Y, R O W ) (.) = N (Y (.) , R W ) Proof. Let y be a point of N (Y, R O W ) and y (.) its corresponding representative in N (Y, R O W ) (.
w ′ in W , that is y (.) ∈ N (Y (.) , R W ). Therefore, y (.) ∈ N (Y, R O W ) (.) is equivalent to y (.) ∈ N (Y (.) , R W ), hence the proposition.
The following result shows the link between R O W -nondominated points and their representative in N (Y (.) , R W ). Proposition 4.8. Let Y be a set of points in R p , y 1 , ..., y k be points in Y such that y i = y (.) , i = 1, ..., k, and W be a set of weights in K p . Then, we have:

y (.) ∈ N (Y (.) , R W ) if and only if y i ∈ N (Y, R O W ), i = 1, ..., k.
Proof. Suppose that y (.) / ∈ N (Y (.) , R W ). Then, equivalently, there exists y ′ in Y such that y ′ (.) R W y (.) . For all i = 1, ..., k, y ′ R O W y i and

y i / ∈ N (Y, R O W ), i = 1, ..., k, hence the proposition.
From the previous result, all representative points of N (Y, R O W ) can be computed by determining N (Y (.) , R W ). Observe that for each representative in N (Y (.) , R W ), all corresponding points in Y are R O W -nondominated while the optimization algorithm we use, only computes one of the feasible permutations. However, resorting to an OWA aggregation implies that the condition of impartiality between criteria, also called generalized commutativity, is accepted. Consequently the DM should be indifferent between permutations of the same point.

Moreover if all feasible permutations of a representative of a R O W -nondominated point are required, it is possible to check a posteriori which permutations, among the p! possibilities, are feasible. Alternatively, one can compute all solutions in the decision space corresponding to y (.) . Some solvers provide the tool to perform this operation, like the method populate in CPLEX. In Section 4.5, we give, for some MOCO instances, the percentage of points of N (Y ) that are not individually represented in N (Y ) (.) .

Application to multi-objective optimization

Suppose now that W is defined by linear inequalities. Therefore W is a polytope, as depicted in Figure 4.3b. Every element of W can be expressed as a convex combination of its extreme points, denoted by w i . The enumeration of the extreme points of a polytope has been investigated in the field of Computational Geometry with algorithms like the Double Description Method or the Primal-Dual method [START_REF] Bremner | Primal-dual methods for vertex and facet enumeration[END_REF]). The matrix of extreme weights of W is denoted by A as follows. We recall the result to compute the R W -nondominated set hereafter.

A =       w 1 1 w 1 2 ...
Proposition 4.9 (Chapter 3, Section 3.3). Let W be a weight polytope in K p and A ∈ R m×p be its associated matrix of extreme weights defined by (4.3). If W satisfies no additional equality constraint, then we have:

A[N (Y, R W )] = N (A[Y ]) with A[Y ] = {z|z = Ay, y ∈ Y }
Combining Propositions 4.7 and 4.9, we deduce the following result to compute the set of representatives of the R O W -nondominated set. Proposition 4.10. Let W be a weight polytope in K p and A ∈ R m×p be its associated matrix of extreme weights defined by (4.3). If W satisfies no additional equality constraint then we have: ) ] = {z|z = Ay (.) , y (.) ∈ Y (.) } Proof. From Propositions 4.7 and 4.9.

A[N (Y, R O W ) (.) ] = N (A[Y (.) ])with A[Y (.
In order to obtain the representatives of the R O W -nondominated set for multi-objective problem (1.1), we just need to compute the Pareto nondominated set of the following multiobjective problem, where A is the matrix of extreme weights associated to W :

         min Ay ′ = (A 1 y ′ , ..., A m y ′ ) s.t.
x ∈ X y = f (x) y ′ = y (.) (4.4) Contrary to the preference relation R W , the problem constraints are modified and multiobjective optimization algorithms that rely on a specific problem structure cannot be applied. For example, as illustrated in [START_REF] Galand | Choquet-based optimisation in multiobjective shortest path and spanning tree problem[END_REF] with the more general Choquet integral and the multi-objective shortest path problem, dynamic programming cannot be performed to compute the R O W -nondominated set because the Bellman principle does not hold anymore. Therefore the choice of the MOO algorithm must be made depending on the constraints used for the reordering step. We present hereafter a linear formulation with binary variables, which requires resorting to a general multi-objective mixed integer programming solver.

Two-stage procedure

The two-stage procedure is based on Proposition 4.3 and should be applied when W has a large number m of extreme weights. The details are given as follows:

Stage 1. Select a superset W ′ of a set W with the same affine dimension. The weight set W ′ should have less extreme weights than W , ideally p, and not be too large compared to W . We compute the representatives of the R O W ′ -nondominated set with the direct procedure using Proposition 4.10. Every weight set has a superset with p extreme weights, which is the standard unit simplex K p defined by (4.2). However both stages could suffer from a too large number of points in N (Y, R O W ′ ). We presented several methods in Section 3.3.2 that lead to different supersets W ′ . We proposed in Chapter 3 an estimator based on the size of W ′ . We illustrate in the following the advantage of using another estimator in addition to the size of W ′ .

Performance estimation of supersets of similar size

In Chapter 3, Section 3.3, we presented an indicator based on the estimated size of the superset W ′ . Since a weight set W can admit several candidate supersets W ′ , we need to select one of these. From Proposition 4.3, a more constrained weight set W ′ leads to a smaller R O W ′nondominated set. It is thus natural to select supersets based on their size, even if this is only an a priori indication. The size of a weight set W ′ can be approximated by uniformly drawing random weights in K p (see Algorithm 2). However, contrary to observations made concerning R W ′ -nondominated sets, we illustrate in Section 4.5 that weight sets having exactly the same size, differ significantly in terms of computation time and an additional estimator should be taken into account when choosing a superset for the two-stage procedure. We illustrate this in a biobjective space with Figures 4.7 We illustrate with Figures 4.8a and 4.8b, two weight sets W 1 , W 2 defined by w 2 ≤ w 1 and w 1 ≤ w 2 , respectively. These weight sets have the same size.

W 1 (0, 1) (1, 0) w 2 ≤ w 1 w 1 ≤ w 2 • • w 1 w 2 (a) Weight set W 1 defined by w 2 ≤ w 1 in a biobjective space.
W 2 (0, 1)

(1, 0) space of representatives, respectively. We observe that the angle between the hyperplanes defining the cone, also called angle of the cone, is the same for both weight sets in this part of the objective space. However the area dominated by y (.) differs in terms of size. This observation is strenghtened when we illustrate the corresponding domination structure of y in the whole objective space. In the figures above, the domination structure of weight sets having the same size differs in terms of dominated area. Indeed, in Figure 4.9a, the angle of the cone is more directed towards the hyperplane y 1 = y 2 than the one in Figure 4.9b. Therefore, depending on the orientation of the corresponding domination structure, weight sets W with similar size should differ in terms of number of R O W -nondominated points, and thus, computation time. In the subspace of the objective space defined by y 1 ≤ ... ≤ y p , the standard simplex is represented by the Pareto dominance cone, which is the smallest possible cone. We propose an indicator, based on the angle of the cone. For a weight polytope W , we first compute the minimum angle α i , i = 1, ..., p, between each extreme weight e i , i = 1, ..., p, of the standard simplex, corresponding to the i th objective f (i) , i = 1, ..., p, and the extreme weights w j , j = 1, ..., m, of W . Therefore, for i = 1, ..., p, we have the following formulation: = 0, i = 1, ..., p. We illustrate this on Figures 4.11a and 4.11b.

w 2 ≤ w 1 w 1 ≤ w 2 • • w 1 w 2 (b) Weight set W 2 defined by w 1 ≤ w 2 in a biobjective space.
α W i =
+ f 1 f 2 y (.) α W 1 2 (a) Representation of angle α W1 i , i = 1, 2. Note that α W1 1 = 0. + f 1 f 2 y (.) α W 2 1 (b) Representation of angle α W2 i , i = 1, 2. Note that α W2 2 = 0.
W j i , i = 1, 2, j = 1, 2.
However, as we can see in Figures 4.9 to 4.11, an angle with the hyperplane corresponding to objective f (2) seems to less increase the dominated area than the same angle with the hyperplane corresponding to objective f (1) . Instead of just summing the angle differences α i , i = 1, ..., p, we propose to estimate the impact by dividing these angles. In the biobjective space, the hyperplane cuts the objective space in half. Therefore, we propose to estimate this impact by dividing the angle with the hyperplane corresponding to f (2) by 2 and by dividing the angle with f (1) by 1. In a p-dimensional space, the constraint y 1 ≤ y 2 divides the objective space by 2. However the inequality constraint y 2 ≤ y 3 divides the remaining objective space by 3 since it also implicitly adds the constraint y 1 ≤ y 3 . Therefore, we propose to divide the angle with f (3) by 3 × 2. We illustrate this on a section of the triobjective space in the following.

f 1 f 2 f 3 y 1 ≤ y 2 y 1 ≤ y 2 y 2 ≤ y 3 y 1 ≤ y 3 f 1 f 2 f 3 Figure 4
.12: The constraint y 1 ≤ y 2 divides the objective space in half, while y 2 ≤ y 3 divides the remaining objective space by 3.

More generally, the inequality constraint y i-1 ≤ y i , i = 2, ..., p divides the remaining objective space, defined by y 1 ≤ ... ≤ y i-1 , by i. Consequently, we propose to divide the angle with f (i) by i!, as presented hereafter.

E W = p i=1 α W i i! (4.9)
Remark 4.12. Note that E Kp = 0.

Between supersets of the same size, the weight sets with the largest E W value should be chosen. Between supersets of different size, selecting a superset should be based both on the size and the E W value. Between two supersets, a large difference on the size in one direction cannot be compensated by a small difference on the E W value in the other direction and conversely. Nevertheless this observation should be put into perspective. Indeed, the area covered by the domination structure depends on the position of the considered points in the objective space. Therefore, similarly to the estimated size of the weight sets in Chapter 3, this indicator aims to provide an a priori estimation of the weight set performance in most cases.

Preference elicitation frameworks

Preference information can be elicited using several frameworks that have already been presented in the context of imprecise weights with the weighted sum. We present some of them hereafter with results on their number of extreme weights. Most of them are based on ordinal information as the DM generally prefers to avoid expressing precise parameter values.

Ordinal information

A classic situation is when the DM cannot provide cardinal information on the weights but is able to rank the weights by order of importance. We first present two weak rankings that correspond to specific preferences. Depending on the context, it can characterize the attitude of the DM towards risk, equitability, etc. The third preference elicitation framework is based on the median value. The last framework is based on unimodal weights.

Pessimistic preferences

The DM can decide to assign largest weights to the worst values. We define the following set of weights with a weak ranking on the weights.

W 1 = {w ∈ K p : w 1 ≤ w 2 ≤ ... ≤ w p } (4.10)
Several specific weights belongs to W 1 :

• The min-max criterion, which corresponds to w = (0, ..., 0, 1), is represented in the set W ′ 1 . • The mean criterion, which corresponds to w = ( 1 p , ..., 1 p ), is represented in the set W ′ 1 . More generally all OWA giving a higher importance to the worst values, and therefore pessimistic preferences, are represented using set W 1 . Therefore the DM is only required to indicate that he/she has pessimistic preferences. The orness of weights in the set goes from 0 to 0.5. Proposition 4.13. The number of extreme weights of W 1 is p.

Proof. From Proposition 3.19.

The matrix A 1 corresponding to the extreme weights of W 1 is reminded hereafter (Section 3.4).

A 1 =         0 ... 0 0 1 0 ... 0 1 2 1 2 0 ... 1 3 1 3 1 3 . . . . . . . . . . . . . . . 1 p ... 1 p 1 p 1 p        
Generating the R O W 1 -nondominated set amounts to generating the nondominated set according to the Lorenz dominance, which is consistent since the Lorenz dominance favors equitable outcomes. In order to show this, we first recall the definition, in a minimization context, of the Lorenz dominance [START_REF] Marshall | Inequalities: theory of majorization and its applications[END_REF]Olkin, 1979, Perny and[START_REF] Perny | An axiomatic approach to robustness in search problems with multiple scenarios[END_REF], denoted by ≤ L . We introduce the following result between R O W 1 and ≤ L . Proposition 4.15. Let Y be a set of points in R p and W 1 the weight set defined by (4.10). Then, we have N (Y, R O W 1 ) = N (Y, ≤ L ) . Proof. According to Proposition 3.14, using matrix A 1 for the application of R O W 1 is equivalent to using the following matrix A 1′ .

A 1′ =         0 ... 0 0 1 0 ... 0 1 1 0 ...
(.) = y ′ (.) . Thus, R O W 1 = ≤ L and N (Y, R O W 1 ) = N (Y, ≤ L ).

Optimistic preferences

The DM can decide to assign the largest weights to the best values. We define the following set of weights with a weak ranking on the weights.

W 2 = {w ∈ K p : w 1 ≥ w 2 ≥ ... ≥ w p } (4.11)
Several specific weights belong to W 2 :

• The min-min criterion, which corresponds to w = (1, 0, ..., 0), is represented in the set W 2 .

• The mean criterion, which corresponds to w = ( 1 p , ..., 1 p ), is represented in the set W 2 . More generally, all OWA giving a higher importance to the best values, and therefore optimistic preferences, are represented using set W 2 . Similarly to the previous case, the DM is only required to indicate that he/she has optimistic preferences. The orness of weights in the set goes from 0.5 to 1.

Median-centered preferences

The DM can also dislike extreme values and give more importance to central values of a point. Therefore the more an objective is central, the more it is important to the DM. We define the corresponding weight set:

W 3 = {w ∈ K p : w i ≤ w j , |j - p + 1 2 | < |i - p + 1 2
|, i, j = 1, ..., p} (4.12)

Several specific weights belong to W 3 :

• The median criterion, which corresponds to w = (0, ..., 0, 1, 0, ..., 0) when p is odd or w = (0, ..., 0, 1 2 , 1 2 , 0, ..., 0) when p is even, is represented in the set W 3 .

• The mean criterion, which corresponds to w = ( 1 p , ..., 1 p ), is represented in the set W 3 . More generally all preference based on excluding extreme values are represented within this set.

This framework is equivalent to the Group Ranking framework (Chapter 3, Section 3.4). Therefore we can deduce from Proposition 3.21 the following result on the number of extreme weights.

Orness-based preferences

This framework is used in Example 4.1. The DM is able to provide a lower and/or an upper bound for the orness measure, l and u respectively. The associated set of weights W 4 is defined below.

W 4 = {w ∈ K p : l ≤ orness(w) ≤ u} (4.16)
The orness measure lies between 0 and 1 for all weights. Therefore we impose 0 ≤ l ≤ u ≤ 1. The maximum number of extreme weights of the set W 4 may be very large. In order to apply a two-stage procedure, we consider two possible supersets W l 4 , W u 4 which have both p extreme weights. The supersets only impose a lower and an upper bound, respectively. The choice of the most promising superset will be made regarding their respective size. We consider W l 4 , superset of W 4 and defined by a lower bounds on the orness measure. (i -2)w i . Since (i -2)w i ≥ 0, i = 2, ..., p, we have w 1 ≥ 0.

Consequently, W l 4 is defined by an irredundant system of p inequality constraints: orness(w) ≥ l and w i ≥ 0, i = 2, ..., p, and the normalization constraint. The result follows by Proposition 3.17.

The extreme weights of W l 4 are the feasible basic solutions of polytope W l 4 . A basic solution is the solution of a system composed of p -1 inequality constraints of W l 4 set to equality completed by the normalization constraint. We get the extreme weights by solving these p systems. The extreme weights of W l 4 are given below.

A 4,l =         1 0 ... 0 ... 0 1-(1-l) p-1 1 (1-l) p-1 1 ... 0 ... 0 . . . . . . . . . . . . . . . . . . 1-(1-l) p-1 i-1 0 ... (1-l) p-1 i-1 ... 0 . . . . . . . . . . . . . . . . . . l 0 ... 0 ... (1-l)        
We also consider W u 4 , superset of W 4 and defined by an upper bound on the orness.

W u 4 = {w ∈ K p : orness(w) ≤ u} (4.18)

• p = 4 and n = 40 (4-MOKP40),

• p = 5 and n = 30 (5-MOKP30).

For MOAP we used the following instance sizes:

• p = 3 and n = 50 (3-MOAP50),

• p = 4 and n = 30 (4-MOAP30),

• p = 5 and n = 20 (5-MOAP20).

We also use several preference elicitation frameworks:

• No preference relation. This framework computes the Pareto nondominated set. It is therefore denoted by Pareto in the different tables;

• No information on weights. This framework is equivalent to use K p as weight set and to compute the nondominated set of representative points, that is we compute N (Y (.) ). It is therefore denoted by Representative in the different tables;

• The orness-based preferences framework are denoted by Orness lu, where l, u denotes the lower and upper bound on the orness, respectively. Orness 0 -0.5 and Orness 0.5 -1 are tested when p = 3;

• The median-centered preferences framework is denoted by Median;

• The optimistic preferences framework is denoted by Optimistic. The corresponding weight set is a subset of the weight set of Orness 0.5 -1;

• The pessimistic preferences framework is denoted by Pessimistic. The corresponding weight set is a subset of the weight set of Orness 0 -0.5;

A computer with a Linux Debian operating system, 3.7 GHz processor and a 32 GB memory limit has been used for the experiments. CPLEX 12.6.3 is the solver provided for the algorithm. We used 10 instances for each problem size to compute our results. Several observations are made regarding quantitative information -computation time denoted by CPU time, number of representative of preferred points denoted by |N (Y, R O W ) (.) |, size of the corresponding weight set and estimator value, denoted by E W . Note that for the Pareto framework, we provide the number of Pareto nondominated points, that is |N (Y )|. We also make observations based on qualitative information (consistency with the weight sets). For the sake of clarity we split the results in several parts.

From the objective space to the representative space

In Section 4.2.2, we explained that a representative in Y (.) may correspond to several points in the objective space. We computed for 3-MOKP100, 4-MOKP40 and 3-MOAP50 instances, the number of Pareto nondominated points that are not individually represented in N (Y ) (.) . With Table 4.4, we observe that the percentage of points of N (Y ) that are not individually represented in the set N (Y ) (.) is rather small. Therefore the "loss" of points due to the reordering step does not have a significant impact.

3-MOKP100

Estimated size and performance estimator value

We present the size and estimator value, denoted by E W , of the weight sets hereafter. The size is approximated by using Algorithm 2 to draw 5.0 × 10 6 random weights over K p . We observe in Table 4.5, that Orness 0.5-1 and Orness 0-0.5 have the same size. However, the value of E W for these two weight sets differ. Indeed, the value of E W is larger for Orness 0-0.5 than for Orness 0.5-1. Therefore Orness 0-0.5 should compute a lower number of preferred points. The same observations hold for the Optimistic and Pessimistic frameworks when p = 3, 4, 5. Concerning the supersets of the Median framework when p = 3 (4.13), Median superset 3a and Median superset 3b have the same size but different E W value. Since Median superset 3b has a larger E W value than Median superset 3a , Median superset 3b should have better performances than Median superset 3a . Moreover, Median superset 3a has a relatively large size and low E W value compared to the Median framework. Even if the Median framework involves a weight set with 4 extreme weights, the computation time of Median could be lower than Median superset 3a . Median superset 3c is smaller than Median superset 3b in terms of size but also have a smaller E W value. Since the difference of size is not significant enough compared to the difference of E W value, Median superset 3b could have better performances than Median superset 3c . Numerical experiments confirm these assumptions. We also observe that Orness 0.5-1 and Median superset 3a have the same size and E W value. Therefore we expect these weight sets to have similar performances. However numerical results do not confirm this assumption and show the limit of the estimator E W . The same observation holds for Orness 0-0.5 and Median superset 3b . p = 4 #Extreme Size (%) E W (×10

p = 3 #Extreme Size (%) E W (×10 -

CPU time and number of preferred points

With Table 4.8, we present the corresponding average CPU time(s) and number of nondominated points. We observe that computing the R O W -nondominated set is always faster than computing the Pareto nondominated set. For each problem type and size, using one of the presented frameworks always reduces substantially the computation time and the corresponding R O Wnondominated set has a smaller size than the standard Pareto nondominated set (Proposition 4.2).

When each weight set has p extreme weights, the computation time of the most restricted set is lower than the least restricted one since there are fewer points to compute (see, e.g., Pessimistic and Orness 0-0.5 framework). However weights with the exact same size behave differently (see Section 4.3). For example, Orness 0.5-1 and Orness 0-0.5 have the same size but have different performances on 3-MOKP100 and 3-MOAP50. Orness 0.5-1 yields more R O W -nondominated points than Orness 0-0.5, which also induces a larger computation time than Orness 0-0.5. We also observe similar differences between the pessimistic and optimistic frameworks on almost all instances. However on 5-MOKP30 instances, the optimistic framework performs better in terms of computation time. This may come from the low number Observe however that the number of R O W -nondominated points is still lower in the pessimistic framework than in the optimistic framework. We performed experiments in the 5-objective case on 5-MOAP20 instances, which have a larger number of points. Since the number of R O W -nondominated points is significant, the pessimistic framework has a lower computation time than the optimistic framework.

Performance of the two-stage procedure

The two-stage procedure applies when the weight sets admit a number of extreme weights larger than p. This is the case for the preference elicitation framework based on mediancentered preferences (see Section 4.4.1). For p = 3, three supersets were used in the two-stage procedure: W 3a 3 , W 3b 3 , and W 3c 3 , defined by (4.13). They are denoted in the different tables by Median superset 3a , Median superset 3b , and Median superset 3c , respectively. For p = 4, four supersets were used in the two-stage procedure: W 4a 3 , W 4b 3 , W 4c 3 , and W 4d 3 , defined by (4.14). They are denoted in the different tables by Median superset 4a , Median superset 4b , Median superset 4c , and Median superset 4d , respectively. Results are reported in Tables 4.9 and 4.10.

We compared the performance of several supersets in the two-stage procedure in order to evaluate the relevance of the estimator presented in Section 4.3. 4.9: Comparison between the direct approach and the two-stage procedure.

3-MOKP100

CPU time(s) |N (Y, R O W ) (.) | Size E W (×10 -
In Table 4.9, there are three possible supersets, that are Median superset 3a , Median superset 3b , and Median superset 3c . We observe that Median superset 3a and Median superset 3b have the same size but different E W value. Median superset 3b has a better E W value and also a better computation time than Median superset 3a . This supports the relevance of our performance estimator, when weight sets have similar size and number of extreme weights. However, Median superset 3b is larger than Median superset 3c in terms of size. The estimator value of Median superset 3b is significantly better than the one of Median superset 3c . The computation time of Median superset 3b is also better than Median superset 3c . This illustrates that the size of a weight set should not be the only criterion when choosing a superset. The computation time of the direct procedure is larger than the two-stage procedure with Median superset 3b . Nevertheless, the computation time of the direct procedure is smaller than the two-stage procedure with Median superset 3a . This underlines the need of adapting the performance estimation of Chapter 3, only based on the size, to this preference relation. When p = 4, the same observations on the relation between the estimator E W and the computation time hold. With similar size, weight sets that have a larger performance estimator than other weight sets are more likely to compute the corresponding R O W -nondominated set faster than those weight sets. For instance with Median superset 4a and Median superset 4b , the corresponding weight sets have the same size but Median superset 4a is faster than Median superset 4b . Median superset 4c and Median superset 4d have the same size and the same value for E W . Their performances in terms of computation time and number of R O W -nondominated points are also similar. However there are several limits with this indicator. Based on the E W values, Median superset 4a seems to be the best possible choice but Median superset 4c and Median superset 4d have better performances. Indeed, the size of Median superset 4a is significantly larger than the size of Median superset 4c and Median superset 4d and this difference cannot be compensated by the difference on the E W value. Therefore the size of a weight set still needs to be taken into account. A possible research direction would be to consider an estimator that takes into account both the size of the weight set and, like E W , the angle of the corresponding dominance structure.

4-MOKP40

CPU time(s) |N (Y, R O W ) (.) | Size E W (×10 -

Limit of the proposed performance estimator

We show with the following table the limit of E W and the size as performance estimator.

Orness 0.5-1, Median superset 3a , and Orness 0-0.5, Median superset 3b , have the same size and E W value, respectively. However the size of the corresponding preferred set varies in all instances. This shows the limit of E W and the size when comparing two weight sets and proves the need of finding a more relevant estimator.

Consistency with the weight set

To evaluate the consistency of a returned R O W -nondominated set with the corresponding weight set, we take as indicators the minimum and maximum values on each i th objective f (i) , i = 1, ..., p, over this set. These values correspond to the ideal and nadir point values of N (Y, R O W ) (.) , respectively (Definition 1.6). For this purpose, after computing the R O W -nondominated sets on one 3-MOAP50 instance, we report the results in Table 4.12. Results on other instances are similar. Table 4.12 illustrates the consistency between the R O W -nondominated points and the preference elicitation framework. Consider first the Orness 0.5-1 framework. This framework preserves the best performance on f (1) , f (2) , and only slightly deteriorates the best performance on f (3) . Moreover, the worst performances are not improved significantly on all three objectives. The extreme values do not change, since Orness 0.5-1 favors solutions that are good on at least one objective. On the contrary, Orness 0-0.5 preserves the best performance on f (2) , f (3) , but deteriorates the best performance on f (1) . The worst performance on f (2) significantly improves, while the worst performance on f (3) improves with a lower order of magnitude than on f (2) . This corresponds to points that are good on at least two objectives and do not have the worst performances on f (3) , which is consistent with the framework since it corresponds to points that do not have only one good performance. Likewise, Median deteriorates the best performance on f (1) and improves the worst performances on f (2) , f (3) but with a different order of magnitude. Median significantly improves the worst median value (f (2) ), which is consistent with the framework.

3-MOAP50 instance

Ideal Nadir f (1) f (2) f (3) f (1) f (2) f (3)
The same observations as for Orness 0-0.5 and 0.5-1 hold for the Pessimistic and Optimistic framework, respectively. Since the preference information is more precise, the trend is strenghtened with the Pessimistic and Optimistic framework. For example, the Pessimistic framework significantly deteriorates the best performances on f (1) and f (2) and improves the worst performance on f (2) and f (3) . This is also consistent with the framework, since it corresponds to points that avoid the largest values.

Conclusions and perspectives

In this chapter we presented a preference relation based on OWA and a set of possible weights defined by partial preference information. We showed noteworthy properties in the general case. In the specific case where the weight set is a polytope, we proposed a way to apply this preference relation with an a priori approach in multi-objective optimization problems. We also reused the two-stage procedure presented in Chapter 3 in order to compute the corresponding nondominated set. An additional indicator is provided in order to take into account the specificity of the domination structure. Several preference elicitation frameworks are discussed with some results on their number of extreme weights and instanciated on MOCO problems. They show competitive results both in terms of quantitative information (CPU time and number of preferred points) and qualitative information. This shows the efficiency of integrating a priori preference information in multi-objective optimization algorithms. The experimental results are promising in most cases and show that the two-stage procedure is more interesting in all cases. Nevertheless this suggests several directions for future work like determining another performance estimator that not only takes into account the size of the weight set but also the size of the dominated area. Furthermore, additional preference elicitation frameworks or enumeration algorithms could be tested and compared. This general approach of exploiting partial preference information can also be studied with other aggregation models.

122

PERSPECTIVES

the data association problem and the sensor management problem -that is a large number of objectives and solutions, a limited computation time, and relevant solutions for the decision maker-this work fulfills the goals defined at the beginning of this thesis by proposing several partial preference models and their application to multi-objective optimization. It shows that the approach consisting in using partial preference information to reduce the number of generated solutions and the computation time, is appropriate in multi-objective optimization.

Research directions

This thesis opens several future research directions. Some technical points can be improved for each preference relations. The preference relation based on thresholds could benefit from another preference elicitation framework. Similarly to the preference relations based on the weighted sum and OWA, this preference relation could be adapted to partial preference information. For example, the DM could only provide constraints on requirement and tolerance thresholds. The preference relation based on OWA needs further work on the performance estimator. Indeed some numerical experiments show that the estimator based on the angle can be refined in order for the estimation to correspond in all cases.

Applying a preference relation based on a scalarizing function and partial preference information on parameters could be extended to other aggregation functions in MOO. For instance, the weighted Tchebycheff method could have weights defined by partial preference information but the reference point of this scalarizing function could also be defined by partial preference information.

More generally, all these preference relations could also be applied with approximate algorithms when the single objective version of the MOO problem is hard to solve, like ,e.g., the travelling salesman problem. For the preference relation based on the weighted sum, the adaptation is straightforward since it consists in solving a modified MOO problem. For the preference relation based on thresholds or based on OWA with partial preference information on weights, similarly to the application of these preference relations to exact algorithms, the adaptation would need more specific work.

Au contraire de l'aide à la décision multi-critères, l'optimisation multi-objectifs se concentre sur la génération de l'ensemble Pareto-optimal d'un problème d'optimisation multi-objectifs défini par des contraintes. Cette branche travaille sur les problèmes liés à l'optimisation et se concentre plus particulièrement sur l'amélioration des temps de calculs.

Certains problèmes d'optimisation ont pour caractéristiques d'avoir un grand nombre de solutions réalisables, un grand nombre d'objectifs et un temps de calcul limité. Dans ce contexte, le décideur est intéressé par les solutions Pareto-optimales. Calculer l'ensemble des solutions Pareto-optimales de ces problèmes génère tous les compromis intéressants. Cependant, le nombre de solutions Pareto-optimales est très grand, ce qui résulte la plupart du temps en un temps de calcul prohibitif et en des solutions non pertinentes pour le décideur. Une autre approche est de choisir un modèle d'aggrégation, déterminer les paramètres de ce modèle avec des informations fournies par le décideur, et générer les solutions optimales selon ce modèle. Une difficulté majeure de cette approche est de déterminer les paramètres du modèle, car il demande la plupart du temps des informations très précises au décideur. Ces paramètres peuvent en plus dépendre de la méthode d'élicitation choisie et mener à des résultats très différents.

Pour pallier les limites de ces approches, une troisième voie est apparue. Cette voie a pour but d'étudier l'intégration d'informations de préférences en optimisation multi-objectifs via des modèles de préférences partielles. Un modèle de préférences partielles enrichit la relation de dominance de Pareto et réduit l'incomparabilité entre les solutions. Cependant la plupart de ces approches ont aussi besoin de valeurs précises pour leur paramètres.

Objectifs et plan de la thèse Dans cette thèse, nous étudions l'application de relations de préférences partielles en optimisation multi-objectifs. Nous proposons des modèles de préférences partielles dont les paramètres sont plus aisés à déterminer pour un décideur et nous nous concentrons sur l'application de ces modèles à des problèmes d'optimisation combinatoires multi-objectifs. Nous présentons dans cette thèse plusieurs modèles de préférences partielles : une relation de préférence basées sur des seuils, une relation de préférence basée sur la somme pondérée avec information partielle sur les poids et une relation de préférence basée sur la somme pondérée ordonnée avec information partielle sur les poids. Nous nous sommes intéressés à la génération de l'ensemble des points préférés, défini comme étant les points non-dominés selon ces relations. Nous donnons certaines propriétés de ces relations de préférences et présentons des adaptations d'algorithmes d'optimisation discrète multi-objectifs pour générer l'ensemble des points préférés. Les expérimentations sur des problèmes d'optimisation combinatoires multi-objectifs démontrent la pertinence de notre approche aussi bien en terme de temps de calcul que de qualité des points générés.

Résumé du chapitre 1

Dans le premier chapitre, nous introduisons les notations utilisées tout au long de la thèse mais également des définitions (Pareto-optimalité, somme pondérée, somme pondérée ordonnée, etc.), propriétés et autres outils nécessaires par la suite. Nous nous concentrons en particulier sur l'optimisation discrète multi-objectifs et présentons un algorithme générique basée sur la notion de région de recherche. Cet algorithme décompose l'espace des objectifs en zones de recherche qui peuvent contenir des solutions n'ayant pas été générées. Après avoir calculé une nouvelle solution, l'algorithme met à jour la région de recherche en supprimant les zones que l'on sait vides. Pour finir, nous présentons deux problèmes d'optimisation multi-objectifs qui ont servi pour les expérimentations numériques : le problème du sac-à-dos multiobjectifs ainsi que le problème d'affectation multi-objectifs.

Résumé du chapitre 2

Ce chapitre présente une relation de préférence originale qui définit des compromis basés sur des seuils d'amélioration et de détérioration sur les objectifs. Cette relation enrichit la dominance de Pareto en définissant des nouveaux cas de dominance grâce à ces seuils. Une solution est préférée à une autre si elle atteint un certain niveau d'amélioration sur un groupe d'objectifs sans dépasser un certain niveau de détérioration sur les objectifs restants. Nous introduisons l'exemple suivant pour motiver l'utilisation de cette relation de préférence.

Exemple Dans un contexte de minimisation des critères, soit Y = {y 1 , y 2 , y 3 } l'ensemble des solutions Pareto-optimales évaluées sur trois critères avec y 1 = (11, 9, 15), y 2 = (10, 10, 18) et y 3 = (15, 13, 12). Le décideur établit que si une solution est significativement meilleure qu'une autre sur les deux premiers critères et que la différence sur le troisième critère n'est pas trop importante, alors la première est préférée à la seconde. Pour modéliser cette situation, nous fixons le niveau d'amélioration à atteindre pour chacun des deux premiers objectifs à 2 et le niveau de détérioration à ne pas dépasser sur le dernier objectif à 5. Ces niveaux d'amélioration/détérioration sont représentés par un vecteur ∆ = (2, 2, -5).

Dans cette situation, y 1 est préféré à y 3 et y 3 ne sera pas présenté au décideur. Observons cependant que y 2 n'est pas préféré à y 3 car la performance de y 2 sur le troisième critère est trop loin de celle de y 3 .

Ces valeurs d'amélioration et de détérioration peuvent être constantes ou variables et représenter plusieurs situations de compensation. Cette relation de préférence n'est pas nécessairement transitive et correspond à une union de cônes de dominance selon Pareto qui sont translatés suivant différents vecteurs. Partant de cette observation, nous adaptons un algorithme d'optimisation discrète multi-objectifs en modifiant la phase d'exploration et de mise à jour de la région de recherche. La phase de mise à jour de la région de recherche consiste à utiliser des points artificiels en plus du point non dominé trouvé précédemment. La phase d'exploration consiste à ajouter une deuxième étape qui garantit, grâce à l'optimisation d'un programme mathématique, la non-dominance d 'un point nouvellement trouvé. Nous fournissons des expérimentations numériques sur le problème d'affectation multi-objectifs. Les résultats sont intéressants aussi bien en terme de temps de calcul qu'en terme de nombre de points générés.

3-MOAP50

Résumé du chapitre 3

Ce chapitre présente une relation de préférence basée sur la somme pondérée avec information préférentielle partielle sur les poids. Classiquement, la somme pondérée est utilisée avec un jeu de poids avec des valeurs spécifiques. Déterminer ce jeu de poids est contraignant pour un décideur, aussi nous proposons d'étudier l'application d'une relation de préférence utilisant la somme pondérée mais avec un jeu de poids seulement partiellement défini, dans le sens où l'information donnée par le décideur détermine un ensemble de poids représentant les préférences du décideur. Cette relation de préférence a déjà été etudiée dans de nombreux articles mais nous nous concentrons sur l'application de cette relation à l'optimisation mlulti-objectifs. Après avoir déterminé un ensemble de poids possibles représentant les préférences du décideur, une solution est préférée à une autre si elle est meilleure pour toutes les sommes pondérées possibles. Nous introduisons grâce à l'exemple suivant les avantages de cette relation. En choisissant un poids w = (0.5, 0.5), la somme pondérée génère la solution y 2 comme solution préférée. Clairement, y 3 est une solution équilibrée et devrait être proposée au décideur. La figure 3b montre que quelque soit le poids choisi, le point y 3 ne sera jamais optimal.

Exemple

Supposons maintenant que l'on traduise le fait que les critères ont une importance similaire par déterminer l'ensemble de poids suivant. W = {w ∈ R 2 : 0.4 ≤ w 1 ≤ 0.6, 0.4 ≤ w 2 ≤ 0.6, w 1 + w 2 = 1}.

Une soluion est préférée à une autre si sa somme pondérée est meilleure pour tous les poids possibles. La figure 3a montre la valeur de la somme pondérée avec un poids dans W pour les 5 alternatives. De cette représentation, nous observons que y 1 et y 5 sont respectivement plus mauvaises que y 2 et y 4 pour tous les poids possibles dans W . Cependant ni y 2 ni y 4 ne sont meilleurs que y 3 pour tous les poids possibles. L'ensembles des alternatives préférées selon cette relation est donc {y 2 , y 3 , y 4 }. L'ensemble de points préférés est réduit par rapport à l'ensemble Pareto-optimal et intègre des solutions pertinentes pour le décideur.

L'application de cette relation de préférence en optimisation multi-objectifs est possible lorsque l'ensemble de poids est défini par des contraintes linéaires. Dans ce cas là, la relation peut s'exprimer à l'aide uniquement des poids extrêmes de l'ensemble de poids. En reformulant les critères du problème d'optimisation multiobjectifs que l'on veut résoudre avec ces poids extrêmes, on peut alors générer l'ensemble des solutions préférées selon cette relation. Lorsque le nombre de poids extrêmes est grand, le problème reformulé peut être compliqué à résoudre. Dans ce cas, nous proposons une procédure en deux étapes. La première étape consiste à générer un surensemble des solutions préférées qui sera plus facile à calculer. La deuxième étape consiste à filtrer la liste explicite de solutions calculées précédemment. La figure ?? représente un exemple de surensemble que l'on peut utiliser pour la procédure en deux phases. Nous détaillons plusieurs manières de définir des ensembles de poids représentatifs des préférences d'un décideur : classement des objectifs par ordre d'importance, tri des objectifs en groupes d'importance mais aussi définition de bornes inférieures et supérieures pour les poids des objectifs.

Pour évaluer les bénéfices de cette approche, nous avons appliqué nos résultats sur les problèmes d'affectation et sac-à-dos multi-objectifs. Sur tous les ensemble de poids étudiés, les expérimentations numériques démontrent la pertinence de l'approche, aussi bien en terme de temps de calculs que de qualité des solutions générées. La méthode en deux phases que nous proposons est notamment avantageuse en terme de temps de calcul et représente un gain conséquent dans l'application de cette relation.

Résumé du chapitre 4

La somme pondérée ordonnée (OWA en anglais) est une fonction de scalarisation qui associe un poids à l'objectif avec la plus grande valeur, puis à celui avec la deuxième plus grande valeur, etc. Cette opérateur permet d'optimiser plusieurs critères comme le min, le max ou encore la médiane. Cet opérateur peut représenter différentes préférences du décideur vis-à-vis du risque ou de l'équité qu'il/elle désire fixer. Cette attitude du décideur a été quantifiée grâce à l'expression de l'orness. Dans un contexte de minimisation, plus l'orness d'une somme pondérée est proche de 1, plus la somme pondérée ordonnée se concentre sur des points avec au moins une très bonne valeur (optimisime). Plus l'orness est proche de 0, plus la somme pondérée ordonnée se concentre sur des points dont la plus mauvaise valeur est basse (pessimisme). Ce chapitre présente une relation basée sur la somme pondéré ordonnée avec information partielle préférentielle sur les poids. Cette relation de préférence a déjà été étudiée dans quelques publications mais nous nous concentrons sur son application à l'optimisation multi-objectifs. De même qu'au chapitre précédent, après avoir déterminé un ensemble de poids possibles représentant les préférences du décideur, une solution est préférée à une autre si elle est meilleure pour toutes les sommes pondérées ordonnées possibles. En choisissant une somme pondérée ordonnée avec orness(w) = 0.5, le point y 3 est l'alternative optimale. Clairement, y 2 et y 5 sont également des solutions intéressantes et devraient être proposées au décideur. En choisissant orness(w) = 0.4 et orness(w) = 0.6, les solutions y 2 et y 3 sont optimales. Cependant, y 5 ne peut être optimale pour aucune somme pondérée ordonnée.

Exemple

Supposons maintenant que l'on traduise le fait que les critères ont une importance similaire par déterminer l'ensemble de poids suivant. W = {w ∈ R 2 : 0.4 ≤ w 1 ≤ 0.6, 0.4 ≤ orness(w) ≤ 0.6, w 1 + w 2 = 1}.

La figure 6a montre la valeur de la somme pondérée ordonnée avec un poids dans W pour chaque point. On observe que ni y 2 , ni y 3 n'est meilleure que y 5 pour tous les poids dans W , contrairement à y 1 et y 4 . L'ensemble des points non-dominés selon la nouvelle relation est donc {y 2 , y 3 , y 5 }. L'ensemble de points préférés est réduit par rapport à l'ensemble Pareto-optimal et intègre des solutions pertinentes pour le décideur.

L'application de cette relation de préférence en optimisation multi-objectifs est possible lorsque l'ensemble de poids est défini par des contraintes linéaires. Dans ce cas là, on peut utiliser les résultats du chapitre précédent et les liens entre la somme pondérée ordonnée et la somme pondérée. En reformulant les critères du problème d'optimisation multi-objectifs avec les poids extrêmes et en ajoutant des contraintes pour intégrer le classement des critères, on peut alors générer l'ensemble des solutions préférées selon cette relation. Lorsque le nombre de poids extrêmes est grand, le problème reformulé peut être compliqué à résoudre. Dans ce cas, nous réutilisons la procédure en deux étapes présentée précédemment en ajoutant un indicateur propre à la somme pondérée ordonnée. Les expérimentations numériques sur des problèmes d'optimisaiton combinatoires multi-objectifs démontrent la pertinence de notre approche, aussi bien en terme de temps de calculs que de qualité des solutions générées.

Conclusions et perspectives

Nous nous sommes concentrés dans cette thèse sur l'intégration d'informations de préférences dans les algorithmes d'optimisation multi-objectifs. La motivation était double car générer l'ensemble des solutions Pareto-optimales est à la fois couteux et souvent non pertinent. Nous avons proposé trois relations de préférence basées respectivement sur des valeurs de seuils, la somme pondérée avec information préférentielle partielle sur les poids et la somme pondérée ordonnée avec information préférentielle partielle sur les poids.

Cette thèse ouvre plusieurs axes futurs de recherche. Outre certains points techniques, la démarche de raisonner sur des fonctions de scalarisation avec des informations préférentielles partielles sur leurs paramètres pourrait être étendue à d'autres fonctions. L'application d'algorithmes approchés d'optimisation pourrait aussi être étudié avec des modèles de préférences partielles.

Résumé Mots Clés

Abstract

Keywords

Les problèmes d'optimisation multi-objectifs mènent souvent à considérer des ensembles de points non-dominés très grands à mesure que la taille et le nombre d'objectifs du problème augmentent. Générer l'ensemble de ces points demande des temps de calculs prohibitifs. De plus, la plupart des solutions correspondantes ne sont pas pertinentes pour un décideur. Une autre approche consiste à utiliser des informations de préférence, ce qui produit un nombre très limité de solutions avec des temps de calcul réduits. Cela nécessite la plupart du temps une élicitation précise de paramètres. Cette étape est souvent difficile pour un décideur et peut amener à délaisser certaines solutions intéressantes. Une approche intermédiaire consiste à raisonner avec des relations de préférences construites à partir d'informations partielles. Nous présentons dans cette thèse plusieurs modèles de relations partielles de préférences. En particulier, nous nous sommes intéressés à la génération de l'ensemble des points non-dominés selon ces relations. Les expérimentations démontrent la pertinence de notre approche en termes de temps de calcul et qualité des points générés.

Multi-objective optimization problems often lead to large nondominated sets, as the size of the problem or the number of objectives increases. Generating the whole nondominated set requires significant computation time, while most of the corresponding solutions are irrelevant to the decision maker. Another approach consists in obtaining preference information, which reduces the computation time and produces one or a very limited number of solutions. This requires the elicitation of precise preference parameters most of the time, which is often difficult and partly arbitrary, and might discard solutions of interest. An intermediate approach consists in using partial preference models. In this thesis, we present several partial preference models. We especially focused on the generation of the nondominated set according to these preference relations. This approach shows competitive performances both on computation time and quality of the generated preferred sets.

Definition 1. 4 .

 4 Figure 1.2 depicts an example of the ideal and nadir point.

Figure 1

 1 Figure 1.2: The coordinates of y I and y N are the minimum and maximum values of the nondominated points, respectively.

  Figure 1.3: Illustration of supported and nonsupported points in the biobjective case.

Figure 1 . 4 :

 14 Figure 1.4: Initialization of the search region with the search zone induced by u 0 .

Figure 1 . 5 :

 15 Figure 1.5: Illustration of the updating step (1).

  for all d ∈ C and λ > 0 Definition 1.18 (Cone relation). Let y, y ′ be two points in R p and C be a cone in R p . We define the cone relation according to C as follows. y dominates y ′ according to the cone C if and only if y ′y ∈ C \ {0}. Proposition 1.19 (Convex cone). A cone C ⊆ R p is convex if and only if

Figure 1 . 8 :

 18 Figure 1.8: Representation of a polyhedron P defined by 3 inequality constraints in the biobjective case. There are two extreme points A and B.

  b) y 2 does not R ∆ -dominates y 3 (Example 2.1).

Figure 2 . 1 :

 21 Figure 2.1: Illustration of Example 2.1.

Figure 2 . 3 :

 23 Figure 2.3: Representation of Y I> , N (Y I> ), Category I and Category II in Example 2.3.

Figure 2 . 4 :

 24 Figure 2.4: Illustration of an improvement/deterioration scale for each criterion.

Figure 2 . 5 :

 25 Figure 2.5: After generating y, the part RU -dominated by y is removed from the search region.

Figures 2 .

 2 Figures 2.6a and 2.6b depict the adapted updating step applied to Example 1.1. Extending this procedure to several thresholds ∆ 1 , ..., ∆ m is straightforward. After generating a point y, the search region is updated with y and m artificial points y + ∆ 1 , ..., y + ∆ m . We now focus on the generation of a new R U -nondominated point.

Figure 2 . 6 :

 26 Figure 2.6: Illustration of the modified updating step.

  case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.2.2 Specific case: Weight set defined by linear inequalities . . . . . . . . . 53 Representation by a dominance cone . . . . . . . . . . . . . . . . . . . 54 3.3 Application to multi-objective optimization . . . . . . . . . . . . . 55 3.3.1 Direct procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.3.2 Two-stage procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Presentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Superset construction methods . . . . . . . . . . . . . . . . . . . . . . 61 Superset performance estimation . . . . . . . . . . . . . . . . . . . . . 64 3.4 Preference elicitation frameworks . . . . . . . . . . . . . . . . . . . . 65 3.4.1 Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Criteria ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Group ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.4.2 Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.5 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.5.1 Approximated size of weight sets . . . . . . . . . . . . . . . . . . . . . 77 3.5.2 Computation time and number of nondominated points . . . . . . . . 78 3.5.3 Performance of the two-stage procedure . . . . . . . . . . . . . . . . . 79 Difference with the direct procedure . . . . . . . . . . . . . . . . . . . 79 Difference between supersets . . . . . . . . . . . . . . . . . . . . . . . 83 3.5.4 Evaluation of the preferred sets . . . . . . . . . . . . . . . . . . . . . . 83 Consistency of the weight set . . . . . . . . . . . . . . . . . . . . . . . 84 Proportion of nonsupported points in the preferred sets . . . . . . . . 85 3.6 Conclusions and perspectives . . . . . . . . . . . . . . . . . . . . . .

  Weighted sum value of wy i with w 1 between 0.4 and 0.6.

Figure 3 . 2 :

 32 Figure 3.2: Weighted sum value of wy i according to the weight value of w 1 on the intervals [0.4, 0.6] and [0, 1].

Figure 3 . 3 :

 33 Figure 3.3: Illustration of the standard simplex K 3 and an example of a constrained weight set W in R 3 .

Figure 3

 3 Figure 3.7: Graph composed of 5 vertices a, ..., e.

Figure 3 . 8 :Figure 3

 383 Figure 3.8: There are two Pareto nondominated paths (a, b, d, e) and (a, c, d, e).

Figure 3 .

 3 Figure 3.11 depicts an example of sets W (Figure 3.11a) and W ′ (Figure 3.11b).

Figure 3 .

 3 Figure 3.11: Illustration of W and W ′ in a two-stage procedure.

Figure 3

 3 Figure 3.13: Illustration of the construction of a superset by removing constraints of W .

Figure 3

 3 Figure 3.14: Illustration of the construction of a superset by removing constraints of W .

Figure 3

 3 Figure 3.15: Illustration of the construction of a superset by removing constraints of W .

Figure 3 Figure 3

 33 Figure 3.16: Representation of a weight set W with 4 extreme weights.on removing constraints, there are two candidate supersets. These supersets are illustrated

Figure 3 .

 3 Figure 3.18: Illustration of the construction of a superset by creating valid constraints for W .

Figure 3

 3 Figure 3.19: Illustration of random weights in the simplex K 3 .

  When p = 3 and n M = 1, we use supersets of Example 3.5 in Section 3.4.1. W c 2 , defined by (3.11), is indicated by superset c and W d 2 , defined by (3.12), is indicated by superset d . When p = 4 and n M = 2, we use supersets of Example 3.4 in Section 3.4.1. W a 2 , defined by (3.8), is indicated by superset a and W b 2 , defined by (3.9), is indicated by superset b ;

Definition 4 . 1 .

 41 Let W be a weight set in R p ≥ and Y be a set of points in the objective space. For any y, y ′ in Y , yRO

Figure 4 . 1 :

 41 Figure 4.1: Illustration of Example 4.1. y 5 cannot be optimal for any OWA with positive weights.

Figure 4 . 2 :

 42 Figure 4.2: Value of OW A w (y i ) according to the weight value of w 1 on the intervals [0.4, 0.6] and [0, 1].

Figure 4 . 3 :

 43 Figure 4.3: Illustration of the standard simplex K 3 and an example of a constrained weight set W in R 3 .

Figure 4 . 4 :

 44 Figure 4.4: Counter example for the inclusion property in R 3 .

Example 4 . 3 .

 43 We consider the situation of Example 4.1 where 5 alternatives, evaluated on a scale [0, 20], are presented to the DM. Each of these are represented in a bi-objective space by their point and representative point as depicted inFigures 4.5a

  and 4.5b, respectively.

  Representation of y 1 , ..., y 5 in Example 4.1.

Figure 4 .

 4 Figure 4.5: Representation of Y and Y (.) in 4.1.

Proposition 4 . 4 .

 44 Let Y be a set of points in R p . Then, N (Y (.) ) ⊆ N (Y ) (.) .

Figure 4 .

 4 Figure 4.6 depicts an example of sets W (Figure 4.6a) and W ′ (Figure 4.6b).

  Illustration of a set W ′ , superset of W , with 3 extreme weights.

Figure 4 . 6 :

 46 Figure 4.6: Illustration of W and W ′ in a two-stage procedure.

  to 4.9.

Figure 4 .

 4 7 depicts the domination structure of a point y in a biobjective space, corresponding to R O W with the standard simplex K 2 .

Figure 4 . 7 :

 47 Figure 4.7: Domination structure of a point y with W = K 2 .

Figure 4 . 8 :

 48 Figure 4.8: Representation of the weight sets W 1 , W 2 in a biobjective space.

Figure 4 .

 4 Figure 4.9a and Figure 4.9b represent the domination structure of R O W 1 and R O W 2 in the

Figure 4 . 9 :

 49 Figure 4.9: Domination structures corresponding to R O W 1 and R O W 2 in the space of representatives.

  structure corresponding to W 2 in the biobjective space.

Figure 4 .

 4 Figure 4.10: Representation of domination structures corresponding to W 1 and W 2 in the biobjective space.

Figure 4 .

 4 Figure 4.11: Representation of α

Definition 4 .

 4 14. Let Y be a set of points in the objective space. For any y, y ′ in Y , y ≤ L y ′ if and only if for all i = 1, ..., p and y (.) = y ′ (.) .

Proposition 4 .

 4 16. The number of extreme weights of W 2 is p.Proof. From Proposition 3.19.

CHAPTER 4 .

 4 OWA MODEL WITH PARTIAL INFORMATION result on the number of extreme weights of W 3 . Corollary 4.18. The number of extreme weights of W 3 is 2 p-1 . Proof. From Proposition 3.20, with n M = 1 and n L = p -1.

W l 4 = 4 ,

 44 {w ∈ K p : l ≤ orness(w)} (4.17) Proposition 4.19. When l ≥ p-2p-1 , the number of extreme weights of W l 4 is p.Proof. For any weight w ∈ W l i)w i ≥ l ≥ p-2 p-1 . Therefore, we havep i=1 (pi)w i ≥ l ≥ (p -2). i)w i ≥ l ≥ (p -2)

  y 2 n'est pas préféré à y 3 .

  Figure 2

  Figure3

Figure 4

 4 Figure 4

  Figure5

  Figure6

Table 2

 2 .3.

	3-MOAP30 CPU time(s) |N(Y, R)| # Empty
	Pareto	1424.61	6181.4	-
	R U	325.53	443.9	0
	Pareto	4774.81	14679.7	-
	R U	800.71	562.6	0

.1: Average CPU time and number of points for 10 3-MOAP30 instances.

3-MOAP40 CPU time(s) |N(Y, R)| # Empty

Table 2 .

 2 2: Average CPU time and number of points for 10 3-MOAP40 instances.

	3-MOAP50 CPU time(s) |N(Y, R)| # Empty
	Pareto	11753.18	24916.8	-
	R U	1602.90	553.8	0

Table 2 .

 2 3: Average CPU time and number of points for 10 3-MOAP50 instances.

Table 2 .

 2

		49 52	55	507 509 489
	R U	101 92 309	188 171 466

4: Ideal and nadir Points for a 3-MOAP40 instance.

  Figure 3.10: There is one R W -nondominated path (a, c, d, e).

	5.2 6.8	b	4.6 5.4	9.8 12.2	,	9.4 8.6	15 15
	a			d			e
						5.6
	5.2 5.8	c	3.4 3.6			6.4
	Then, we have:

m, where A i , A ′ i are the i th row of A, A ′ , respectively.

Table 3 .

 3 7: CPU time and size of the R W -nondominated sets for MOKP and MOAP instances.

	80	CHAPTER 3. WEIGHTED SUM MODEL WITH PARTIAL INFORMATION
	3-MOKP100	CPU time(s)		|N (Y, R W )|
			Avg.	min	max	Avg.	min	max
	Pareto		642.40	221.00	1764.00	3579.9	1856	6967
	Group ranking (M = 2)	65.28	15.80	82.70	688.0	257	1490
	Group ranking (M = 1) 2	138.44	40.18	334.38	577.5	262	1130
	Criteria ranking	20.45	4.90	60.90	268.5	101	662
	Bounds-20% 2	2.30	0.65	5.35	18.6	14	81
	Bounds-10% 2	0.45	0.15	1.15	6.4	2	15
	4-MOKP40	CPU time(s)		|N (Y, R W )|
			Avg.	min	max	Avg.	min	max
	Pareto		15495.70	227.00 71 800.00	1168.1	430	2117
	Group ranking (M = 3)	314.15	32.80	861.60	355.8	199	566
	Group ranking (M = 2) 2	109.49	19.40	307.70	145.6	97	256
	Criteria ranking	2.91	0.21	6.10	48.5	10	90
	Bounds-20% 2	0.71	0.11	2.62	6.2	2	14
	Bounds-10%	0.10	0.02	0.30	2.4	1	5
	5-MOKP30	CPU time(s)		|N (Y, R W )|
			Avg.	min	max	Avg.	min	max
	Criteria ranking	3.03	0.29	12.10	21.4	10	44
	Bounds-20% 2	7.37	0.13	68.75	7.5	2	40
	Bounds-10% 2	0.28	0.07	1.75	2.9	1	8
	3-MOAP50	CPU time(s)		|N (Y, R W )|
			Avg.	min	max	Avg.	min	max
	Pareto		7982.90	5729.00	9283.00 25193.4 19547 28787
	Group ranking (M = 2)	1239.80	912.00	1993.00	4112.7	2948	5870
	Group ranking (M = 1) 2	3257.16	2145.34	4395.75	5005.2	3606	6191
	Criteria ranking	541.00	368.00	882.00	1578.5	1103	2345
	Bounds-20% 2	84.34	24.82	127.41	83.6	18	211
	Bounds-10% 2	8.61	1.15	26.05	16.9	1	62
	4-MOAP30	CPU time(s)		|N (Y, R W )|
			Avg.	min	max	Avg.	min	max
	Group ranking (M = 3)	43636.39 26598.00 67787.30 24629.5 19473 37088
	Criteria ranking	1257.07	329.00	2846.00	2092.2	772	4128
	Bounds-20% 2	145.94	32.15	421.45	97.0	19	264
	Bounds-10%	5.99	0.63	21.19	8.3	2	21

  CPU time(s) |N (Y, R W )|

	LowerBounds-20%	2.29	38.9
	UpperBounds-20%	2.45	40.5
	LowerBounds-10%	0.44	10.6
	UpperBounds-10%	0.57	11.7
	4-MOKP40	CPU time(s) |N (Y, R W )|
	LowerBounds-20%	0.70	12.8
	UpperBounds-20%	0.62	14.9
	LowerBounds-10%	0.13	3.4
	UpperBounds-10%	0.14	4.2
	5-MOKP30	CPU time(s) |N (Y, R W )|
	LowerBounds-20%	7.36	16.2
	UpperBounds-20%	17.19	17.1
	LowerBounds-10%	0.27	5.3
	UpperBounds-10%	0.28	5.2
	3-MOAP50	CPU time(s) |N (Y, R W )|
	LowerBounds-20%	84.16	219.3
	UpperBounds-20%	63.65	174.9
	LowerBounds-10%	8.59	31.0
	UpperBounds-10%	12.28	39.0
	4-MOAP30	CPU time(s) |N (Y, R W )|
	LowerBounds-20%	145.66	321.8
	UpperBounds-20%	282.37	397.9
	LowerBounds-10%	11.99	33.4
	UpperBounds-10%	12.86	35.5
	Table 3.10: Comparison between two supersets in the two-stage procedure with Bounds-α%.
	3-MOKP100	Size(%) CPU time(s) |N (Y, R W )|
	Group ranking (M = 1) superset c	44.44	134.87	1040.4
	Group ranking (M = 1) superset d	49.96	164.59	1258.0
	4-MOKP40	Size(%) CPU time(s) |N (Y, R W )|
	Group ranking (M = 2) superset a	24.98	109.29	266.9
	Group ranking (M = 2) superset b	33.34	318.59	377.7
	3-MOAP50	Size(%) CPU time(s) |N (Y, R W )|
	Group ranking (M = 1) superset c	44.44	3070.46	7983.7
	Group ranking (M = 1) superset d	49.96	3308.86	8674.9
	Table 3.11: Difference in computation time between two supersets in the two-stage procedure
	with Group Ranking.

  %N S (Y, R W ) %N N S (Y, R W )

	Pareto	5.95	94.05
	Group ranking(M = 2)	14.94	85.06
	Group ranking(M = 1)	13.29	87.71
	Weak ranking	21.89	78.11
	Bounds-20%	60.28	39.72
	Bounds-10%	76.39	23.61
	4-MOKP40	%N S (Y, R W ) %N N S (Y, R W )
	Pareto	20.46	79.54
	Group ranking(M = 3)	31.84	68.16
	Group ranking(M = 2)	48.18	51.82
	Weak ranking	70.45	29.55
	Bounds-20%	90.79	9.21
	Bounds-10%	94.17	5.83
	3-MOAP50
	Pareto	4.66	95.34
	Group ranking(M = 2)	10.31	89.69
	Group ranking(M = 1)	7.75	92.25
	Weak ranking	13.27	86.73
	Bounds-20%	40.88	59.12
	Bounds-10%	74.50	25.50
	Table 3.13: Percentage of supported/nonsupported points for the 3-MOKP100, 4-MOKP40
	and 3-MOAP50 instances.

%N S (Y, R W ) %N N S (Y, R W )

  The representatives of the R O W ′ -nondominated set may be easier to compute than the ones from the R O W -nondominated set and is a superset of the representatives of the R O W -nondominated set by Proposition 4.3. For each representative point y (.) in the R O W ′ -nondominated set, we compute its weighted sum value on all extreme weights of W , that is we compute Ay (.) . These points are filtered by making pairwise comparisons: for any two representatives y (.) and y ′ -dominated by points represented by y (.) and y ′ (.) is discarded from the list of points.

	Stage 2. (.)
	from the R O W ′ -nondominated set, if Ay (.) ≤ Ay ′ (.) , then the points represented by y ′ (.) are
	R O W

Table 4 .

 4 4: Percentage of points in N (Y ) that are not individually represented in N (Y ) (.) .

		% Permutations
	3-MOKP100	0.00
	4-MOKP40	0.00
	3-MOAP50	2.16

Table 4 .

 4

	1 )

5: Number of extreme weights, Size and E W value for weight sets with p = 3.

Table 4 .

 4 6: Number of extreme weights, Size and E W value for weight sets with p = 4.Median superset 4a and Median superset 4b , and Median superset 4c and Median superset 4d have the same size, respectively. However Median superset 4a and Median superset 4b are larger than Median superset 4c and Median superset 4d . Median superset 4a has a better E W value than Median superset 4b , therefore Median superset 4a should computer fewer points than Median superset 4b . Median superset 4c and Median superset 4d have the same size and E W value, therefore they should have similar performances.

	-1 )

Table 4 .

 4

7: Number of extreme weights, Size and E W value for weight sets with p = 5.

  1 )

	Median superset 3a	422.86	758.6 49.98	1.31
	Median 2	423.49	133.9	-	-
	Median superset 3b	175.54	277.4 50.01	7.85
	Median 2	175.75	133.9	-	-
	Median superset 3c	208.42	375.9 44.45	5.41
	Median 2	208.72	133.9	-	-
	Median	382.61	133.9 33.34	9.16
	3-MOAP50	CPU time(s) |N (Y, R O W ) (.) |	Size E W (×10 -1 )
	Median superset 3a	3073.22	2305.4 49.98	1.31
	Median 2	3084.48	233.8	-	-
	Median superset 3b	638.16	291.3 50.01	7.85
	Median 2	638.41	233.8	-	-
	Median superset 3c	1428.26	850.0 44.45	5.41
	Median 2	1432.49	233.8	-	-
	Median	706.76	233.8 33.34	9.16
	Table

Table 4 .

 4 1 ) 10: Comparison between the direct approach and the two-stage procedure.

	Median superset 4a	80.90	124.7 33.34	9.55
	Median 2	80.97	44.4	-	-
	Median superset 4b	112.30	191.2 33.33	0.40
	Median 2	112.39	44.4	-	-
	Median superset 4c	45.10	84.1 24.97	8.18
	Median 2	45.14	44.4	-	-
	Median superset 4d	47.11	89.7 24.99	8.18
	Median 2	47.15	44.4	-	-
	Median	73.40	44.4 16.67	9.95

Table 4 .

 4 11: Comparison between weight sets with similar size and E W value.

	118	CHAPTER 4. OWA MODEL WITH PARTIAL INFORMATION
	3-MOKP100		CPU time(s) |N (Y, R O W ) (.) |	Size E W (×10 -1 )
	Median superset 3a	422.86	758.6 49.98	1.31
	Orness 0.5-1		633.26	960.1 50.02	1.31
	Median superset 3b	175.54	277.4 50.01	7.85
	Orness 0-0.5		175.52	202.6 49.98	7.85
	3-MOAP50		CPU time(s) |N (Y, R O W ) (.) |	Size E W (×10 -1 )
	Median superset 3a	3073.22	2305.4 49.98	1.31
	Orness 0.5-1		5666.89	3693.3 50.02	1.31
	Median superset 3b	638.16	291.3 50.01	7.85
	Orness 0-0.5		316.83	109.1 49.98	7.85

Table 4 .

 4 12: Ideal and nadir representative points for a 3-MOAP50 instance.

	Representative	11	87 161	160 425 567
	Orness 0.5-1	11	87 168	153 425 567
	Orness 0-0.5	84	87 161	160 205 463
	Median	55	87 161	160 162 498
	Optimistic	11	93 174	143 406 567
	Pessimistic	145 157 161	160 162 172

Table 1 -

 1 Temps et nombre de points de l'algorithme moyennés sur 10 instances du problème d'affectation triobjectif 50×50.

		CPU time(s) |N(Y, R)|
	Pareto	11753.18	24916.8
	R U	1602.90	553.8

http://home.ku.edu.tr/~moolibrary/

Computed by a two-stage procedure.

ation algorithms could be tested and compared. This general approach of exploiting partial preference information can also be studied with other aggregation models.

Computed by a two-stage procedure.

Results for the Pareto nondominated set (N (Y )).

Remerciements

 3.5: Estimated size of weight sets with p = 4.

On Tables 3.5 and 3.6, the same observations still hold. Since the difference of size between Group ranking (M=1) superset a and Group ranking (M=1) superset b , when p = 3, is larger than the difference between superset c and superset d when p = 4 (see Table 3.4 and 3.5), the variation should vary accordingly. Numerical experiments confirm these assumptions based on the size of the weight set.

Computation time and number of nondominated points

We gathered CPU times and number of R W -nondominated points in Table 3.7. For each problem type and size, using one of the presented frameworks always reduces substantially the computation time and the corresponding R W -nondominated set has a smaller size than the standard Pareto nondominated set (Proposition 3.2).

Proposition 3.3, stating inclusion between R W -nondominated sets, is verified between Group ranking and Criteria ranking and between Bounds-20% and Bounds-10%. When each weight These values correspond to the ideal and nadir point values, respectively (Definition 1.6). For this purpose, after computing the R W -nondominated sets on one 3-MOAP50 instance, we report the results in Table 3.12. Results on other instances are similar. Table 3.12 illustrates the consistency between the R W -nondominated points and the preference elicitation framework. Consider first Group ranking (M = 1), where f 1 is the most important objective and f 2 , f 3 are the least important objectives. The R W -nondominated set preserves the best performance on f 1 , while significantly improving its worst performance. Conversely, for f 2 and f 3 , the best performances are deteriorated, with the same magnitude, while the worst performances are similar to those on the Pareto nondominated set. Similar observations can be made regarding Group ranking (M = 2). Likewise, Weak ranking deteriorates the best performances on f 2 and f 3 but with different orders of magnitude. Since f 2 is more important than f 3 , the best performance on f 2 is less deteriorated than the best performance on f 3 . On the contrary, the worst performance on f 2 improves more than the worst performance on f 3 , which is also consistent with the Weak ranking framework. We observe that Bounds-20% and Bounds-10% focus on balanced points, which is consistent with the frameworks since the weight sets are centered around the mean weight. Indeed, the best performances are deteriorated with the same magnitude on all three objectives, while the worst performances are improved with the same magnitude on all three objectives. This shows clearly that the preferred set contains the most balanced points. Observe finally that the gap between the ideal and nadir points is consistently smaller for Bounds-10% than for Bounds-20%.

3-MOAP50 instance

Proportion of nonsupported points in the preferred sets

After generating each nondominated set, we used the algorithm presented in [START_REF] Barber | The quickhull algorithm for convex hulls[END_REF] to compute the convex hull of the nondominated set and the proportion in percentage of supported -both extremal and non extremal-and nonsupported nondominated points. Once the R W -nondominated sets are computed, we established the percentage of supported and nonsupported nondominated points in each set.

The drawback of the weighted sum scalarization is avoided as mentioned earlier. In Table 3.13, the percentage of nonsupported points in the R W -nondominated set is always strictly positive. Most weight sets (except Bounds-20% and Bounds-10% in some instances) always lead to at least one nonsupported point. We observe that the more the weight set is constrained the fewer there are nonsupported points. This observation seems natural, since the more you constrain the weight set the more you tend to use a classic weighted sum with precise weights.

Chapter 4

Partial preference on weights: a preference relation based on the ordered weighted average

Chapter abstract

This chapter presents a preference relation based on the ordered weighted average (OWA) and partial information on weights. This preference relation has already been studied in some publications but we especially study this relation in the multi-objective optimization context. Properties are presented in the general case and in the case where the weight set is defined as a polytope. In the latter case, a transformation of the objective functions, based on the extreme weights of the weight set, leads to compute the nondominated set corresponding to the preference relation. The two-stage procedure presented in Chapter 3 is still valid but an estimator of the performance for this two-stage procedure, specific to OWA, is added. Some preference elicitation frameworks are then studied. Numerical experiments are conducted on several instances of the multi-objective knapsack problem and on the multi-objective assignment problem. These experiments show the applicability of the approach and the quality of the returned preferred set. [START_REF] Kaddani | Ordered weighted average model with partial preference information: application to multi-objective optimization[END_REF] which has been submitted for publication.

This chapter has been adapted from

CHAPTER 4. OWA MODEL WITH PARTIAL INFORMATION

Formulation with binary variables

The following formulation has been presented in [START_REF] Boland | Exact procedures for solving the discrete ordered median problem[END_REF], [START_REF] Galand | Exact algorithms for OWA-optimisation in multiobjective spanning tree problems[END_REF] and [START_REF] Fernández | Ordered weighted average combinatorial optimization: Formulations and their properties[END_REF]. We introduce p × p boolean variables t ij , i, j = 1, ..., p.

In order to compute N (Y (.) ), we formulate the following MOO problem.

The constant M is a value greater than all possible differences on one objective between two points y, y ′ . Therefore, we define M as follows.

According to Proposition 4.7, the R O W -nondominated set of problem (1.1) is generated by computing the nondominated set of problem (4.4) which, considering formulation (4.6), is equivalent to the following MOO problem (4.7).

Problem (4.7) is linear if the constraints of the initial problem are linear. Nevertheless, due to the formulation above, the chosen MOO algorithm must be able to handle the binary variables t ij , i, j = 1, ..., p (4.5). The number of objectives of problem (4.7) depends on the number of extreme weights m of the weight set W . The computation time of the optimization could highly increase with a large number of extreme weights. In Chapter 3, a two-stage procedure is proposed in order to improve the performance of the approach. This two-stage procedure can also be used in this context. We remind this procedure hereafter.

Corollary 4.17. The number of extreme weights of W 3 is:

2 , when p is even;

• 3p-1 2 , when p is odd.

Proof. From Proposition 3.21. When p is even and odd, there are p 2 and p-1 2 + 1 groups, respectively. When p is even, each group is composed of two criteria. When p is odd, the first group contains one criterion while all other groups are composed of two criteria.

When p = 3, the number of extreme weights is 4 from Proposition 4.17. We can use both methods presented in Section 3.3.2 to derive supersets with p = 3 extreme weights. Supersets W 3a 3 and W 3b 3 are derived using the method where constraints are removed, whereas superset W 3c 3 is obtained by creating a valid constraint. These are the only supersets that we can create using these methods. As shown in Table 4.2, using the uniform drawing technique, supersets W 3a 3 and W 3b 3 have the same size. Observe, however, that W 3a 3 constrains the weight of the largest objective value (w 3 ), while W 3b 3 constrains the weight of the smallest objective value (w 1 ). Therefore, superset W 3a 3 favors the smallest objective value, while superset W 3b 3 favors the largest objective value. Consequently, we expect W 3b 3 to generate less points than W 3a 3 , as shown with their E W value. Superset W 3c 3 is smaller than W 3a 3 and W 3b 3 but favors the median objective value, in opposition to the largest objective value for W 3b 3 . Since the difference of size is not significant, we could expect W 3c 3 to still generate more points than W 3b 3 in particular.

PREFERENCE ELICITATION FRAMEWORKS

109

When p = 4, the number of extreme weights is 5 from Proposition 4.17. We can use both methods presented in Section 3.3.2 to derive supersets with p = 4 extreme weights. Supersets W 4a 3 , W 4b 3 , W 4c 3 and W 4d 3 are derived using the method where constraints are removed, whereas no superset are obtained by creating valid constraints. These are the only supersets that we can create using these methods.

Supersets W 4a 3 and W 4b 3 have the same size, as shown in Table 4.3, but W 4a 3 favors the largest objective value while W 4b 3 favors the smallest objective value, as shown by their E W value. Therefore we expect W 4a 3 to generate less points than W 4b 3 . Supersets W 4c 3 and W 4d 3 also have the same size. Both weight sets constrain the smallest and largest objective with one constraint. Therefore neither of them seems to favor the smallest or largest objective values more than the other, as shown by their E W value, and we expect W 4c 3 and W 4d 3 to generate a similar number of points. Supersets W 4c 3 and W 4d 3 are smaller than W 4a 3 and W 4b 3 , but do not favor the largest objective value, contrary to W 4a 3 . However the difference of size is more significant than for p = 3, consequently we could expect that W 4c 3 and W 4d 3 compute a smaller number of points than W 4a 3 in particular.

Unimodal weight set

More generally the DM could favour the k th criterion such that w k has always the largest value. Let k = 1, ..., p denote the mode of the weight set.

This framework corresponds to the framework of Group ranking in Chapter 3, Section 3.4, with one objective in M and p-1 objectives in L. From Proposition 3.20, we have the following Proposition 4.20. When u ≤ 1 p-1 , the number of extreme weights of W u 4 is p.

Proof. For any weight w ∈ W u 4 , we have

w i . Thus, we deduce the

Consequently, W u 4 is defined by an irredundant system of p inequality constraints: orness(w) ≤ u and w i ≥ 0, i = 1, ..., p -1, and the normalization constraint. The result follows by Proposition 3.17.

The extreme weights of W u 4 are the feasible basic solutions of polytope W u 4 . A basic solution is the solution of a system composed of p -1 inequality constraints of W u 4 set to equality completed by the normalization constraint. We get the extreme weights by solving these p systems. The extreme weights of W u 4 are given below.

Observe that for p = 3, W l 4 and W u 4 have p = 3 extreme weights for l = 0.5 and u = 0.5, respectively.

Numerical experiments

We performed our experiments using the generic algorithm presented in [START_REF] Kirlik | A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems[END_REF]. This algorithm generates all nondominated points for multi-objective discrete optimization problems. We used the code provided by the authors 1 . We have generated our results on two MOCO problems: the Multi-Objective Knapsack Problem (MOKP) and the Multi-Objective Assignment Problem (MOAP), presented in Section 1.1.6. The parameters used to generate instances of MOKP and MOAP are described as follows:

• We tested on uncorrelated instances of MOKP and weights and profits of items are random integers uniformly drawn in the interval [1, 1000]. Let ω i , i = 1, ..., n, denote the weights of the items, the weight capacity of the knapsack is set to

• The objective costs of MOAP instances are random integers uniformly drawn in the interval [1,20].

For MOKP we used the following instance sizes:

• p = 3 and n = 100 (3-MOKP100),

Perspectives Summary

We focused in this thesis on integrating preference information within MOO algorithms. This was motivated by the double fact that generating the whole nondominated set is both costly and often irrelevant. We proposed to define partial preference relations to narrow the Pareto nondominated set to a preferred set based on preference information given by the DM. We put the emphasis on the application of these preference relations in MOO.

We first presented a preference relation based on requirement and tolerance thresholds that translate the Pareto dominance cone. This preference relation is based on determinining a combination of improvements and deteriorations that corresponds to a situation of dominance between two solutions. This provides an alternative framework to define trade-offs, that can handle heterogeneous objective scales easily since the improvements and deterioration can be determined on each objective individually. This not necessarily transitive preference relation defines several situations of dominance based on constant and variable thresholds. We proposed an adaptation of a discrete MOO algorithm to generate the corresponding preferred set. This adaptation shows interesting results on MOAP instances. The returned preferred sets are consistent with the information provided by the DM and their computation time is reduced compared to the computation time of the Pareto nondominated set.

The two other preference relations are based on scalarizing functions, weighted sum and OWA respectively, with partial preference information on weights. When the weight set is a polytope, the approach consists in generating the nondominated set of a new multi-objective optimization problem, where the number of objectives corresponds to the number of extreme weights of the weight polytope. In particular, the preference relation based on the weighted sum does not need a specific adaptation of a MOO algorithm and can thus be applied with any MOO algorithm. When the number of extreme weights is larger than the original number of objectives, the computation time may increase, even if the number of returned solutions is substantially smaller than for the Pareto nondominated set of the original multi-objective problem. In this case, we propose a two-stage procedure to improve the computation time. This two-stage procedure generates a superset of the desired preferred set and then filters a posteriori this superset. In order to discriminate between various candidate supersets, we propose an a priori performance estimator which aims at selecting the superset that should have the lowest computation time. The performance estimator in the case of the weighted sum is consistent with the numerical experiments, whereas the performance estimator in the case of the OWA can be ameliorated. These preference relations show convincing results on MOCO problems in terms of computation time and quality of the returned preferred set.

Considering some important features of some optimization problems at DCNS like ,e.g.,

Résumé

Les problèmes d'optimisation multi-objectifs mènent souvent à considérer des ensembles de points nondominés très grands à mesure que la taille et le nombre d'objectifs du problème considéré augmentent. Générer l'ensemble des points non-dominés demande des temps de calculs prohibitifs. De plus, la plupart des solutions correspondantes ne sont pas pertinentes pour un décideur. Une autre approche consiste à utiliser des informations de préférence avant l'optimisation, ce qui produit une ou un nombre très limité de solutions avec des temps de calcul réduits. Néanmoins, cela nécessite la plupart du temps l'élicitation d'informations préférentielles précises. Cette élicitation est souvent difficile pour un décideur et en partie arbitraire, ce qui peut amener à ne pas considérer certaines solutions intéressantes. Une approche intermédiaire consiste à raisonner avec des relations de préférences construites à partir d'informations partielles de préférence. Nous présentons dans cette thèse plusieurs modèles de préférences partielles : une relation de préférence basées sur des seuils, une relation de préférence basée sur la somme pondérée avec information partielle sur les poids et une relation de préférence basée sur la somme pondérée ordonnée avec information partielle sur les poids. Nous sommes intéressés par la génération de l'ensemble des points préférés, défini comme étant les points non-dominés selon ces relations. Nous donnons certaines propriétés de ces relations de préférences et présentons des adaptations d'algorithmes d'optimisation discrète multi-objectifs pour générer l'ensemble des points préférés. Les expérimentations sur des problèmes d'optimisation combinatoires multi-objectifs démontrent la pertinence de notre approche aussi bien en terme de temps de calcul que de qualité des points générés.

Mots-clés optimisation multi-objectifs, relation partielle de préférence, problème d'optimisation combinatoire multi-objectifs.

Abstract

Multi-objective optimization problems often lead to large nondominated sets, as the size of the problem or the number of objectives increases. Generating the whole nondominated set requires significant computation time, while most of the corresponding solutions are irrelevant to the decision maker. Another approach consists in obtaining preference information and integrating it a priori, which reduces the computation time and produces one or a very limited number of more focused solutions. This requires, however, the elicitation of precise preference parameters most of the time, which is often difficult and partly arbitrary, and might discard solutions of interest. An intermediate approach consists in using partial preference models.

In this thesis, we present several partial preference models: a preference relation based on thresholds, a preference relation based on the weighted sum aggregation where weights are not precisely defined, and a preference relation based on the ordered weighted aggregation operator where weights are not precisely defined. We give some properties of these preference relations and define the set of preferred points as the set of nondominated points with respect to these relations. We provide an efficient and generic way of generating these preferred sets in multi-objective combinatorial optimization problem using discrete multi-objective optimization algorithms. This approach shows competitive performances both on computation time and quality of the generated preferred sets.