Nawal Benabbou
email: nawal.benabbou@lip6.fr

Cassandre Leroy
email: cassandre.leroy@lip6.fr

Thibaut Lust
email: thibaut.lust@lip6.fr

Patrice Perny
email: patrice.perny@lip6.fr

Combining Preference Elicitation with Local Search and Greedy Search for Matroid Optimization

We propose two incremental preference elicitation methods for interactive preference-based optimization on weighted matroid structures. More precisely, for linear objective (utility) functions, we propose an interactive greedy algorithm interleaving preference queries with the incremental construction of an independent set to obtain an optimal or nearoptimal base of a matroid. We also propose an interactive local search algorithm based on sequences of possibly improving exchanges for the same problem. For both algorithms, we provide performance guarantees on the quality of the returned solutions and the number of queries. Our algorithms are tested on the uniform, graphical and scheduling matroids to solve three different problems (committee election, spanning tree, and scheduling problems) and evaluated in terms of computation times, number of queries, and empirical error.

Introduction

Local search is a very general heuristic approach standardly used in AI to determine good solutions to hard combinatorial optimization problems [START_REF] Russell | Artificial intelligence: a modern approach[END_REF][START_REF] Aarts | Local search in combinatorial optimization[END_REF]. Local search algorithms start from a candidate solution and then iteratively move to a neighbor solution with the aim of finding the optimal one. A typical instance of local search algorithm is hill climbing, which consists in choosing the neighbor solution among the ones that locally optimize the objective function in the neighborhood.

In many cases, local search delivers sub-optimal solutions to the global problem and the search method needs to be modified t o c ontinue t he s earch b eyond l ocal optimality. However, there are some well known examples of problems for which local search algorithms deliver optimal solutions. For example, in continuous optimization, the simplex algorithm used to solve linear programs is essentially a local search algorithm passing from vertices of a polytope to neighbor vertices until reaching a local optimum, which is known to be a global optimum. In discrete optimization, the minimum spanning tree problem can also be solved by local search from any arbitrary initial spanning tree using neighborhoods and improving sequences based on edge swaps. This result is strongly related to the correctness of the greedy algorithm in the spanning tree problem (Kruskal algorithm (Kruskal 1956)) and more generally to the weighted matroid structure underlying the problem.

Matroids are indeed of special interest both for greedy search and local search. First, they are the only non-empty hereditary structures for which the greedy algorithm provides optimal solutions [START_REF] Oxley | Matroid theory[END_REF]. But local search also benefits from matroid structures. In a combinatorial optimization problem where the admissible solutions are the bases of a weighted matroid, a local search algorithm can indeed be used from any base to progressively improve the current base using swaps of elements until reaching the optimal one, as suggested in [START_REF] Lee | A first course in combinatorial optimization[END_REF]) with a simple exchange algorithm. To perform useful swaps in a local search or optimal greedy choices in the construction of a solution, we need to know the relative values of the elements composing the feasible solutions. When this preference information is not available at the beginning of the search, it can be acquired during the search via preference elicitation procedures to reduce the elicitation burden. The goal of this paper is to make some propositions in this direction for matroid optimization.

The standard assumption in preference-based optimization is that preferences have been elicited beforehand and are known when the optimization procedure is launched. Nevertheless, some recent works in AI and algorithmic decision theory have relaxed this assumption to extend search procedures to the case of imprecisely known objective functions. The idea is to combine preference elicitation methods aiming to progressively specify the objective with the exploration of the set of solutions in order to focus the elicitation task on acquiring the part of preference information that is necessary to solve the instance under consideration. Thus, the optimal solution can be found after a reduced number of preference queries. This approach which is both incremental and adaptive to answers provided by the Decision Maker was first implemented in non-combinatorial problems, in various contexts such as multiattribute utility theory [START_REF] White | A model of multiattribute decisionmaking and trade-off weight determination under uncertainty[END_REF][START_REF] Braziunas | Minimax regret based elicitation of generalized additive utilities[END_REF], decision making under risk [START_REF] Ha | Problem-focused incremental elicitation of multi-attribute utility models[END_REF][START_REF] Chajewska | Making rational decisions using adaptive utility elicitation[END_REF][START_REF] Wang | Incremental Utility Elicitation with the Minimax Regret Decision Criterion[END_REF], collective decision making [START_REF] Lu | Robust Approximation and Incremental Elicitation in Voting Protocols[END_REF]) and multicriteria decision making [START_REF] Benabbou | Incremental elicitation of Choquet capacities for multicriteria choice, ranking and sorting problems[END_REF]. Elicitation for decision making on combinatorial domains is more challenging and has motivated several contributions in various contexts, e.g., constraint satisfaction prob-lems [START_REF] Gelain | Elicitation strategies for soft constraint problems with missing preferences: Properties, algorithms and experimental studies[END_REF], sequential decision making under risk [START_REF] Regan | Regret-based reward elicitation for Markov decision processes[END_REF][START_REF] Weng | Interactive Value Iteration for Markov Decision Processes with Unknown Rewards[END_REF]Benabbou and Perny 2017), stable matching [START_REF] Drummond | Preference Elicitation and Interview Minimization in Stable Matchings[END_REF], and multiobjective state space search (Benabbou and Perny 2015a,b). Then, some interactive versions of dynamic programming, branch and bound, greedy algorithms have been proposed for specific problems, combining preference elicitation and optimization on combinatorial domains [START_REF] Benabbou | Interactive resolution of multiobjective combinatorial optimization problems by incremental elicitation of criteria weights[END_REF]. Recently, some metaheuristics have also been proposed to solve harder optimization problems (see [START_REF] Benabbou | An Interactive Regret-Based Genetic Algorithm for Solving Multi-Objective Combinatorial Optimization Problems[END_REF] for the traveling salesman problem). Our aim is to take advantage of matroid structures to propose general interactive local search and greedy algorithms yielding exact solutions or approximate solutions with performance guarantees.

The paper is organized as follows: First, we recall some basic notions on weighted matroids and on regretbased preference elicitation. Then, we present an interactive greedy algorithm and interactive local search method for linear optimization on matroids. We establish a performance guarantee in terms of worst-case regrets for these algorithms. Finally, we present three applications of the proposed algorithms and the results of numerical tests.

Weighted Matroids and Preference Elicitation

Matroids appear in various combinatorial optimization problems such as subset selection, task ordering, minimum spanning trees [START_REF] Lee | Matroid applications and algorithms[END_REF][START_REF] Lee | A first course in combinatorial optimization[END_REF]) with various possible applications in AI, e.g., in the context of social choice and fair division (Gourvès, Monnot, andTlilane 2013, 2014). We recall here some basic definitions related to matroids, as well as some well-known examples that will be used for application and numerical tests later in the paper.

Matroids.

A matroid M = (S, I) is a finite ground set S of size n, together with a collection of sets I ⊆ 2 S known as the independent sets, satisfying the following axioms:

• (A 1 ) if Y ∈ I and X ⊆ Y then X ∈ I, • (A 2 ) if X ∈ I, Y ∈ I and |Y | > |X| then there exists e ∈ Y \ X such that X ∪ {e} ∈ I.
Axiom A 2 implies that all maximal independent sets (w.r.t set inclusion) have the same cardinality. A maximal independent set is called a base of the matroid; the set of all bases will be denoted by B hereafter. The cardinality of a base is called the rank of the matroid and it will be denoted by r(M) in the sequel. Note that the notion of matroid clearly generalizes the notion of linear independence over vectors.

In this work, we consider the problem of finding a maximum weight independent set in a matroid. More precisely, given a matroid M = (S, I), we want to compute max X∈I w(X) where w is a set function defined on 2 S measuring the weight (or utility) of any subset of S. Here we consider the case of an additive set function, characterized by the fact that w(X) = e∈X w(e) for all X ⊆ S. Function w is therefore completely characterized by the weights w(e), e ∈ S. These weights represent the utilities of the elements of S and are assumed to be strictly positive. Under this assumption, w is monotonic with respect to set inclusion, and therefore any optimal independent subset is necessarily a base of the matroid.

Finding the optimal base in a weighted matroid is a very general problem that appears in various practical contexts. Let us give some examples of matroid optimization problems in the context of combinatorial optimization and algorithmic decision theory: Uniform matroid. It is defined by I = {X ⊆ S : |X| ≤ k} for a given positive integer k ≤ n. A base is any set of cardinality k. This structure appears in social choice when the problem is to determine the best committee of size k. In this context S is the set of candidates and w measures the social utility of any candidate and any group of candidates.

Graphic matroid. Given a graph G = (V, E) where V is the set of nodes and E is the set of edges, the independent sets are the subsets of edges that do not contain any cycle (i.e. the forests). If the graph G is connected, any base will correspond to a spanning tree T of the graph. Let c : E → R + be a function defining the cost of every edge e ∈ E and let c * be any constant strictly greater than max e∈E c(e). Now if we define w(e) = c * -c(e) then finding the w-optimal base amounts to solving the minimum spanning tree problem.

Scheduling matroid. We are given n jobs that each takes one unit of processing time. All jobs are available at time 0, and job j has a profit w j and a deadline d j . The profit for job j will only be earned if the job completes by time d j . The problem is to find an ordering of the jobs that maximizes the total profit. If S = {1, . . . , n} and I = {X ⊆ S : X can be completed on time} then M = (S, I) is a matroid. If we set w(X) = j∈X w j for all X ∈ I then any optimal base gives a set of jobs maximizing the total profit.

Here we consider a matroid optimization problem where w is a set function representing the subjective preferences of a Decision Maker (DM). Moreover, we assume that w is initially not known which precludes the use of standard solving methods. Instead, we are given a (possibly empty) set P of pairs (X, Y ) ∈ I ×I such that X is known to be preferred to Y by the DM; such preference data can be obtained by asking comparison queries to the DM. Let W be the uncertainty set defined as the set of all functions w that are compatible with P, i.e. such that w(X) ≥ w(Y ) for all (X, Y ) ∈ P. In this context, we consider the minimax regret decision criterion which is commonly used within the AI community to make robust recommendations under preference imprecision. The minimax regret (MMR) can be defined using pairwise max regrets (PMR) and max regrets (MR) as follows: Definition 1. For any two sets B, B ∈ B:

P M R(B, B , W ) = max w∈W {w(B ) -w(B)} M R(B, B, W ) = max B ∈B P M R(B, B , W ) M M R(B, W ) = min B∈B M R(B, B, W )
Applying this criterion in a matroid context, an optimal base is a base that achieves the minimax regret, i.e., a base B ∈ B such that M R(B, B, W ) = M M R(B, W ). By definition, recommending any of these solutions enables to min-imize the worst-case loss (regret). Note that these solutions are necessarily optimal when M M R(B, W ) = 0 holds.

Since the MMR value can only decrease when adding new preference statements in P, it has been proposed to use the following incremental elicitation approach: progressively ask preference queries to the DM until the MMR value drops below a given threshold δ ≥ 0 which represents the maximum allowable gap to optimality [START_REF] Boutilier | Constraint-based optimization and utility elicitation using the minimax decision criterion[END_REF]. Note that if we set δ = 0, then we obtain an optimal base at the end of the execution. This approach, sometimes referred to as regret-based incremental elicitation, was efficiently used in various decision contexts, such as multicriteria decision making and voting problems (e.g., [START_REF] Lu | Robust Approximation and Incremental Elicitation in Voting Protocols[END_REF][START_REF] Benabbou | Incremental elicitation of Choquet capacities for multicriteria choice, ranking and sorting problems[END_REF]).

To implement this approach, one needs to compute the value M M R(B, W ) at every iteration step of the procedure. For matroid optimization, this may induce prohibitive computation times since it may require to compute the pairwise max regrets for all pairs of distinct bases in B. Therefore, we propose instead to combine search and regret-based incremental elicitation to reduce both computation times and number of queries. More precisely, we generate queries during the search so as to progressively reduce the set W until being able to determine a (near-)optimal base.

An Interactive Greedy Algorithm

When function w is known, the so-called Rado-Edmons theorem states that the problem of finding a maximum weight independent set in the matroid can be solved using a greedy algorithm [START_REF] Edmonds | Matroids and the greedy algorithm[END_REF]. Starting from the empty set, the idea is to iteratively select an element of maximal weight among those that could be inserted to the current independent subset without loosing the independence property. In practice, one first sorts the elements of the ground set by decreasing order and try to insert each of them successively without loosing independence. When no element can be added anymore to the current subset, the algorithm stops and the elements selected so far form the optimal base. When w is not known or imperfectly known, we can ask preference queries to the DM in order to determine his/her preference order over the elements of the ground set, or to approximate it. For the sake of efficiency, the preference elicitation can be performed during the greedy search in order to focus the elicitation task on preference information that is directly necessary to implement the algorithm. To this end we propose an interactive version of the greedy algorithm for matroid optimization, described in Algorithm 1.

Our algorithm uses the rank r(M) in lines 2-3 to reduce the number of preference queries in practice. The rank can be easily obtained for various matroids (e.g., uniform or graphic). For more complex matroids, we can use any upper bound (by default n) or precalculate r(M) by running the standard greedy algorithm for an arbitrary function w.

Note that the inner loop (lines 3-6) stops after a finite number of steps since M M R(E, W ) equals 0 when all the elements of E have been compared by the DM. Note also that Algorithm 1 with δ = 0 selects an element that is necessarily optimal at every step (i.e., the selected element is optimal for all admissible set functions w ∈ W ). Therefore, our Algorithm 1: The Interactive Greedy Algorithm

1 X ← ∅; E ← S; 2 while |X| < r(M) do 3 while MMR(E, W ) > δ/r(M) do 4
Ask the DM to compare two elements of E; 5 Update W according to the DM's answer;

6 end 7 Select ei ∈ E such that MR({ei}, E, W ) ≤ δ/r(M); 8 if X ∪ {ei} ∈ I then X ← X ∪ {ei} end; 9 E ← E \ {ei} 10 end 11 return X;
algorithm with δ = 0 is nothing else but the standard greedy algorithm [START_REF] Edmonds | Matroids and the greedy algorithm[END_REF], and it returns an optimal base. However, asking queries until minimax regrets decrease to zero may entail an important number of queries in practice (as will be observed in the numerical section). For a practical implementation of this procedure, Algorithm 1 can be used with any positive δ to construct a base with bounded regrets. This adaptation is not straightforward, as shown below: Proposition 1. Algorithm 1 returns a base B ∈ B such that M R(B, B, W ) ≤ δ holds at the end of the execution.

Proof. Let us prove that M R(B, B, W ) ≤ δ holds at the end of the execution. By definition of max regrets, it is sufficient to prove that w(B * ) -w(B) ≤ δ holds for any base B * ∈ B and for any function w ∈ W that is still admissible at the end of the execution. To do so, let us prove by induction that the following statement, denoted by P (i), holds at the end of iteration step i ∈ {1, . . . , m} of the outer loop (lines 2-10):

∃Bi ∈ B s. t.      Xi ⊆ Bi Bi\Xi ⊆ Ei w(B * ) -w(Bi) ≤ |Xi| × δ/r(M) (1a) (1b) (1c)
where m is the number of iteration steps and X i (resp. E i ) denotes the set X (resp. E) at the end of step i. In other words, we want to prove that X i can be extended into a base B i with a regret bounded above by |X i | × δ/r(M). For step i = 0 (before entering the first loop), we have X i = ∅ and E i = S (see line 1). Consequently if we set B i = B * then Equations (1a-1c) are obviously satisfied. Hence P (0) holds. Now we assume that P (i -1) holds for some step i ∈ {1, . . . , m} and we want to prove that P (i) is true. In other words, assuming that Equations (1a-1c) hold for some base B i-1 , we need to identify some base B i such that Equations (1a-1c) are satisfied by B i . According to line 8, two cases may occur: either X i-1 ∪{e i } ∈ I or X i-1 ∪{e i } ∈ I.

Case X i-1 ∪ {e i } ∈ I: In that case, we have X i = X i-1 (see lines 8-9). Let us prove that we can simply set B i = B i-1 to establish the result. First, note that the induction hypothesis (IH) directly implies that Equations (1a) and (1c) hold for B i since X i = X i-1 and B i = B i-1 . Then, for Equation (1b), we need to prove that we have

B i \X i ⊆ E i , i.e. B i-1 \X i-1 ⊆ E i . By the IH, we have B i-1 \X i-1 ⊆ E i-1 , i.e. B i-1 \X i-1 ⊆ E i ∪ {e i } (see line 9
). Moreover, we can derive e i ∈ B i-1 from axiom A 1 since X i-1 ∪{e i } ∈ I and X i-1 ⊆ B i-1 (by the IH). Hence B i-1 \X i-1 ⊆ E i holds and therefore P (i) is true.

Case X i-1 ∪ {e i } ∈ I: In that case, we have X i = X i-1 ∪ {e i } (see lines 8-9). Two cases can be distinguished:

• Case e i ∈ B i-1 : let us show that we can simply set B i = B i-1 . More precisely, for Equation (1a), we have:

Xi = Xi-1 ∪ {ei} (by hypothesis) ⊆ Bi-1 ∪ {ei} (by the IH) = Bi-1 (since ei ∈ Bi-1) = Bi (by definition)
For Equation (1b), we have:

Bi\Xi = Bi-1\(Xi-1 ∪ {ei}) ⊆ Ei-1\{ei} (by the IH) = Ei (see line 9)
For Equation (1c), we have:

w(B * )-w(Bi) = w(B * ) -w(Bi-1) (by definition) ≤ |Xi-1| × δ/r(M) (by the IH) ≤ |Xi| × δ/r(M) (since |Xi| = |Xi-1| + 1)
Hence P (i) holds.

• Case e i ∈ B i-1 : note that we have

|X i | ≤ |B i-1 | since B i-1 is a base.
Hence by iteratively applying axiom A 2 , we can conclude that there exists

Y ⊆ B i-1 \X i such that |X i ∪ Y | = |B i-1 | and X i ∪ Y ∈ I. Now we set B i = X i ∪ Y
and we want to prove that Equations (1a-1c) are satisfied by B i . Note that Equation ( 1a) is obviously true since B i = X i ∪Y (by definition). For Equation (1b), since B i \X i = Y , we only need to prove that Y ⊆ E i . We have:

Y ⊆ Bi-1\Xi (by definition) = Bi-1\(Xi-1 ∪ {ei}) (since Xi = Xi-1 ∪ {ei}) ⊆ Ei-1\{ei} (by the IH) = Ei (see line 9)
For Equation (1c), we need to prove that inequality w(B * ) -w(B i ) ≤ |X i | × δ/r(M) holds. We have:

Bi\Bi-1 = (Xi ∪ Y )\Bi-1 (by definition) = (Xi-1 ∪ {ei} ∪ Y )\Bi-1 (by hypothesis) = ({ei}∪Y )\Bi-1 (since Xi-1 ⊆ Bi-1 by the IH) = {ei} (since Y ⊆ Bi-1 and ei ∈ Bi-1)
As a consequence, since we also have

|B i | = |B i-1 |,
we know that there exists e j ∈ S\{e i } such that

B i = (B i-1 ∪ {e i })\{e j }. Now let us prove that e j ∈ E i-1 : {ej} = Bi-1\Bi = Bi-1\(Xi ∪ Y ) = Bi-1\(Xi-1 ∪ {ei} ∪ Y ) ⊆ Bi-1\Xi-1 ⊆ Ei-1
where the last inclusion is obtained by the IH. Consequently we can derive w(e i ) -w(e j ) ≤ δ/r(M) from the definition of max regrets (see line 7). Hence we have: Hence Equation (1c) holds and therefore P (i) is true.

Thus, statement P (i) holds for every step i ∈ {1, . . . , m}, and in particular P (i) is true for i = m. Since X m is a base, then we necessarily have X m = B m due to Equation (1a). Then, using Equation (1c), we obtain w

(B * ) -w(X m ) ≤ |X m | × δ/r(M) = r(M) × δ/r(M) = δ.
Finally, since Algorithm 1 returns B = X m , the result is established.

Note that Algorithm 1 generates no more than a polynomial number of queries since in the worst-case the DM is asked to compare all the elements of S (see line 4). Consequently the total number of steps of the inner loop (lines 3-6) is also polynomial. However, despite the existence of a general formalism, the implementation of Algorithm 1 may differ significantly from one application context to another. More precisely, checking whether X ∪ {e i } ∈ I can be more or less complex depending on the matroid under consideration; for the three examples used in the paper (the uniform, graphic and scheduling matroids), the independence test can be performed in polynomial time. Moreover, computing regrets can be more or less complex depending on the assumptions made on w. In this respect, an interesting option is to define w by a parametric function which is linear in its parameters (e.g., a linear combination of spline functions, or a linear multiattribute utility, or an ordered weighted average of criterion values). In that case, regret optimization can be performed in polynomial time using linear programming. Moreover, using a parametric definition of w enables to save queries because any preference statement of type w(e) > w(e ) translates into a constraint on the parameter space that reduces possible preferences over other elements.

We now present an execution of Algorithm 1 on a small instance of the scheduling matroid:

Example 1. Consider an instance of the scheduling matroid with S = {1, . . . , 8} (a set of 8 jobs of unitary length). The utility w(j) of completing job j on time is defined from an attribute vector y(j) = (y 1 (j), y 2 (j), y 3 (j)) by w(j) = λ 1 y 1 (j) + λ 2 y 2 (j) + λ 3 y 3 (j)

(2)

for some unknown λ = (λ 1 , λ 2 , λ 3 ) representing the value system of the DM. The attribute vectors attached to jobs are given below, together with their deadlines d j , j ∈ S: j 1 2 3 4 5 6 7 8 y1(j) 6 2 5 8 1 6 3 2 y2(j) 8 4 2 7 2 3 4 3 y3(j) 8 7 5 1 8 3 6 1 dj 4 1 2 4 1 3 4 1

Initially, the set Λ of admissible weighting vectors λ is defined by Λ = {λ ∈ [0, 1] 3 :

3 i=1 λ i = 1}
and induces a set W of admissible set functions w by Equation (2). To simulate the DM's answers during the execution of Algorithm 1, we assume that the actual set function w of the DM is defined by λ * = ( 6 9 , 2 9 , 1 9 ). In Figure 1, Λ is represented by triangle ABC in the space (λ 1 , λ 2 ), λ 3 being implicitly defined by λ 3 = 1 -λ 1 -λ 2 , and λ * is represented by a star inside the triangle. For this instance, we applied the standard greedy algorithm with an arbitrary w and obtained r(M) = 4. Now, let us execute Algorithm 1 with δ = 0. Step 1: Since E = S and M M R(E, W ) = 2 > 0, the DM is asked to compare two jobs, say 1 and 4. We have w(4) = 7 ≥ w(1) = 6.7 (by Equation ( 2) with λ = λ * ). Therefore the DM's answers: "job 4 is more important than job 1". Then W is updated by imposing the constraint w(4) ≥ w(1) which amounts to restricting Λ by inserting λ 2 ≥ 7 6 -3 2 λ 1 . Now Λ is represented by the triangle CDE in Figure 1. Moreover, we have M M R(E, W ) = M R({4}, E, W ) = 0 and therefore job 4 is added to the current independent set X.

Step 2:

We have E = S\{4} and M M R(E, W ) = M R({1}, E, W ) = 0. Hence we do not need to solicit the DM at this. Then job 1 is added to X (X = {4, 1}) since it can be completed on time.

Step 3:

We have E = S\{4, 1}. Again no query is needed since M M R(E, W ) = M R({6}, E, W ) = 0, and job 6 is added to X (X = {4, 1, 6}) as schedule (6, 1, 4) is feasible.

Step 4:

We have E = S\{4, 1, 6} and M M R(E, W ) = 0.67 > 0. Therefore the DM is asked to compare two jobs, say 3 and 7. Since we have w(3) = 4.3 ≥ w(7) = 3.6, the DM answers: "job 3 is more important than job 7". Then, W is updated by imposing the constraint w(3) ≥ w(7), which amounts to further restricting Λ by inserting λ 2 ≤ 3λ 1 -1. Now Λ is represented by the polyhedron CFGE in Figure 2. Moreover, since M M R(E, W ) = M R({3}, E, W ) = 0, job 3 is added to X (X = {4, 1, 6, 3}) as schedule (3, 6, 1, 4) is feasible. Finally the algorithm stops since |X| = r(M) = 4 and X = {4, 1, 6, 3} is optimal. After only two queries, we know that the actual weights of the DM is within the area CFGE in Figure 2 and this is sufficient to determine an optimal solution without any ambiguity.

An Interactive Local Search Algorithm

Local Search is another efficent way of constructing optimal solutions to matroid optimization problems [START_REF] Lee | A first course in combinatorial optimization[END_REF]). More precisely, starting from an arbitrary base, one can look for an element that can be profitably replaced by an element out of the base while preserving independence. This simple exchange principle can be iterated to progressively improve the current base until reaching a local optimum. When w is not known, this principle can be combined with a preference elicitation algorithm to collect the information that is necessary to identify improving swaps. To implement this idea, we propose Algorithm 2 where X∆Y denotes the symmetric difference defined by (X \Y )∪(Y \X) and N B is the neighborhood of base B, i.e., the set of bases that differ from B by exactly one element (thus the symmetric difference with B is of cardinality 2). The procedure ComputeInitialBase called in line 1 can be any heuristic providing a good starting solution. For instance, we can compute an optimal base for a sample of arbitrary set functions and ask the DM to compare them. The quality of the base returned by Algorithm 2 is guaranteed by the following: Proposition 2. Algorithm 2 returns a base B ∈ B such that M R(B, B, W ) ≤ δ holds at the end of the execution.

Proof. We want to prove that M R(B, B, W ) ≤ δ holds when the algorithm stops. By definition of max regrets, we only need to prove that w(B * )-w(B) ≤ δ holds for any base B * ∈ B and for any function w ∈ W that is still admissible at the end of the execution. Due to a well-know multiple exchange theorem [START_REF] Greene | Some abstract pivot algorithms[END_REF], there exists a one-to-one correspondence σ : B → B * such that B i = (B\{e i }) ∪ {σ(e i )} is a base of the matroid for every element e i ∈ B. Note that B i ∈ N B (the neighborhood of B) for all e i ∈ B since we have |B∆B i | = 2 (see line 4). Note also that we necessarily have M R(B, N B , W ) ≤ δ/r(M) at the end of the execution due to line 9. Therefore, w(B i )-w(B) ≤ δ/r(M) holds by definition of max regrets. Then, since w is additive and B i = (B\{e i }) ∪ {σ(e i )}, we obtain w(σ(e i ))-w(e i ) ≤ δ/r(M). Hence we have:

w(B * )-w(B) = w( r(M) i=1 {σ(ei)}) -w(B) (by definition of σ) = r(M) i=1 w(σ(ei)) -w(ei) (by additivity of w) ≤ r(M) i=1 δ r(M) = δ.
Note that when δ = 0, Proposition 2 ensures that Algorithm 2 yields an optimal base. Note also that Algorithm 2 generates no more than a polynomial number of queries when w is additive as computing the PMR values between two neighbors amounts to comparing two elements of the ground set. We now present an execution of Algorithm 2:

Example 2. Consider the same scheduling problem as in Example 1. Let us execute Algorithm 2 with δ = 0. Assume that ComputeInitialBase(M) returns B = {1, 2, 4, 7} corresponding to the schedule (2, 1, 4, 7) whose attribute vector is y(B) = (19,23,22).

Step 1: Base B only has 7 candidate neighbors and their attribute vectors are as follows: where B e,e is the base obtained by replacing e by e in B. Since M M R(N B , W ) = 4 > 0, the DM is asked to compare two bases, say B and B 2,6 . We have w(B 2,6 ) = 22.2 ≥ w(B) = 20.2 (by Equation ( 2)), and therefore the DM answers: "B 2,6 is better than B". Then the algorithm updates W by imposing the constraint w(B 2,6 ) ≥ w(B), which amounts to restricting Λ by inserting λ 2 ≥ 4 3 -8 3 λ 1 (see Figure 4 where Λ is represented by CDE). Now M M R(N B , W ) = 0.5 > 0 which requires to compare two other bases, say B 2,6 and B 2,3 . Here we have w(B 2,6 ) = 22.2 ≥ w(B 2,3 ) = 21.5. Therefore W is updated by imposing w(B 2,6 ) ≥ w(B 2,3 ), i.e. Λ is restricted by adding λ 2 ≥ 2 3 -λ 1 (see Figure 5 where Λ is represented by CFGD). Now the algorithm stops asking queries since M M R(N B , W ) = M R(B 2,6 , N B , W ) = 0 and then we move from solution B to solution B 2,6 for the next step corresponding to schedule (6, 1, 4, 7).

Step 2: Here N B only includes 2 candidate bases, namely B = B 2,6 and B = {1, 4, 6, 3} corresponding to the schedule (3, 6, 1, 4) whose vector is (25,20,17). Since M M R(N B , Λ) = 1.2 ≥ 0, the DM is asked to compare B and B . We have w(B ) = 23 ≥ w(B) = 22.2 and the DM answers: "B is better than B". Then W is updated by imposing w(B ) ≥ w(B) and Λ is restricted by λ 2 ≤ 3λ 1 -1 (see Figure 6 where Λ is represented by CFIH). Now M M R(N B , W ) = M R(B , N B , W ) = 0 and we set B = B for the next step.

Step 3: Here M M R(N B , W ) = M R(B, N B , W ) = 0 and therefore no question is needed. The algorithm ends by returning base B associated to (3, 6, 1, 4) which is optimal.

Experimental Results

We have implemented our algorithms on three problems corresponding to three different matroids (uniform, graphic, and scheduling). Their performances are evaluated in terms of number of queries (for local search, it includes those generated by ComputeInitialBase), computation times (given in seconds)1 , and empirical error measured as a percentage of the optimal value. Results are averaged over 30 runs. Standard deviations are given in the appendix. Before analyzing the results, let us present our experimental setting.

We consider here multi-objective optimization problems in which every matroid's element e ∈ S is evaluated by a vector x e ∈ R p where p is the number of objectives to be maximized. The criterion values are randomly drawn between 1 and 1000. The DM's preferences over elements are defined using a scalarizing function f λ : R p → R (linear in its parameter λ) by w(e) = f λ (x e ). Hence, any preference information of type "e is as least as good as e " translates into the constraint f λ (e) ≥ f λ (e ) which is linear in λ. Examples of admissible functions for f λ are weighted sums, ordered weighted average or Choquet integrals. Here we assume that f λ is a weighted sum and λ is initially unknown. Recall that, in our algorithms, we ask preference queries to the DM until MMR values drops below δ/r(M). In our tests, two values of δ have been used: δ = 0% (which guarantees that the returned solution is optimal) and δ = 20% of the initial regret (to reduce the number of preference queries). To generate informative queries, we use the Current Solution Strategy (CSS) to efficiently reduce the set of admissible weights [START_REF] Boutilier | Constraint-based optimization and utility elicitation using the minimax decision criterion[END_REF]): at each step, the DM is asked to compare a subset X achieving the minimax regret to one of its best challengers chosen in arg max Y P M R(X, Y, W ). Answers to queries are simulated using a function w * generated from a weighting vector λ * randomly generated before running the algorithms.

We now provide the results obtained with our program written in C++ tested on an Intel Core i7-9700, 3.00 GHz with 15,5 GB of RAM. Pairwise max regret optimizations were performed by CPLEX (https://www.ibm.com/analytics/cplex-optimizer).

Subset Selection Problem (Uniform Matroid). We first consider the subset selection problem corresponding to the uniform matroid. Here the size of the ground set is |S| = 50 and k = 25, i.e. I = {X ⊆ S : |X| ≤ 25}. For this matroid, the independence test simply consists in checking the cardinality constraint. In Table 1, we observe that local search is more efficient than greedy in terms of number of queries. For example, the local search algorithm performs about two times better for p = 6 (46 queries against 99). However, greedy is faster than local search in terms of computation times. This is due to the fact that minimax regrets are computed on subsets of the ground set (of size bounded by 50) for greedy search, whereas it is computed on neighborhoods (of size bounded above by 25 2 since all elementary swaps Spanning Tree Problem (Graphic Matroid). Here the elements of the ground set are the edges of a connected graph. The independence test consists in checking that the selected edges do not form a cycle. We have generated graphs with 50 nodes and a density equal to 50% with the LEMON (https://lemon.cs.elte.hu/trac/lemon). In Table 2, we observe that local search is much faster and asks less queries than greedy with δ = 0. This is mainly due to a larger size of the ground set (about 600 here against 50 for the previous problem) and to the fact that greedy constructs the optimal base from the empty set, whereas local search starts from a good complete solution (obtained with ComputeInitialBase). For both algorithms, we observe a significant improvement in terms of number of queries and times for δ = 20%, without causing a significant reduction in the quality of the returned base. We have also compared our algorithms to the interactive version of Prim algorithm proposed in (Benabbou and Perny 2015c).

It has similar performances to our greedy approach, while being outperformed by the local search we propose.

Scheduling Problem (Scheduling Matroid). We consider instances involving a ground set of 50 jobs, with deadlines randomly drawn between 1 and 25. The independence test consists in checking that there exists an order of the selected jobs compatible with their deadlines. As already observed, local search generates less queries than greedy, and the error remains very small for both algorithms. Execution times are close for δ = 0, but greedy is twice as fast as local search for δ = 20%. Note that this problem is very close to the subset selection problem but the independence test here further restricts the number of possible swaps in the local search procedure (which explains why local search is faster here).

Conclusion

We have introduced two interactive optimization methods combining preference elicitation with the exploration of independent sets in a matroid, one based on local search and the other on greedy search. The common principle used in both methods is to interleave preference queries with optimization steps to concentrate the elicitation effort on obtaining the preferential information needed to determine an optimal solution (or a near-optimal solution if we want to save some preference queries). The interest of our proposal is that it is quite general and can be implemented in various optimization problems involving a matroid structure. We have implemented these methods on three problems (subset selection, spanning tree and scheduling) and presented numerical tests showing the practical efficiency of our algorithms, in terms of computation times, number of preference queries and empirical error.

A natural continuation of this work is to extend our approach to non linear set functions. For example, submodular set functions (i.e., such that w(X ∪ Y ) + w(X ∩ Y ) ≤ w(X) + w(Y ) for all subsets X, Y of the ground set S) are of particular interest as they naturally appear in various contexts (e.g., coverage problems). Submodular utility functions are also used to guarantee a principle of diminishing returns stating that adding an element to a smaller set has more value than adding it to a larger set. Moreover, submodularity is of special interest in maximization problems over combinatorial domains because it plays a role that is analogous to concavity in continuous optimization.

The optimization of a submodular function is hard in general (it includes max-cut as special case) but approximate greedy and local search algorithms have been proposed for the optimization of submodular functions under a matroid constraint and some interesting worst case bounds on the quality of the approximations returned are known, see e.g., [START_REF] Nemhauser | An analysis of approximations for maximizing submodular set functions-I[END_REF]. The interactive approach proposed here, based on interleaving preference queries with the construction of the optimal solution, can also be implemented for submodular optimization. We did some preliminary tests which are very encouraging. The detailed analysis of such algorithms is left for further research.

Another interesting direction of research would be to consider a regret-based Bayesian approach, following some recent works [START_REF] Bourdache | Incremental Elicitation of Rank-Dependent Aggregation Functions based on Bayesian Linear Regression[END_REF], so as to handle noisy preferences (possible mistakes).

  w(B * ) -w(Bi) = w(B * )-w((Bi-1 ∪{ei})\{ej}) (by definition) = w(B * )-w(Bi-1)+(w({ei})-w({ej})) (by additivity) ≤ |Xi-1|×δ/r(M) +(w({ei})-w({ej})) (by the IH) ≤ (|Xi-1|+1)×δ/r(M) (since w(ei)-w(ej) ≤ δ/r(M)) = |Xi| × δ/r(M) (since Xi = Xi-1 ∪ {ei})

Figure 2 :

 2 Figure 1: Λ after 1 query.

Algorithm 2 :

 2 The Interactive Local Search Algorithm 1 B ← ComputeInitialBase(M ); 2 improve ← true; 3 while improve do 4 NB ← {B ∈ B : |B∆B | = 2}; 5 while MMR(NB ∪ {B}, W ) > δ/r(M) do 6 Ask one preference query to the DM; 7 Update W according to the DM's answer; B, NB, W ) ≤ δ/r(M) then improve ← false ;

Figure 3 :

 3 Figure 3: Initial set Λ.

Figure 6 :

 6 Figure 4: Λ after 1 query.

Table 1 :

 1 Greedy vs local search for the uniform matroid.

				Local Search			Greedy
	δ	p time queries error(%) time queries error(%)
		4	4	19	0.00	5	44	0.00
	0	6	14	46	0.00	10	100	0.00
		8	45	81	0.00	13	124	0.00
		4	3	14	0.01	3	18	0.00
	20	6	8	29	0.01	5	37	0.00
		8	36	36	0.02	4	38	0.01
	are allowed) for local search. The gap becomes larger as the
	number of objectives increases due to the growing number
	of Pareto non-dominated neighbors. With δ = 20%, we no-
	tice a significant reduction of the number of queries for both
	algorithms while keeping good quality solutions (the error is
	at most equal to 0.02%).

Table 2 :

 2 Greedy vs local search for the sgraphic matroid.

				Local Search			Greedy
	δ	p time queries error(%) time queries error(%)
		4	18	42	0.00	20	64	0.00
	0	6	61	105	0.00	152	155	0.00
		8	256	195	0.00	584	263	0.00
		4	17	13	0.14	10	13	0.28
	20	6	33	25	0.17	41	26	0.24
		8	69	37	0.25	99	41	0.28

Table 3 :

 3 Greedy vs local search for the scheduling matroid.

The time for answering the queries is here negligible as answers are automatically generated by artificial decision makers.

Acknowledgments

This work was supported by the Paris Ile-de-France Region.