Nawal Benabbou
email: nawal.benabbou@lip6.fr

Hugo Martin
email: hugo.martin@lip6.fr

Patrice Perny
email: patrice.perny@lip6.fr

Min Cost Improvement and Max Gain Stability in Multicriteria Sorting Methods on Combinatorial Domains

Keywords: Multicriteria Sorting Method, Multi-Objective Combinatorial Optimization, Min Cost Improvement, Max Gain Stability

Various multicriteria sorting methods have been proposed in the literature to assign the feasible alternatives into predefined categories. We consider here problems involving a set of totally ordered categories representing different achievement levels in the satisfaction of criteria. As in many existing methods, the assignment rule of an alternative to a category is based on the comparison of its performance vector to reference profiles defining lower bounds of the categories. Within this standard setting we address a new problem that consists in finding how to modify a given solution, within a combinatorial set of alternatives, to upgrade it in the upper category (or higher) at minimum cost. We also consider the problem of identifying the sequence of solutions that minimize the total cost while satisfying some budget constraint at every step, and the problem of determining how to modify the current solution to save money while staying in the same category. We first propose a general approach based on mixed integer (linear or quadratic) programming to solve these problems. Then, we implement this approach on various multiobjective combinatorial problems, such as multi-agent assignment problems and multiobjective knapsack problems. Numerical tests are provided to establish the feasibility of the approach on instances of different sizes.

Introduction

In the field of multicriteria decision making, it is usual to distinguish different types of decision problems according to the nature of the recommendation sought, see e.g., [START_REF] Roy | Multicriteria methodology for decision aiding[END_REF]. Besides choice and ranking problems that are very frequent in practice and that motivate a large number of contributions in the field of multicriteria decision aid, there are other problems known as sorting problems where the goal is to assign the alternatives to predefined categories (ordered or not). One major difference with choice and ranking problems lies in the aim of defining an absolute evaluation system. In sorting problems, we are not merely interested in the relative value of the alternatives but also in their instrinsic qualities. What really matters is how alternatives compare to norms defining the categories. Very often, the categories are totally ordered and in this case the norms can be represented by different reference levels on an overall utility scale (see the UTADIS method [START_REF] Jacquet-Lagreze | An application of the UTA discriminant model for the evaluation of r & d projects[END_REF]) or by different reference vectors in the space of criteria (different achievement levels in the satisfaction of criteria, as in the ELECTRE TRI method [START_REF] Moscarola | Procédure automatique d'examen de dossiers fondée sur une segmentation trichotomique en présence de critères multiples[END_REF][START_REF] Yu | Aide multicritère à la décision dans le cadre de la problématique du tri: concepts, méthodes et applications[END_REF]). In other cases, categories are not ordered (or only partially ordered) and represent different types of alternatives characterized by specific combinations of features [START_REF] Fodor | The use of fuzzy preference models in multiple criteria choice, ranking and sorting[END_REF][START_REF] Henriet | Systèmes d'évaluation et de classification multicritères pour l'aide à la décision: Construction de modèles et procédures d'affectation[END_REF][START_REF] Léger | A multicriteria assignment procedure for a nominal sorting problematic[END_REF].

Multicriteria sorting methods are useful for decision support because they provide intrinsic evaluations of the alternatives (objects, projects, candidates). They allow to partition the set of alternatives into specific classes corresponding to different types of values and norms, that may receive different treatments or lead to different decisions. Moreover, the assignment of an alternative to a category is easily explainable because it is based on the comparison of the alternative to reference norms. These norms can be explicited as well as the criteria and the rule used to make the comparisons, and can be used as a support to explain the final decisions.

The multicriteria sorting problem has motivated various contributions in different directions. Different versions of the initial ELECTRE TRI method have been proposed and studied, see e.g., [START_REF] Almeida-Dias | A multiple criteria sorting method where each category is characterized by several reference actions: The ELECTRE TRI-nC method[END_REF][START_REF] Bouyssou | On the relations between ELECTRE TRI-B and ELEC-TRE TRI-C and on a new variant of ELECTRE TRI-B[END_REF][START_REF] Dias | ELECTRE TRI-C : A multiple criteria sorting method based on characteristic reference actions[END_REF][START_REF] Fernández | ELECTRE TRI-nB: A new multiple criteria ordinal classification method[END_REF][START_REF] Leroy | Learning the parameters of a multiple criteria sorting method[END_REF]. In addition, other multicriteria sorting procedures relying on similar principles have been proposed, offering new variants and some sophistications [START_REF] Doumpos | Multicriteria decision aid classification methods[END_REF][START_REF] Greco | Rough sets methodology for sorting problems in presence of multiple attributes and criteria[END_REF][START_REF] Marichal | Sorting multi-attribute alternatives: The tomaso method[END_REF][START_REF] Massaglia | N-tomic: a support system for multicriteria segmentation problems[END_REF][START_REF] Zopounidis | Multicriteria classification and sorting methods: A literature review[END_REF]. Moreover, the sorting problem has been extended to the case of fuzzy categories and some multicriteria filtering procedures based on the comparison of alternatives to reference points have been proposed to define the membership of any alternative to any category [START_REF] Belacel | Multicriteria assignment method PROAFTN: Methodology and medical application[END_REF][START_REF] Fodor | The use of fuzzy preference models in multiple criteria choice, ranking and sorting[END_REF][START_REF] Greco | Fuzzy extension of the rough set approach to multicriteria and multiattribute sorting[END_REF][START_REF] Perny | Multicriteria filtering methods based on concordance and non-discordance principles[END_REF]. Then the axiomatic fundations of sorting methods have been studied, especially in the case of non-compensatory comparison methods based on a weighted majority principle [START_REF] Bouyssou | An axiomatic approach to noncompensatory sorting methods in mcdm, i: The case of two categories[END_REF][START_REF] Bouyssou | An axiomatic approach to noncompensatory sorting methods in mcdm, ii: More than two categories[END_REF][START_REF] Greco | Axiomatization of utility, outranking and decision rule preference models for multiple-criteria classification problems under partial inconsistency with the dominance principle[END_REF]. Another stream of research on sorting methods concerns the supervised learning of preference parameters used in such methods, typically the weights of criteria, the preference thresholds and/or the reference levels or reference points used to define the categories. Various methods have been proposed for the automatic learning or the interactive elicitation of these parameters from assignment examples, e.g., [START_REF] Benabbou | Incremental elicitation of choquet capacities for multicriteria choice, ranking and sorting problems[END_REF][START_REF] Greco | Multiple criteria sorting with a set of additive value functions[END_REF][START_REF] Leroy | Learning the parameters of a multiple criteria sorting method[END_REF][START_REF] Sobrie | Learning a majority rule model from large sets of assignment examples[END_REF][START_REF] Zheng | Learning criteria weights of an optimistic ELECTRE TRI sorting rule[END_REF].

Beyond these works that are still very active, other questions of interest concern post-assignment analysis aiming at investigating the possibility of preserving or improving the level of performance of a given solution or to find the best possible modifications leading to achieve a target level. These questions that have much importance in practice have recently led to various interesting proposals. Let us mention the post-factum analysis [START_REF] Ciomek | Predictive analytics and disused railways requalification: Insights from a post factum analysis perspective[END_REF][START_REF] Kadziński | Post factum analysis for robust multiple criteria ranking and sorting[END_REF] aiming to highlight the minimal improvements that would warrant the feasibility of a currently impossible outcome or the maximal deteriorations that alternatives can afford to maintain a target result. A similar concern is present in the literature on stepwise benchmarking [START_REF] Fang | Centralized resource allocation based on efficiency analysis for step-by-step improvement paths[END_REF][START_REF] Ghahraman | A learning ladder toward efficiency: Proposing network-based stepwise benchmark selection[END_REF][START_REF] Petrović | An ELECTRE-based decision aid tool for stepwise benchmarking: An application over eu digital agenda targets[END_REF][START_REF] Petrović | Supporting performance appraisal in ELECTRE based stepwise benchmarking model[END_REF] that deals with finding an optimal improvement path for objects, units or entities and to provide recommendations for stepwise improvement.

In this paper, we focus on similar issues for multi-criteria evaluation problems in which the overall value of a solution is defined by its assignment to a category using a sorting procedure (each category representing a clearly identified level of performance). More precisely, we consider the following questions:

1. The Min Cost Improvement problem: given a feasible solution of a multiobjective optimization problem, assigned to a given category by a sorting procedure, find the min cost modifications of this solution that will lead to a new feasible solution belonging to an upper category targeted by the decision maker.

2. The Max Gain Stability problem: given a feasible solution of a multiobjective optimization problem, assigned to a given category by a sorting procedure, find a new solution in the same category allowing the maximal gain (or cost saving).

The Min Cost Improving

Sequence problem: given a feasible solution x 0 of a multiobjective optimization problem, and a fixed number of steps h, find the sequence of solutions (x 0 , . . . , x h ) that minimizes the total cost among those with x h belonging to the category targeted by the decision maker.

These questions which correspond to very natural practical concerns lead to new optimization problems that must be formulated and solved. The closest work we know on such questions is a recent work on the "Inverse Multicriteria Sorting Problem (IMSP)" [START_REF] Mousseau | Inverse multiple criteria sorting problem[END_REF] but the framework is a bit different. Starting from a given alternative, it is assumed in the IMSP that various possible actions can modify the performance of this alternative and the aim is to find the combination of actions that will allow a min cost improvement, or a max improvement for a given cost. Hence, the admissible modifications of solutions are not imposed by the structure of the set of alternatives but by external actions that could directly modify the criterion values of the alternative under consideration.

As far as we know, very few contributions on this subject address these questions on combinatorial domains. However such questions may also appear in multiobjective combinatorial optimization problems [START_REF] Ehrgott | Multicriteria optimization[END_REF][START_REF] Ehrgott | A survey and annotated bibliography of multiobjective combinatorial optimization[END_REF], for example to improve the overall quality of a solution to a multiobjective transportation problem aimed at supplying stores from factory warehouses, to increase the efficiency or satisfaction of a team by modifying the assignment of tasks incumbent on each individual, or to improve the value of a group of objects or individuals selected from a set of potential candidates under a budget constraint (multiobjective knapsack problem). When the list of feasible solutions is not explicit, it is much harder to explore the possible solutions that belong to the target category, and this makes the search of the most adequate improvements much more complex. In particular, when the set of feasible alternatives has a combinatorial structure, finding optimal improvements from a given solution leads to combinatorial optimization problems that must be formulated and solved. This paper aims to address these problems. This is why, in this paper, we consider the case of a multiobjective combinatorial optimization problem where the value of every feasible solution is defined by a multicriteria sorting procedure involving a list of pre-defined ordered categories. Any modification of a solution may generate losses or gains and is limited by feasibility constraints defining the set of admissible solutions. Under these assumptions, we want to propose computational models to answer the two above mentioned questions.

The paper is organized as follows: first, we present the multicriteria sorting method studied in the paper (Section 2). Then, we introduce the min cost improvement, max gain stability and the min cost improving sequence problems, and provide mixed integer (linear/quadratic) formulations to efficiently solve these problems (Section 3). Finally, we provide numerical results for three multicriteria sorting problems on combinatorial domains (transportation, assignment, and knapsack problems) showing the practical efficiency of our approach (Section 4).

The Multicriteria Sorting Method

In this paper, we consider sorting problems where alternatives/solutions are evaluated with respect to n criteria to be maximized. The set of alternatives can be implicitly defined as the set of all feasible solutions of a multi-objective combinatorial optimization problem, as defined here below:

max f (x) = W x s.t. Ax ≤ b
x ∈ N m where x T = (x 1 , . . . , x m ) ∈ N m is a solution vector, W ∈ Z n×m is a matrix allowing the definition of performance vectors from solution vectors, f (x) T = (f 1 (x), . . . , f n (x)) ∈ Z n is the performance vector giving the evaluation of x with respect to every criterion i ∈ N = {1, . . . , n}, and A ∈ Z d×m and b ∈ Z d are matrices that jointly impose d ∈ N feasibility constraints on solutions. The set of all feasible solutions will be denoted by X in the sequel.

In sorting problems, alternatives are to be assigned to categories based on their performance vector. Here we consider a set of q categories denoted by K = {K 1 , . . . , K q }, where K 1 is the best category and K q is the worst one. The bounds of categories are defined using a set R of multicriteria reference profiles R = {r 0 , r 1 , . . . , r q }, where r = (r 1 , . . . , r n ) ∈ R n defines the lower boundary of category K , ∈ {1, . . . , q}, and r 0 ∈ R n represents a top performance profile chosen to bound above all criterion values. These reference profiles are defined in such a way that r r +1 for all ∈ {0, . . . , q -1}, where is the strict Pareto dominance relation defined as follows: a b if and only if a i > b i for all i ∈ N . At some point, we will also consider the weak Pareto dominance (i.e. a b if and only if a i ≥ b i for all i ∈ N ) and the Pareto dominance (i.e. a b if and only if a i ≥ b i for all i ∈ N and a i > b i for some i ∈ N ).

In this context, the general principle of preference-based assignment methods is to assign alternatives to categories according to the following rule:

Assignment Rule ( * ): Alternative x ∈ X is assigned to category K if and only if x is preferred to profile r and x is not preferred to profile r -1 .

We focus here on the assignment method introduced in [START_REF] Perny | Multicriteria filtering methods based on concordance and non-discordance principles[END_REF] which is a soft implementation of this principle using valued preference relations and fuzzy membership to categories. This sorting method is based on the following preference indices:

Monocriterion preference index: For any criterion i ∈ N , the preference index P i (x, r ) of any alternative x ∈ X with respect to any reference profile r ∈ R is defined by:

P i (x, r ) =        1 if f i (x) -r i > γ + i f i (x) -r i -γ - i γ + i -γ - i if γ - i < f i (x) -r i ≤ γ + i 0 if f i (x) -r i ≤ γ - i (2)
This index measures the credibility of the statement "alternative x is better than profile r with respect to criterion i". The variation of P i (x, r ) as the performance difference f i (x)-r i increases is represented in Figure 1. This preference index is maximal (i.e. equals 1) when the difference f i (x) -r i is larger than γ + i the preference threshold representing the minimal performance difference compatible with a strict preference. This index is minimal (i.e. equals 0) when the difference f i (x) -r i is below γ - i the indifference threshold representing the maximal performance difference compatible with an indifference (absence of preference). Between these two thresholds, there is an area where the decision maker may hesitate between strict preference and indifference; in

f i (x) -r i P i (x, r ) 1 - 0 | γ - i | γ + i Fig. 1: Preference index P i (x, r ) as a function of f i (x) -r i .
this area, the monocriterion preference index grows linearly with the difference f i (x) -r i (see Figure 1). We assume here that preference and indifference thresholds are part of the definition of the criterion scale and they are defined in such a way that γ + i > γ - i holds. These monocriterion indices are then aggregated into an overall preference index P (x, r ) using an aggregation function ψ θ parameterized by θ:

Overall preference index: The overall preference index P (x, r ) of any solution x ∈ X with respect to any reference profile r ∈ K is defined by: P (x, r ) = ψ θ (P 1 (x, r ), . . . , P n (x, r ))

(

This overall index represents the strength of arguments supporting the statement "alternative x is better than profile r ". A standard choice for ψ θ is a compromise operator, i.e. an aggregation function that verifies min i∈N {a i } ≤ ψ θ (a) ≤ max i∈N {a i } for all a = (a 1 , . . . , a n ) ∈ R n . When considering such an operator, P (x, r ) necessary belongs to [0, 1]. It is equal to 1 when the criteria are unanimously in favor of strict preference, and equals 0 when they are unanimously against preference. Moreover, ψ θ is assumed to be compatible with weak Pareto-dominance, i.e. ψ θ (a) ≥ ψ θ (b) for all a, b ∈ R n such that a b. In this paper, a special focus will be placed on the discrete Choquet integral, which is a family of (non-linear) aggregation functions that is very popular in multicriteria decision making as it enables to model possible synergies between criteria [START_REF] Grabisch | The application of fuzzy integrals in multicriteria decision making[END_REF][START_REF] Grabisch | Aggregation functions[END_REF]. These aggregation functions are specified by a capacity function θ : 2 N → [0, 1] such that θ(∅) = 0, θ(N ) = 1 and θ(A) ≤ θ(B) for all A ⊂ B ⊆ N , which defines the weight attached to any coalition of criteria [START_REF] Grabisch | Set functions, games and capacities in decision making[END_REF]. The discrete Choquet integral assigns to any performance vector a = (a 1 , . . . , a n ) ∈ R n the following value:

ψ θ (a) = n i=1 a (i) -a (i-1) θ(A (i) ) with a (0) = 0,
where (•) is a permutation such that a (i-1) ≤ a (i) for all i ∈ N (sorting the components of vector a in increasing order) and given in Table 1. For a = (3, 2, 5), we have

A (i) = {(i), . . . , (
ψ θ (a) = (2 -0) × θ({1, 2, 3}) + (3 - 2) × θ({1, 3}) + (5 -3) × θ({3}) = 2 × 1 + 1 × 0.7 + 2 × 0.3 = 3.3.
The family of Choquet integrals includes the weighted sums (when θ is additive, i.e. θ(A∪B) = θ(A)+θ(B)) and OWA aggregators (when θ is symmetric, i.e. θ(A) = θ(B) for all A, B s.t. |A| = |B|) as a special case. Moreover, using a convex capacity enables to model preferences for well-balanced preference profiles (see e.g., [START_REF] Chateauneuf | Diversification, convex preferences and nonempty core in the Choquet expected utility model[END_REF]). Moreover, these subclasses are very interesting from a computational perspective since efficient linearization techniques have been proposed for these functions [START_REF] Chassein | Alternative formulations for the ordered weighted averaging objective[END_REF][START_REF] Lesca | LP solvable models for multiagent fair allocation problems[END_REF][START_REF] Ogryczak | On solving linear programs with the ordered weighted averaging objective[END_REF][START_REF] Ogryczak | On efficient WOWA optimization for decision support under risk[END_REF].

Finally, the membership indices and the assignment rule are defined as follows:

Membership index: The membership index c (x) of any alternative x ∈ X to any category K ∈ K is defined by:

c (x) = min P (x, r ), 1 -P (x, r -1 ) (4)
This index measures the membership of any alternative x to any category K on the [0, 1] scale. Equation ( 4) is a translation in multi-valued logic of the assignment rule ( * ): in this equation, 1 -P (x, r -1 ) is used for the negation and the min t-norm for the conjunction. For any fixed alternative x, c (x) seen as a function of is unimodal, with a maximum at least equal to 1/2 (for more details see [START_REF] Perny | Multicriteria filtering methods based on concordance and non-discordance principles[END_REF]).

Assignment rule ( * * ): Alternative x ∈ X is assigned to category K if and only if is the smallest index such that c (x) = max ∈{1,...,q} c (x).

In the sequel, c(x) will denote the index of the category in which x is assigned.

This preference-based sorting method is typical of the "compare then aggregate" approach: to determine the category of any alternative x ∈ X , we first compare x to all reference profiles r ∈ R by considering each criterion separately, leading to monocriterion indices P i (x, r ), i ∈ N . These indices are then aggregated using (3) to define P (x, r ) and the membership of x to any category K by [START_REF] Bouyssou | An axiomatic approach to noncompensatory sorting methods in mcdm, i: The case of two categories[END_REF]. The advantage of this approach lies in the use of reference vectors r instead of scalar thresholds on aggregated values, which allows a finer control in the definition of category boundaries: two alternatives having the same "average" performance but different performance vectors may be assigned to different categories, as shown in the following example:

Example 1 Consider a sorting problem with 3 criteria f 1 , f 2 , f 3 and 3 reference profiles r 0 , r 1 , r 2 (given in Table 2) allowing the definition of two categories K 1 and K 2 . We use the same preference threshold γ + i = 1 and indif- [START_REF] Marichal | Sorting multi-attribute alternatives: The tomaso method[END_REF] ference threshold γ - i = 0 for all criteria i ∈ N = {1, 2, 3}. We aggregate the preference indices using a Choquet Integral ψ θ with the capacity θ defined as follows (Table 3):

f 1 f 2 f 3 r 0 30
∅ {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3} θ 0 0.2 0.1 0.3 0.4 0.7 0.6 1 Table 3: Capacity θ used in Example 1.
Consider 2 alternatives x, y with the following performance vectors: f (x) = [START_REF] Bouyssou | On the relations between ELECTRE TRI-B and ELEC-TRE TRI-C and on a new variant of ELECTRE TRI-B[END_REF][START_REF] Doumpos | Multicriteria decision aid classification methods[END_REF][START_REF] Fodor | The use of fuzzy preference models in multiple criteria choice, ranking and sorting[END_REF] and f (y) = [START_REF] Chassein | Alternative formulations for the ordered weighted averaging objective[END_REF][START_REF] Bouyssou | On the relations between ELECTRE TRI-B and ELEC-TRE TRI-C and on a new variant of ELECTRE TRI-B[END_REF][START_REF] Grabisch | Aggregation functions[END_REF]. Note that alternatives x and y would be indiscernible after using ψ θ as a direct scalarization function since they have the same aggregated value:

ψ θ (f (x)) = 6 + (11 -6) × 0.6 + (16 -11) × 0.3 = 10.5 and ψ θ (f (y)) = 6 + (7 -6) × 0.6 + (20 -7) × 0.3 = 10.5.
Let us compare x and y indirectly using reference profiles r 1 , r 2 and r 3 . Using Equations ( 3) and ( 4), we obtain the following overall preference indices and membership values: For example, using Equation (3), P (x, r 1 ) is obtained as follows:

P (•, r 0 ) P (•, r 1 ) P (•, r 2 ) c 1 (•) c 2 (•) x 0 0.6 1 0.6 0.4 y 0 0.3 1 0.3 0.7
P 1 (x, r 1 ) = 0 (since f 1 (x) -r 1 1 = 6 -11 ≤ 0 = γ - 1
), P 2 (x, r 1 ) = 1 and P 3 (x, r 1 ) = 1, and

P (x, r 1 ) = ψ θ (0, 1, 1) = 0 + (1 -0) × θ({2, 3}) + (1 -1) × θ({3}) = 0.6.
Furthermore, using Equation (4), we have c 1 (x) = min{P (x, r 1 ), 1 -P (x, r 0 )} = min{0.6, 1-0} = 0.6. Thus x is assigned to category K 1 (i.e. c(x) = 1) whereas y is assigned to category K 2 (i.e. c(y) = 2); thus x obtains a better position than y in this example. Moreover, it can easily be checked that y remains in K 2 when y 1 increases from 20 to 30, although its aggregated value ψ θ (y) increases: there is no point in improving y 1 since it already exceeds r 1 1 while the weaknesses of y on criteria 2 and 3 remain. This illustrates the non-compensatory nature of this sorting procedure, where the difference of performances does not play any role beyond a given threshold.

Optimization Problems and Integer Linear Formulations

In this section, we study three optimization problems in which the decision maker wants to move from a given solution to another feasible solution of a given multi-objective optimization problem in order to achieve a target level efficiently, namely the Min Cost Improvement, Max Gain Stability and the Min Cost Improving Sequence problems.

The Min Cost Improvement Problem

Given a solution x ∈ X , we consider the problem of moving from x to another solution y ∈ X in order to enter into a higher category at a minimal cost. This optimization problem, called Min Cost Improvement (MCI) problem, can be formulated as follows: min g(x, y)

(P M CI ) : s.t. c(y) ≤ c(x) -1 Ay ≤ b (5a) (5b) y ∈ N m (5c)
where g : X × X → R is a real-valued function giving the cost of moving from a given solution x ∈ X to any another solution y ∈ X , Equation (5a) ensures that y is assigned to a strictly higher category than x, and Equations (5b-5c) are the feasibility constraints. Given any solution x ∈ X , the optimal solution y * of problem P M CI is the solution that improves x at a minimal cost. When the decision maker does not only wish to enter into a higher category but targets a given category K with < c(x) -1, Equation (5a) must be replaced by the constraint c(y) ≤ . For illustration purposes, an instance of the MCI problem is given below.

Example 2 Consider a knapsack problem where the set O = {o 1 , o 2 , o 3 } of objects/items is evaluated with respect to 2 additive criteria f 1 , f 2 as follows 1 :

f 1 f 2 o 1 2 2 o 2 4 1 o 3 1 3
Table 5: The performance vectors attached to objects in Example 2.

Any solution can be represented by a binary vector x = (x 1 , x 2 , x 3 ) where x i = 1 if and only if object o i is selected, and the knapsack constraint only imposes 1 Additive means that the value of a set of objects is the sum of the values of its elements.

that no more than 2 objects are selected. Moreover, for any two solutions x, y, let us assume that the cost g(x, y) of moving from x to y is defined by:

g(x, y) = |x 1 -y 1 | + |x 2 -y 2 | + |x 3 -y 3 |
penalizing solutions that are far from x in the decision space. Now consider the multicriteria reference profiles given in Table 2. These reference profiles allow the definition of two categories for this problem. Finally, assume that the preference and indifference thresholds are respectively given by γ + 1 = γ + 2 = 1 and γ - 1 = γ - 2 = 0, and that the overall indices are obtained by aggregating monocriterion preference indices using the weighted sum ψ θ defined by ψ θ = θf 1 (x)+(1-θ)f 2 (x) with θ = 2/3. In this problem, there are only seven feasible solutions, denoted by x j , j ∈ {0, . . . , 6}, with the following overall preference indices and membership values: Thus x 0 , x 1 , x 3 and x 5 belong to K 2 (the worst category) whereas x 2 , x 4 and x 6 belong to K 1 (the best category). If x 1 is the current solution, then x 4 is the unique optimal solution of the MCI problem (since we have g(

f 1 f 2 r 0 6 6 r 1 3 2 r 2 -1 -1
f 1 f 2 P (•, r 0 ) P (•, r 1 ) P (•, r 2 ) c 1 (•) c 2 (•) c(•) x 0 = (0, 0, 0) 0 0 0 0 1 0 1 2 x 1 = (1, 0, 0) 2 2 0 0 1 0 1 2 x 2 = (0, 1, 0) 4 1 0 2/3 1 2/3 1/3 1 x 3 = (0, 0, 1) 1 3 0 1/3 1 1/3 2/3 2 x 4 = (1, 1, 0) 6 3 0 1 1 1 0 1 x 5 = (1, 0, 1) 3 5 0 1/3 1 1/3 2/3 2 x 6 = (0, 1, 1) 5 4 0 1 1 1 0 1
x 1 , x 4 ) = 1 < g(x 1 , x 2 ) = 2 < (x 1 , x 6 ) = 3). If instead x 3
is the current solution, then x 6 is the unique optimal solution (as

g(x 3 , x 6 ) = 1 < g(x 3 , x 2 ) = 2 < g(x 3 , x 4 ) = 3).

The Max Gain Stability Problem

Similarly, in a context where any solution has a cost, we consider the problem of reducing the cost while staying in the same category. This amounts to maximizing the gain or cost saving to pass from the current solution x to another solution y ∈ X . This problem named Max Gain Stability (MGS) can be formulated as follows for any x ∈ X : max g(x, y)

(P M GS ) : s.t. c(y) ≤ c(x) Ay ≤ b (6a) (6b) y ∈ N m (6c)
where g : X × X → R is a real-valued function defining the gains and Equation (6a) ensures that y is at least as good as x. When the decision maker is not against reaching a given lower K (with > c(x)) to maximize her gain, then Equation (6a) must be replaced by the constraint c(y) ≥ . Note that the formulation of the MGS problem is very similar to that of the MCI problem and therefore can be solved using the same tools. An instance of the MGS problem is given below.

Example 3 Let us come back to Example 2 and assume that every object o k ∈ O has a market price π k ∈ R + so that the gain g(x, y) obtained when moving from a given solution x to another solution y is simply defined by:

g(x, y) = π 1 (x 1 -y 1 ) + π 2 (x 2 -y 2 ) + π 3 (x 3 -y 3 )
In that case, for any current solution x ∈ K 1 , the unique optimal solution of the MGS problem is x 2 = (0, 1, 0), and for any current solution x ∈ K 2 , the unique optimal solution is trivially x 0 = (0, 0, 0).

The Min Cost Improving Sequence Problem

In some situations, a large improvement of the current solution may be unfeasible in one step due to various reasons, for instance because it requires a prohibitive amount of resources in a short period of time or because it induces too important changes that may have significant reconfiguration costs. In order to cope with such situations, we now consider problems where the decision maker wishes to reach a given higher category in possibly several steps at a minimal cost. The aim is therefore to determine which are the proper steps to reach the targeted category optimally. More formally, we are given:

x 0 : solution at time 0 (current solution)

- * : index of the target category h: number of periods allowed to achieve the goal (horizon)

β 1 , . . . , β h : available budget for each period A feasible solution to the Min Cost Improving Sequence Problem (MCIS) is a sequence (x 1 , . . . , x h ) that satisfies the following constraints:

-Ax t ≤ b for all t ∈ {1, . . . , h} (i.e. x t ∈ X )

c(x h ) ≤ * (the last element in the sequence belongs to the targeted category or some higher category)

g(x t-1 , x t ) ≤ β t for all t ∈ {1, . . . , h} where g : X × X → R is the cost function of the problem (modifications in the sequence are under a budgetary constraint which depends on the period of time)

The goal is to identify a feasible solution (x 1 , . . . , x h ) that minimizes the total cost which is simply defined by:

h t=1 g(x t-1 , x t )
The MCIS problem can therefore be formulated as follows:

min h t=1 g(x t-1 , x t ) (P M CIS ) : s.t.        c(x h ) ≤ * g(x t-1 , x t ) ≤ β t , ∀t ∈ {1, . . . , h}
Ax t ≤ b, ∀t ∈ {1, . . . , h}

x t ∈ N m , ∀t ∈ {1, . . . , h}

Note that we deliberately omitted monotonicity constraints of type c(x t ) ≤ c(x t-1 ) for t ∈ {1, . . . , h} because they are not necessary as soon as the following triangular inequality holds: g(x, y) ≤ g(x, z) + g(z, y). This is the case for all functions g considered here (e.g., when g(x, y) is a linear function of x -y, or when g is a distance defined from a norm by g(x, y) = x -y ). This makes impossible to find 3 solutions x, y, z with c(y) < c(x) (y improves x) and such that the cost of a two step path x → z → y is lower than the cost of the direct path x → y. Hence, whenever z belongs to a category worse than that of x (i.e., c(z) > c(x)), there is no benefit in moving first from x to z and then from z to y compared to directly moving from x to y since g(x, z) + g(z, y) ≥ g(x, y). Moreover, if reaching level or better must be achieved in the sequence of moves at some intermediary step t, one can easily insert the following constraint c(x t ) ≤ in program P M CIS .

We now give an instance of the MCIS problem below.

Example 4 Let us come back to Example 2. Consider the multicriteria reference profiles (given in Table 8) which allow the definition of three categories for this problem. Here there are only seven feasible solutions, denoted by x j , j ∈ {0, . . . , 6}, and their overall preference indices and membership values are given in Table 9. From this table, we conclude that solutions x 4 and x 6 enter into category K 1 (the best category), solutions x 2 and x 5 enter into category K 2 (the second best category) while x 0 , x 1 and x 3 enter to category K 3 (the worst category).

f 1 f 2 r 0 6 6 r 1 4 4 r 2 2 2 r 3 -1 -1
f 1 f 2 P (•, r 0 ) P (•, r 1 ) P (•, r 2 ) P (•, r 3 ) c 1 (•) c 2 (•) c 3 (•) c(•) x 0 = (0, 0, 0) 0 0 0 0 0 1 0 0 1 3 x 1 = (1, 0, 0) 2 2 0 0 0 1 0 0 1 3 x 2 = (0, 1, 0) 4 1 0 0 2/3 1 0 2/3 1/3 2 x 3 = (0, 0, 1) 1 3 0 0 1/3 1 0 1/3 2/3 3 x 4 = (1, 1, 0) 6 3 0 2/3 1 1 2/3 1/3 0 1 x 5 = (1, 0, 1) 3 5 0 1/3 1 1 1/3 2/3 0 2 x 6 = (0, 1, 1) 5 4 0 2/3 1 1 2/3 1/3 0 1
Assume that the current solution is x 0 (belonging to K 3 ), and that we want to reach category K 1 in at most two steps. The graph depicted in Figure 2 represents all feasible sequences of solutions, i.e. the sequences that start from x 0 and end with a solution in K 1 in at most two steps.

In Figure 2, any arrow of type (x i , x j ) is labelled by g(x i , x j ) the cost of moving from solution x i to solution x j . Without any budgetary constraint, we know that we can focus the search on paths of size 1 as g satisfies the triangular inequality. In particular, sequence (x 0 , x 4 ), which consists in moving from x 0 to x 4 in one step, is an optimal solution of the MCIS problem, with a total cost of 2.

Now assume that the cost of each step must not exceed 1 (i.e. we set β 1 = β 2 = 1). In that case, sequence (x 0 , x 4 ) is not feasible anymore, and now sequences (x 0 , x 2 , x 6 ) and (x 0 , x 2 , x 4 ) are the unique optimal solutions of the MCIS problem, with a total cost of 1 + 1 = 2.

x 0

x 1

x 3

x 2

x 5

x 6

x 4

Integer Linear Formulations

In the previous subsections, we have introduced three optimization problems, namely the MCI, MGS and MCIS problems, and they have been solved on very small instances of knapsack problems by enumerating all the feasible solutions (see Examples 2, 3 and 4). For bigger instances, it is not possible to enumerate all the feasible solutions as they are too numerous, and therefore there is a need for tools to solve these optimization problems efficiently.

In this subsection, we propose solving methods based on mixed-integer (linear or quadratic) programming. For simplicity of presentation, we now focus on the MCI problem as these three optimization problems are very similar.

In order to obtain a general mixed-integer formulation of problem P M CI , we now introduce two technical propositions, the proofs of which are given in the Appendix (see Section 6).

Proposition 1 For any solution y ∈ X and any category K ∈ K:

c(y) ≤ ⇐⇒ P (y, r ) ≥ 1/2.
When setting = c(x) -1, we see that constraint c(y) ≤ c(x) -1, which corresponds to Equation (5a) in P M CI , holds if and only if P (y, r c(x)-1 ) ≥ 1/2. As a consequence solving P M CI amounts to solving the following optimization problem, denoted by P M CI : min g(x, y)

(P M CI ) : s.t. P (y, r c(x)-1 ) ≥ 1/2 Ay ≤ b (8a) (8b) y ∈ N m (8c)
Now in order to solve P M CI , we propose to use the following program: min g(x, y)

(P M CI ) : s.t.                ψ θ (p 1 , . . . , p n ) ≥ 1/2 p i ≤ f i (y) -r c(x)-1 i -γ - i γ + i -γ - i + (1 -v i )M, ∀i ∈ N p i ≤ M v i , ∀i ∈ N Ay ≤ b (9a) (9b) (9c) (9d) y ∈ N m p = (p 1 , . . . , p n ) ∈ [0,1] n , v = (v 1 , . . . , v n ) ∈ {0, 1} n (9e)
where M is a constant greater than one allowing the introduction of boolean variables v i , i ∈ N , that ensure that all variables p i satisfy p i ≤ P i (y, r c(x)-1 ) (see Lemma 1 in the Appendix).

Interestingly, program P M CI can be used to solve P M CI due to the following proposition:

Proposition 2 For any feasible solution y ∈ N m of problem P M CI , the following two properties are equivalent:

1. Solution y is optimal for problem P M CI .

2. There exist p ∈ [0, 1] n and v ∈ {0, 1} n such that (y, p, v) is a feasible optimal solution of problem P M CI .

Note that P M CI is a mixed-integer linear program when the cost function is linear. When g is not linear but linearizable or when g is a quadratic function, problem P M CI can still be solved efficiently using a state-of-the-art solver, as shown in Section 4.

Using similar arguments, one can easily prove that the MGS problem can be solved using the following program: max g(x, y)

(P M GS ) : s.t.                ψ θ (p 1 , . . . , p n ) ≥ 1/2 p i ≤ f i (y) -r c(x) i -γ - i γ + i -γ - i + (1 -v i )M, ∀i ∈ N p i ≤ M v i , ∀i ∈ N Ay ≤ b y ∈ N m p = (p 1 , . . . , p n ) ∈ [0, 1] n , v = (v 1 , . . . , v n ) ∈ {0, 1} n
and the same applies to the MCIS problem:

min h t=1 g(x t-1 , x t ) (P M CIS ) : s.t.                      ψ θ (p 1 , . . . , p n ) ≥ 1/2 p i ≤ f i (x h ) -r * i -γ - i γ + i -γ - i + (1 -v i )M, ∀i ∈ N p i ≤ M v i , ∀i ∈ N g(x t-1 , x t ) ≤ β t , ∀t ∈ {1, . . . , h} Ax t ≤ b, ∀t ∈ {1, . . . , h} (11a)
x t ∈ N m , ∀t ∈ {1, . . . , h}

p = (p 1 , . . . , p n ) ∈ [0, 1] n , v = (v 1 , . . . , v n ) ∈ {0, 1} n

Some Applications

Depending on the decision problem, function g giving the cost/gain of moving from a given solution to another solution can take different forms. For illustrative purposes, we now study three realistic instances of the MCI problem on combinatorial domains with different cost functions to be minimized2 .

A Transportation Problem

Consider a transportation problem dealing with the distribution of products from a set of m factories F = {F 1 , . . . , F m } to a set of n clients C = {C 1 , . . . , C n }, each factory F j having a limited number of units to supply. We are given a cost matrix g = (g ij ) n×m so that g ij ∈ R + is the cost of transporting one unit of products from factory F j to client C i for all i ∈ {1, . . . , n} and j ∈ {1, . . . , m}. In this problem, a feasible solution can be represented by a matrix X = (x ij ) n×m where x ij ∈ R + is the number of units shipping from F j to C i for all i ∈ {1, . . . , n} and j ∈ {1, . . . , m}, and the corresponding cost is given by T (x) = n i=1 m j=1 x ij g ij . Thus, the cost g(x, y) of moving from a given solution x to another solution y is simply given by g(x, y) = T (y) -

T (x) = n i=1 m j=1 (y ij g ij -x ij g ij ) in this problem. Now suppose that every client C i , i ∈ {1, . . . , n}, provides 3 values α 1 i , α 2 i , α 3 i
representing the minimum number of units required to be very satisfied, satisfied, and slightly satisfied respectively. These thresholds lead to 4 satisfaction categories K 1 (very satisfied), K 2 (satisfied), K 3 (slightly satisfied) and K 4 (not satisfied), which are characterized by the set R = {r 0 , r 1 , r 2 , r 3 , r 4 } of multicriteria reference profiles defined as follows:

r = (α 1 , . . . , α n ) for all ∈ {1, 2, 3},

-r 4 = (-1, . . . , -1),
and r 0 = (M, . . . , M ) with M large enough to bound above all admissible values (e.g., the total number of products).

By definition, the quality of a given solution x only depends on the number of units shipped to the different clients. Hence the performance vector attached to solution x is simply defined by f (x) = (f 1 (x), . . . , f n (x)) where

f i (x) = m j=1
x ij for all i ∈ {1, . . . , n}. Monocriterion preference indices are here aggregated using a Choquet integral ψ θ with a 2-additive convex capacity θ so as to model possible interactions between any two criteria (e.g., clients who have the same parent company, business partners, or clients located in the same country/city).

Using Proposition 2, we know that solving this MCI problem can be done by solving the following optimization problem: 9a), (9b), (9c) and (9e)

min g(x, y) = n i=1 m j=1 y ij g ij -x ij g ij s.t.        Equations (
n i=1 y ij ≤ b j , ∀j ∈ {1, . . . , m} (12a)
y ij ∈ N, ∀i ∈ {1, . . . , n}, ∀j ∈ {1, . . . , m} (12b)
where b j is the capacity of factory F j so that Equation (12a) corresponds to Equation (5b) the feasibility constraints of the problem.

We now present an explicit example of this transportation problem. . For all i, j ∈ {1, 2, 3}, the cost g ij of transporting one unit of product from factory F j to client C i is given below: Here the satisfaction of clients only depends on the quantity they receive, and is represented by the reference profiles given in Table 11. These reference profiles define 4 categories: "Very satisfied" (K 1 ), "Satisfied" (K 2 ), "Slightly satisfied" (K 3 ) and "Not satisfied" (K 4 ). To aggregate monocriterion preference indices, we use the Choquet integral ψ θ with capacity θ defined as follows:

g ij F 1 F 2 F 3 C 1 6 7 7 C 2 5 1 3 C 3 5 3 1
∅ {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3} θ 0 0.2 0.1 0.3 0.4 0.7 0.6 1
Table 12: Capacity θ used in the sorting method.

Let us assume that the current solution x 0 implemented by the decision maker (the delivery company) consists in providing 4 units to C 1 from factory F 1 , 7 units to C 2 from factory F 2 and 7 units to C 3 from factory F 3 (as shown in Figure 3(a)). Its performance vector is f (x 0 ) = (4, 7, 7), and therefore the resulting preference indices are: P (x 0 , r 0 ) = P (x 0 , r 1 ) = P (x 0 , r 2 ) = 0, P (x 0 , r 3 ) = 0.6, and P (x 0 , r 4 ) = 1. Hence the membership values are: c 1 (x 0 ) = c 2 (x 0 ) = 0, c 3 (x 0 ) = 0.6 and c 4 (x 0 ) = 0.4. As a consequence, solution x 0 enters into category K 3 ("Slightly satisfied").

Assume first that the decision maker wants to know how much savings could be realized while remaining in the same category. To answer this question, we solve the MGS problem with solution x = x 0 . We obtain the solution that only differs from x 0 by transporting 3 units from F 1 to C 1 (instead of 4), allowing to save 6 ke.

Assume now that the decision maker wants to know what is the price to pay to improve clients' satisfaction. To answer this question, we solve the MCI problem with solution x = x 0 and we obtain solution x 1 depicted in Figure 3(b), whose performance vector is f (x 1 ) = [START_REF] Benabbou | Incremental elicitation of choquet capacities for multicriteria choice, ranking and sorting problems[END_REF][START_REF] Fernández | ELECTRE TRI-nB: A new multiple criteria ordinal classification method[END_REF][START_REF] Ehrgott | A survey and annotated bibliography of multiobjective combinatorial optimization[END_REF]. This solution belongs to category K 2 ("Satisfied"), as can be derived from its preference indices and membership values: P (x 1 , r 0 ) = P (x 1 , r 1 ), P (x 1 , r 2 ) = 0.6, P (x 1 , r 3 ) = 0.6, P (x 1 , r 4 ) = 1, c 1 (x 1 ) = 0, c 2 (x 1 ) = 0.6, c 3 (x 1 ) = 0.4 and c 4 (x 0 ) = 0.4. The cost of moving from x 0 to x 1 is equal to g(x 0 , x 1 ) = 52 -38 = 14 ke.

The decision maker realizes that moving up one level (i.e. to the "Satisfied" category) is not very expensive. Therefore she now wants to know what is the price to pay to move straight to category K 1 ("Very satisfied"). When solving the MCI problem with x = x 0 and constraint c(y) ≤ 1 (instead of Equation (5a)), we obtain solution x 2 depicted in Figure 3(c) whose performance vector is f (x 2 ) = [START_REF] Benabbou | Incremental elicitation of choquet capacities for multicriteria choice, ranking and sorting problems[END_REF][START_REF] Greco | Multiple criteria sorting with a set of additive value functions[END_REF][START_REF] Grabisch | Aggregation functions[END_REF]. The cost of moving from x 0 to x 2 is equal to g(x 0 , x 2 ) = 121 -38 = 83 ke.

For the decision maker, paying 83 ke in one shot is not possible but is willing to delay the objective to the next period. More precisely, she is willing to accept a solution in two steps (one per year), provided that the cost of each step does not exceed 50 ke. Remark that it is not possible for her to first move from solution x 0 to x 1 and then move from solution x 1 to x 2 as the cost g(x 1 , x 2 ) = 121 -52 = 69 > 50 ke. Therefore we want to know whether it is Fig. 3: Solutions found during the interactions with the decision maker.

F 1 F 2 F 3 C 1 C 2 C 3 4 7 7 (a) Solution x 0 . F 1 F 2 F 3 C 1 C 2 C 3 3 15 10 3 (b) Solution x 1 . F 1 F 2 F 3 C 1 C 2 C 3 3 18 10 10 5 (c) Solution x 2 . F 1 F 2 F 3 C 1 C 2 C 3 3
possible to reach K 1 in two steps, taking into account her budgetary constraints.

To answer this question, we solve the MCIS problem with * = 1 (the target category), h = 2 (at most 2 steps), and β 1 = β 2 = 5 (the available budgets). We obtain the sequence (x 0 , x 1 , x 2 ) where x 1 is the solution belonging to category K 2 ("Satisfied") which is depicted in Figure 3(d). The total cost is g(x 0 , x 1 ) + g(x 1 , x 2 ) = 33 + 50 = 83 ke.

Numerical results. We implemented the presented model using the Gurobi 8.1.1 solver on a computer with 12GB of RAM and an Intel(R) Core(TM) i7 CPU 950 @ 3.07GHz processor. Instances, mathematical programs and initialization algorithms were implemented using python 3.7.5. This model was tested on randomly generated transportation instances where the cost g ij is uniformly drawn in [0, 1] for every client-factory pair (C i , F j ), and the capacity b j is uniformly drawn in [ [START_REF] Almeida-Dias | A multiple criteria sorting method where each category is characterized by several reference actions: The ELECTRE TRI-nC method[END_REF]100]] for every factory F j . The preference and indifference thresholds are respectively set to 1 and 0 for every criterion, and monocriterion preferences indices are aggregated using randomly generated Choquet integrals with a 2-additive convex capacity and rely on the computational model presented in [START_REF] Lesca | LP solvable models for multiagent fair allocation problems[END_REF]. Multicriteria reference profiles were chosen to evenly divide the objective space.

In our experiments, we vary n the number of clients (i.e. the number of criteria), m the number of factories and q the number of categories, and the current solution x is generated by solving the transportation problem with smaller capacities. Computation times (in seconds) obtained by averaging over 20 runs are given in Table 13. The results show that the proposed linear formulation enables to efficiently solve instances with a large number of clients and factories. Table 13: Computation times in the transportation problem.

An Assignment Problem

Consider an assignment problem where a set of m tasks T = {t 1 , . . . , t m } has to be performed by a set of m agents A = {a 1 , . . . , a m } in such a way that each agent is assigned to a different task. A feasible solution can be represented by a binary matrix x = (x jk ) m×m where x jk = 1 if and only if agent a j is assigned to task t k for all j, k ∈ {1, . . . , m}. In this problem, the agents' preferences over tasks are represented by utility vectors of type

u jk = (u jk 1 , . . . , u jk n ) ∈ R n +
where u jk i is the utility of agent a j ∈ A for task t k ∈ T with respect to criterion i ∈ {1, . . . , n} (e.g., duration, arduousness, repetitiveness, intellectual stimulation), and the overall performance of a given solution x is simply given by f (x) = (f 1 (x), . . . , f n (x)) with f i (x) = m j=1 n k=1 x jk u jk i for all criteria i ∈ {1, . . . , n}.

Assume that the team leader cares about how happy the agents are with respect to the different criteria, and therefore defines two positive values α 1 i and α 2 i for each criterion i ∈ {1, . . . , n} representing the minimum average utility required to be satisfied and slightly satisfied respectively. These values define three categories K 1 (satisfied), K 2 (slightly satisfied), and K 3 (not satisfied), which are characterized by the set R = {r 0 , r 1 , r 2 , r 3 } of reference profiles defined as follows:

r = (α 1 , . . . , α n ) for ∈ {1, 2}, r 3 = (-1, . . . , -1), and r 0 = (M 1 , . . . , M n ) with M i large enough to bound above all admissible utility values on criterion i ∈ {1, . . . , n} (e.g., M i = max j,k∈{1,...,m} u jk i ). Then overall preference indices are defined using a Choquet integral ψ θ with a 2-additive convex capacity to model interactions between some criteria such as duration and arduousness. Now assume that the team leader wishes to change the current solution in order to obtain a better solution at a minimal cost. Here the cost is defined as follows: for any agent a j ∈ A, we are given a cost vector g j = (g j 1 , . . . , g j m ) ∈ R n + where g j k is the cost incurred when agent a j is asked to perform task t k instead of its current assigned task. Then, for any agent a j ∈ A, the cost g j (x, y) of moving from a given solution x = (x jk ) m×m to another solution y = (y jk ) m×m can be formally defined by:

g j (x, y) = m k=1 g j k × max{y jk -x jk , 0}
since max{y jk -x jk , 0} is equal to 1 when y jk = 1 and x jk = 0, and is equal to 0 otherwise. Finally the total cost g(x, y) is given by:

g(x, y) = m j=1 g j (x, y) = m j=1 m k=1 g j k × max{y jk -x jk , 0}
Using Proposition 2 and a standard linearization of the max aggregator, we obtain the following mixed-integer linear formulation:

min g(x, y) = m j=1 g j k z jk s.t.                             
Equations (9a), (9b), (9c) and (9e)

(13d)

y jk ∈ {0, 1}, ∀j ∈ {1, . . . , m}, ∀k ∈ {1, . . . , m} (13e)
where Equations (13a) and (13b) correspond to Equation (5b) (the feasibility constraints) while Equations (13c) and (13d) are added so that z jk = max{y jk -x jk , 0} (linearization).

Numerical results. We now present some experimental results obtained for the assignment problem presented in this subsection; the experimental environment is the same as that of the transportation problem, so as the generation methods for thresholds, reference profiles and aggregation functions. The tests were performed on randomly generated instances, where utility vector u jk was uniformly drawn in [ [START_REF] Almeida-Dias | A multiple criteria sorting method where each category is characterized by several reference actions: The ELECTRE TRI-nC method[END_REF]100]] n for every agent-task pair (a j , t k ), and cost g j k was uniformly drawn in [0, 1]. Then, following a previously fixed permutation of agents, each one has its worst object assigned among the ones remaining. We vary n the number of criteria, m the number of agents (or tasks), and q the number of categories. The results obtained by averaging over 20 runs are given in Table 14 (in seconds); for every run, x is generated by solving the assignment problem obtained by simply aggregating the multi-objective valuations into a single value using a randomly generated weighted sum. We observe that our model is able to solve instances with a large number of tasks, agents and criteria.

A Knapsack Problem

Consider a knapsack problem consisting in the selection of W team members from a pool A = {a 1 , . . . , a m } of candidates (e.g., football teams). Any feasible solution can be represented by a binary vector x = (x 1 , . . . , x m ) such that m j=1 x j = W , where x j = 1 if and only if candidate a j is selected. In this selection problem, every candidate a j ∈ A is valued by a vector u j = (u j 1 , . . . , u j n ) ∈ R n + giving the performance of a j with respect to different criteria (e.g., physical fitness, technique, proper mindset, game intelligence), which are assumed to be additive over the candidates. Hence the performance vector attached to a given team x is simply defined by f (x) = n j=1 x j u j .

Assume that the recruiter defines two thresholds α 1 i and α 2 i for every criterion i ∈ {1, . . . , n} representing the minimum level of performance required to be considered as a high-level and middle-level team respectively. These thresholds define three categories K 1 (high-level), K 2 (middle-level) and K 3 (low-level) which are characterized by the set R = {r 0 , r 1 , r 2 , r 3 } of reference profiles defined as follows:

r = (α 1 , . . . , α n ) for ∈ {1, 2}, r 3 = (-1, . . . , -1), and r 0 = (M 1 , . . . , M n ) with M i large enough to bound above all admissible performances on criterion i ∈ {1, . . . , n} (e.g., M i = j∈{1,...,m} u j i ).

Then overall preference indices are defined using a Choquet integral ψ θ with a 2-additive convex capacity to model interactions between pairs of criteria (e.g., technique and game intelligence have a positive interaction). Finally, every candidate a j ∈ A is assumed to have a market price g j ∈ R + so that the cost g(x, y) of moving from a given team x to another team y can be defined by g(x, y) = m j=1 g j (y j -x j ). Thus, the MCI problem can be solved using the following mixed-integer linear program:

min y g(x, y) = m j=1 g j (y j -x j ) s.t.       
Equations (9a), (9b), (9c) and (9e)

m j=1 y j = K, ∀j ∈ {1, . . . , m} (14a)
y j ∈ {0, 1}, ∀j ∈ {1, . . . , m}
where Equation (14a) correspond to Equation (5b) (the feasibility constraints).

Numerical results. We implemented the presented model in the same experimental environment as before, with the same generation methods for thresholds, reference profiles and aggregation functions. The tests were performed on randomly generated knapsack instances with performance vectors u j uniformly drawn in [ [START_REF] Almeida-Dias | A multiple criteria sorting method where each category is characterized by several reference actions: The ELECTRE TRI-nC method[END_REF]100]] n and the knapsack capacity W was set to m/2. Solution x is generated by picking objects a j in increasing order according to the overall utility n i=1 u ji , until the knapsack capacity is reached. We vary n the number of criteria, m the number of objects, and q the number of categories. We report the computation times (in seconds) obtained by averaging over 20 runs in Table 15. The results show that the proposed mixed-integer linear formulation enables to solve very large instances of the MCI problem specialized for the multicriteria knapsack problem. In order to sort the solutions, we consider 6 categories K = {K 1 , . . . , K 6 } delimited by constant reference profiles R = {r 0 , . . . , r 6 } such that f i (r 0 ) = 375, f i (r 1 ) = 313, f i (r 2 ) = 250, f i (r 3 ) = 187, f i (r 4 ) = 124, f i (r 5 ) = 62, f i (r 6 ) = -1 for all i ∈ {1, . . . , 4}.

The aggregation function used to aggregate preference indices is a Choquet integral ψ θ where capacity θ is compactly defined by θ(A) = B⊆A m(B) with m(B) = 0 for all B except the following focal sets:

B {1} {2} {3} {4} {1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3
, 4} m(B) 0.174 0.002 0.035 0.159 0.174 0.066 0.098 0.014 0.124 0.154 Assume that the current solution is subset X 0 = {o 2 , o 3 , o 10 } of utility vector f (X 0 ) = (123, 208, 70, 111). Given the profiles and the assignment rule, one can easily check that X 0 belongs to category K 5 . In this problem, the decision maker wants to reach category K 1 in at most 3 years under some budget constraints which limit the number of changes (insertion or deletion) per year.

The above example can easily be solved by mathematical programming using P M CIS . For illustration purposes, we now give three optimal sequences for three scenarios of constraints limiting the number of changes per year.

-Scenario 1: at most 5 changes are allowed per year. The optimal solution is a direct move from X 0 to X 1 where X 1 = {o 3 , o 4 , o 6 , o 7 , o 8 , o 10 } and f (X 1 ) = (353, 346, 218, 352), a utility vector belonging to K 1 .

-Scenario 2: at most 3 changes are allowed per year. The optimal solution is the sequence (X 0 , X and f (X 2 ) = (349, 286, 279, 320) respectively. This sequence allows the decision maker to move first from K 5 to K 4 and then from K 4 to K 1 while satisfying the budget constraints and minimizing the total cost.

-Scenario 3: at most 2 changes are allowed per year. The optimal solution is a sequence of solutions (X 0 , X 1 , X 2 , X 3 ) leading to three moves. The first step is a move from K 5 to K 3 with solution X 1 = {o In all scenarios, solving the MCIS problem yields a sequence reaching the target category at minimal cost under the given constraints. This example provides a good illustration of the possibilities offered by the approach developed in the paper to plan the improvement of a current solution in a multiobjective combinatorial optimization setting.

Conclusion

In this paper, we have studied three optimization problems in multicriteria sorting methods on combinatorial domains, namely the min cost improvement, max gain stability and min cost improving sequence problems. We have proposed general mixed-integer (linear or quadratic) formulations, illustrated on the transportation, assignment and knapsack problems. The tests have shown that our approach is very effective in practice in terms of computation times. Note that the proposed approach also applies to continuous sets of alternatives defined by linear constraints leading to simpler problems with even better computation times.

A first direct continuation of this work is to extend the approach to more complex multicriteria sorting methods (e.g., based on assignment rules including veto thresholds, or multiple reference profiles to bound a category). We could also address other combinatorial domains by considering other problems (e.g., the traveling salesman problem). A second direction concerns the development of solution methods when multicriteria reference profiles and/or the aggregation function are imprecisely known and defined by linear constraints.

Appendix

Proof of Proposition 1

(=⇒) Let y ∈ X be such that c(y) ≤ . Since c (y) is unimodal when y is fixed, with a maximum at least equal to 1/2 (see [START_REF] Perny | Multicriteria filtering methods based on concordance and non-discordance principles[END_REF]), we know that c(y) ≤ implies that there exists ≤ such that c (y) ≥ 1/2. Assume that P (y, r ) < 1/2. We now prove that c (y) < 1/2 for all ≤ yielding a contradiction.

Consider an index such that < . Since r r by definition, we have P i (y, r ) ≤ P i (y, r ) for all criteria i ∈ N . Hence (P 1 (y, r ), . . . , P n (y, r )) (P 1 (y, r ), . . . , P n (y, r )). Then, since ψ θ is compatible with Pareto-dominance, we have P (y, r ) = ψ θ (P 1 (y, r ), . . . , P n (y, r )) ≥ ψ θ (P 1 (y, r ), . . . , P n (y, r )) = P (y, r ). Thus, for all ≤ , we have: c (y) = min{P (y, r ), 1 -P (y, r -1 )} by definition of membership indices ≤ min{P (y, r ), 1 -P (y, r -1 )} since we have P (y, r ) ≥ P (y, r ) < min{1/2, 1 -P (y, r -1 )} since P (y, r ) < 1/2 by hypothesis ≤ 1/2 (⇐=) Let y ∈ X be such that P (y, r ) ≥ 1/2. Assume that * = c(y) > . Since c (y) is unimodal with a maximum at least equal to 1/2, two cases may occur:

• c * (y) > 1/2. In that case, we necessarily have:

Proof of Proposition 2

In order to establish Proposition 2, we first establish the following Lemma:

Lemma 1 For any feasible solution of problem (P M CI ), we have: ∀i ∈ N, p i ≤ P i (y, r c(x)-1 )

Proof of Lemma 1. Let (y, p, v) be a feasible solution of problem (P M CI ). For all i ∈ N , only three cases may occur:

• f i (y) -r c(x)-1 i > γ + i : In that case, we trivially have p i ≤ P i (y, r c(x)-1 ) since P i (y, r c(x)-1 ) = 1 (see Equation ( 2)) and p i ≤ 1 (see Equation (9e)).

• γ - i ≤ f i (y) -r c(x)-1 i ≤ γ + i : Here we have P i (y, r c(x)-1 ) = fi(y)-r c(x)-1 i -γ - i γ + i -γ - i by definition (see Equation (2)). If v i = 1, then we derive p i ≤ P i (y, r c(x)-1 ) from constraint (9b). Otherwise, p i is necessarily equal to 0 due to constraint (9c) and therefore p i = 0 ≤ P i (y, r c(x)-1 ) trivially holds.

• f i (y)-r c(x)-1 i < γ - i : In that case, P i (y, r c(x)-1 ) = 0 holds by definition (see Equation ( 2)). Note that variable v i must be set to 0 to satisfy constraint (9b) since f i (y) -r c(x)-1 i -γ - i < 0. As a consequence, we necessarily have p i = 0 due to constraint (9c), and therefore p i ≤ P i (y, r c(x)-1 ) also holds.

Using this lemma, we can now establish Proposition 2.

Proof of Proposition 2. (⇐=) Let (y, p, v) be a feasible optimal solution of problem (P M CI ). Assume that y is not optimal for (P M CI ). In that case, there exists y ∈ {0, 1} m such that Ay = b and g(x, y ) < g(x, y). Consider T (y ) = (y , p , v ) defined as follows:

• v i = 0 if P i (y , r c(x)-1 ) = 0 and v 1 = 1 otherwise.

• p i = P i (y , r c(x)-1 ).

It is easy to check that solution T (y ) satisfies constraints (9b-9e). Moreover, since y is a feasible solution of (P M CI ), we know that P (y , r c(x)-1 ) = ψ θ (P 1 (y , r c(x)-1 ), . . . , P n (y , r c(x)-1 )) = ψ θ (p 1 , . . . , p 2 ) ≥ 1/2 due to constraint (8a). Hence T (y ) is a feasible solution of (P M CI ) with g(x, y ) < g(x, y), which contradicts the fact that (y, p, v) is optimal for (P M CI ).

(=⇒) Let y ∈ {0, 1} m be a feasible optimal solution of problem (P M CI ). Assume that no solution of type (y, p, v) with p ∈ [0, 1] n and v ∈ {0, 1} n is optimal for (P M CI ). Consider solution T (y) = (y, p, v) as defined above. Since T (y) is not optimal (by hypothesis), there exists a feasible solution (y , p , v ) such that g(x, y ) < g(x, y). Moreover, we know that p i ≤ P i (y , r c(x)-1 ) for all i ∈ N (see Lemma 1). As a consequence, constraint (9a) implies constraint (8a), and therefore y is a feasible solution of (P M CI ) with g(x, y ) < g(x, y), which yields a contradiction since y ∈ X is optimal for (P M CI ).

K 1 Fig. 2 :

 12 Fig. 2: Feasible sequences of solutions in Example 4.

Example 5

 5 Consider an instance of this transportation problem with n = 3 three clients (i.e. C = {C 1 , C 2 , C 3 }) and m = 3 factories (i.e. F = {F 1 , F 2 , F 3 }) with the following capacities: b 1 = 20, b 2 = 18 and b 3 = 10

m j=1 y jk = 1 ,

 1 ∀k ∈ {1, . . . , m} m k=1 y jk = 1, ∀j ∈ {1, . . . , m} z jk ≥ y jk -x jk , ∀j ∈ {1, . . . , m}, ∀k ∈ {1, . . . , m} z jk ≥ 0, ∀j ∈ {1, . . . , m}, ∀k ∈ {1, . . . , m}

1/ 2 1 ≥ 2 = 1 / 2 =

 21212 > P (y, r * -1 ) since c * (y) = min{P (y, r * ), 1 -P (y, r * -1 )} ≥ P (y, r ) since * -1 ≥ (and therefore r * -1 r ) ≥ 1/2 since P (y, r ) ≥ 1/2 by hypothesis yielding a contradiction. • c * (y) = 1/2. Here we necessarily have P (y, r * -1 ) ≤ 1/2 since c * (y) = min{P (y, r * ), 1 -P (y, r * -1 )} by definition. Thus we obtain: c (y) = min{P (y, r ), 1 -P (y, r -1 )} by definition ≥ min{1/2, 1 -P (y, r -1 )} since P (y, r ) ≥ 1/2 by hypothesis ≥ min{1/2, 1 -P (y, r * -1 )} since * -1 ≥ -min{1/2, 1/2} since P (y, r * -1 ) ≤ 1/c * (y) Hence we have c * (y) = c (y) and * > which contradicts our assignment rule ( * * ).

Table 1 :

 1 An example of capacity function.

	n)} is the

Table 2 :

 2 Multicriteria reference profiles defining categories in Example 1.

				30
	r 1 11 10 12
	r 2	0	0	0

Table 4 :

 4 Overall preference indices and membership values in Example 1.

Table 6 :

 6 The multicriteria reference profiles used in Example 2.

Table 7 :

 7 Overall preference indices and membership values attached to the feasible solutions in Example 2.

Table 8 :

 8 The multicriteria reference profiles in Example 2.

Table 9 :

 9 Overall preference indices and membership values attached to the feasible solutions in Example 4.

Table 10 :

 10 Delivery costs (given in ke).

		C 1 C 2 C 3
	r 0 50 50 50
	r 1 17 22 19
	r 2 16 14 12
	r 3	5	6	6
	r 4 -1	-1	-1

Table 11 :

 11 Multicriteria reference profiles used in the sorting method.

Table 14 :

 14 Computation times in the assignment problem.

Table 15 :

 15 Computation times in the knapsack problem.We conclude this section by considering a particular instance of the multiobjective Knapsack problem in order to illustrate the potential of model P M CIS , see Equation (11a), to generate recommendations in terms of min-cost improving sequences reaching the target category. We consider a multicriteria knapsack problem involving a set of 10 objects O = {o 1 , . . . , o 10 } evaluated according to 4 criteria assumed to be additive (i.e., the utility of a subset is defined as the sum of the utilities of its elements). The maximal weight for an admissible solution to the knapsack problem is set to 221. The utilitiesf 1 (o k ), f 2 (o k ), f 3 (o k ),f 4 (o k ) and the weight w k of object o k , with k ∈ {1, . . . , 10}, are given in the following table:o 1 o 2 o 3 o 4 o 5 o 6 o 7 o 8 o 9 o 10 f

	Example 6 1 75 56 36 68 15 79 74 65 86	31
	f 2 41 60 56 96 13	2 78 22	1	92
	f 3 89	4 11 38 90 28 71 15	9	55
	f 4 26 20 54 28 90 58 77 98 93	37
	w k 14 90 56 44 67 23	5 13 61	69

  2 , o 3 , o 7 , o 10 } of utility vector f (X 1 ) =(197, 286, 141, 188). Then the second step is a move within category K 3 (substitution of o 2 by o 1 ) leading to solution X 2 = {o 1 , o 3 , o 7 , o 10 } of utility vector f (X 2 ) =(216, 267, 226, 194). Finally the third step is a move from K 3 to K 1 with solution X 3 = {o 1 , o 3 , o 4 , o 7 , o 8 , o 10 } of utility vector f (X 3 ) = (349, 385, 279, 320).

Data sharing not applicable to this article as no datasets were generated or analysed during the current study.