Jérémy Omer

Michael Poss

Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty

Keywords: robust combinatorial optimization, compact formulations, column generation, cutting plane

Given a nominal combinatorial optimization problem, we consider a robust two-stages variant with polyhedral cost uncertainty, called DDID. In the first stage, DDID selects a subset of uncertain cost coefficients to be observed, and in the second-stage, DDID selects a solution to the nominal problem, where the remaining cost coefficients are still uncertain. Given a compact linear programming formulation for the nominal problem, we provide a mixed-integer linear programming (MILP) formulation for DDID. The MILP is compact if the number of constraints describing the uncertainty polytope other than lower and upper bounds is constant. In that case, the formulation leads to polynomial-time algorithms for DDID when the number of possible observations is polynomially bounded. We extend this formulation to more general nominal problems through column generation and constraint generation algorithms. We illustrate our reformulations and algorithms numerically on the selection problem, the orienteering problem, and the spanning tree problem.

Introduction

Decision-dependent information discovery (DDID) tackles optimization problems under uncertainty where the decision maker has the possibility to investigate the value of some of the uncertain parameters, thereby reducing the total amount of uncertainty. The model has innumerous applications in urban planning, project management, resource allocations, scheduling, among many others. The first DDID models where motivated by applications in offshore oilfield exploitation [START_REF] Jonsbråten | Optimization models for petroleum field exploitation[END_REF] and production planning [START_REF] Jonsbråten | A class of stochastic programs withdecision dependent random elements[END_REF]. Subsequent examples have been considered in the literature and [START_REF] Vayanos | Robust optimization with decision-dependent information discovery[END_REF] detail applications in a R&D project portfolio optimization problem, where a company must choose how to prioritize the projects in its pipeline [Solak et al., 2010, Colvin and[START_REF] Colvin | A stochastic programming approach for clinical trial planning in new drug development[END_REF]. [START_REF] Vayanos | Robust optimization with decision-dependent information discovery[END_REF] also describe a preference elicitation with real-valued recommendations where one can investigate how much users like any particular item. [START_REF] Vayanos | Robust optimization with decision-dependent information discovery[END_REF] further apply the latter model to improve the US kidney allocation system. Even more recently, [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF] consider a routing problem, which they apply to collecting medicine crates at the Alrijne hospital.

We consider in this paper a model similar to that studied by [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF] and address robust DDID where only the costs are uncertain. We further assume that the underlying nominal optimization problem is a combinatorial optimization problem, thus involving only 0/1 decision variables. Specifically, we define the following feasibility and uncertainty sets.

• W = {w ∈ {0, 1} n | Gw ≤ g } is the set characterizing the possible information discovery;

• Y = {y ∈ Z n | By ≥ b, 0 ≤ y ≤ 1 } is the feasible set of a given combinatorial optimization problem;

• P = {y ∈ R n | By ≥ b, 0 ≤ y ≤ 1 } is the relaxed polytope of Y;

• Ξ = {ξ ∈ R n | Aξ ≤ r, 0 ≤ ξ ≤ d } is an uncertainty polytope.
The DDID problem we consider is then defined by: (c i + ξ i )y i .

z DDID = min
Folklore complexity results in min-max robust combinatorial optimization [START_REF] Kouvelis | Robust discrete optimization: past successes and future challenges[END_REF] imply that computing Φ for general polytopes is N P-hard even when optimizing over Y is easy.

Observation 1. Computing Φ is N P-hard if the number of rows of A is part of the input, even if min y∈Y c T y can be solved in polynomial time.

Despite its many applications, solving DDID exactly even with the budget uncertainty polytope from Bertsimas andSim [2003, 2004] has so far remained a formidable challenge.

Literature Review

We contextualize next how (DDID) fits within the robust optimization landscape. Robust combinatorial optimization introduced by [START_REF] Kouvelis | Robust discrete optimization: past successes and future challenges[END_REF] originally considered min-max optimization problems of the form

z MM = min y∈Y max ξ∈Ξ i∈[n] (c i + ξ i )y i (Min-Max)
for discrete uncertainty sets Ξ. They proved in particular that (Min-Max) is N P-hard even when Ξ consists of only two points and Y is the feasibility set of polynomially solvable optimization problems, such as the selection problem or the shortest path problem. In fact, their results apply also to polyhedrons so these problems remain hard even when Ξ is, for instance, the convex hull of two points. Slightly later than [START_REF] Kouvelis | Robust discrete optimization: past successes and future challenges[END_REF], [START_REF] Ben-Tal | Robust convex optimization[END_REF] considered robust optimization through a different perspective, focusing on convex uncertainty sets and uncertain constraints. They developed the first compact convex reformulations for these problems. While their focus was on convex optimization, applying their reformulations to robust combinatorial optimization problems with polyhedral uncertainty leads to compact mixed-integer linear programming formulations. These can be readily solved numerically using state-of-the-art solvers like CPLEX or Gurobi, despite the theoretical hardness of these problems. An important step forward arose with the introduction of the budget uncertainty set [Bertsimas andSim, 2003, 2004] and its extension to more general knapsack constraints [START_REF] Poss | Robust combinatorial optimization with knapsack uncertainty[END_REF] (special case of Ξ where A is non-negative). Extending the seminal result of [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF], [START_REF] Poss | Robust combinatorial optimization with knapsack uncertainty[END_REF] showed that if the number of rows of A is constant, then the min-max robust counterparts of polynomial problems remains polynomial, contrasting with the difficulty proved by [START_REF] Kouvelis | Robust discrete optimization: past successes and future challenges[END_REF] for arbitrary sets. These rather theoretical results have been pursued for specific variants of the set [Goerigk et al., 2022b[START_REF] Yaman | Short Paper -A Note on Robust Combinatorial Optimization with Generalized Interval Uncertainty[END_REF] and complemented by efficient algorithms that leverage the structure of the set, e.g. for vehicle routing [START_REF] Gounaris | The robust capacitated vehicle routing problem under demand uncertainty[END_REF][START_REF] Pessoa | Branch-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertainty[END_REF], scheduling [START_REF] Tadayon | Algorithms and complexity analysis for robust single-machine scheduling problems[END_REF], lot-sizing [START_REF] Agra | A dynamic programming approach for a class of robust optimization problems[END_REF] and inventory routing [Bertsimas andThiele, 2006, Rodrigues et al., 2021], only to name a few.

After the basic robust models were introduced by [START_REF] Kouvelis | Robust discrete optimization: past successes and future challenges[END_REF] and Ben-Tal and Nemirovski [1998], many extensions have been considered in the literature. We briefly mention below two of these extensions that relate to (DDID). On the one hand, robust optimization with decision-dependent uncertainty sets allows for the uncertainty set Ξ to depend on the decision variables [START_REF] Nohadani | Optimization under decision-dependent uncertainty[END_REF][START_REF] Poss | Robust combinatorial optimization with variable budgeted uncertainty[END_REF][START_REF] Spacey | Robust software partitioning with multiple instantiation[END_REF]. On the other hand, twostage robust optimization splits the decision variables into the here-and-now decisions, and the wait-and-see ones, which can be fixed after ξ is known. Numerous papers have been published on the topic (see the survey by Yanikoglu et al. [2019]), providing exact [START_REF] Ayoub | Decomposition for adjustable robust linear optimization subject to uncertainty polytope[END_REF][START_REF] Zeng | Solving two-stage robust optimization problems using a column-and-constraint generation method[END_REF][START_REF] Zhen | Adjustable robust optimization via Fourier-Motzkin elimination[END_REF] or approximate solutions [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF] in the case of fractional recourse. The case of integer recourse is particularly difficult and, apart from the recent exact algorithms by [START_REF] Arslan | Decomposition-based approaches for a class of two-stage robust binary optimization problems[END_REF], [START_REF] Kämmerling | Oracle-based algorithms for binary two-stage robust optimization[END_REF], research has mostly focused on approximate solutions based on partitioning the uncertain set into K subsets and devising constant second-stage policies for each element of the partition, often referred to as Kadaptability. While most of these approaches lead to decomposition algorithms [Arslan et al., 2022[START_REF] Subramanyam | K-adaptability in two-stage mixed-integer robust optimization[END_REF], [START_REF] Hanasusanto | K-adaptability in two-stage robust binary programming[END_REF] were able to provide a compact reformulation for K-adaptability when only cost is uncertain. [START_REF] Bertsimas | Multistage robust mixed-integer optimization with adaptive partitions[END_REF], [START_REF] Postek | Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set[END_REF] have also proposed to partition Ξ dynamically and heuristically. While the above references aim at solving generic problems, Goerigk et al. [2022a] have focused on specific problems and proposed tailored algorithms and complexity results.

Problem (DDID) borrows ideas from both of the above extensions. On the one hand, its decisions happen in multiple stages, since the observation w is to be decided before revealing anything from Ξ, while y is chosen after the observed coefficients w • ξ have been revealed. The difference with classical two-stage robust optimization lies in the remaining uncertain parameters, ξ, to be revealed only after y is decided. Furthermore, the second-stage uncertainty set Ξ(w, ξ) is decision-dependent.

Contributions and structure of the paper

Our main result is a linear programming relaxation for Φ(w) that is exact whenever conv(Y) = P and compact when the number of rows of A is constant. The linear program for Φ(w) is then dualized and linearized to provide a mixed-integer linear programming relaxation for (DDID) that is exact whenever conv(Y) = P and compact when the number of rows of A is constant. An adhoc study is carried out to strengthen significantly the linearized MILP. Interestingly, our linear programming relaxation involves an extension of the result of [START_REF] Poss | Robust combinatorial optimization with knapsack uncertainty[END_REF] to arbitrary uncertainty polytopes.

Then, we discuss how these relaxations can be made exact for problems for which conv(Y) ⊂ P. First, we propose a convexification approach based on a Dantzig-Wolfe reformulation of conv(Y), leading to column generation and branch-and-price algorithms. Second, we propose a cutting-plane algorithm starting from P and iteratively strengthening the outer approximation through strong valid inequalities. Both approaches can be turned into heuristic algorithms by stopping the variable or constraint generation at any time.

The resulting exact and heuristic algorithms are assessed numerically on different problems motivated by the literature, namely the selection, the orienteering problem, and the spanning tree problem. Results illustrate how these approaches are able to obtain exact solutions, often for the first time, on instances inspired by the scientific literature [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF][START_REF] Vayanos | Robust optimization with decision-dependent information discovery[END_REF]. They also illustrate the efficiency of our heuristic column generation-based algorithm and exact cutting-plane algorithm.

We provide also more theoretical insights into the problem. First, we illustrate extreme cases in which (DDID) is equal to either its min-max or max-min counterpart. The former case arises when considering linear programs rather than discrete problems, while the latter arises when the dimension of Ξ is too small, such as the factor model used in the literature [START_REF] Vayanos | Robust optimization with decision-dependent information discovery[END_REF]. Second, we show that computing Φ(w) can alternatively be done by optimizing a polynomial number of linear functions over Y. This leads to polynomial time algorithms for (DDID) whenever the nominal problems are polynomially solvable and |W| is polynomially bounded. While this result is mostly of theoretical interest, since it relies on the ellipsoid algorithm, the underlying cutting-plane algorithm can be used to compute Φ(w) whenever conv(Y) ⊂ P.

The rest of the paper is structured as follows. In the next section, we detail the relationship between (DDID) and its min-max and max-min counterparts, and provide the counterpart of the result of [START_REF] Poss | Robust combinatorial optimization with knapsack uncertainty[END_REF] for general polytopes (thus not assuming that A ≥ 0). We provide in Section 3 the polynomial-time algorithm and linear programming reformulation for Φ(w). We dualize and linearize this formulation in Section 4, and discuss in Section 5 extensions to problems for which conv(Y) ⊂ P. Section 6 presents our numerical experiments. The appendix contains a comparison with the algorithm of [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF], the proofs of the linearization of Φ(w) and the dominance relationships used in the column generation algorithms. It provides the reformulation proposed by [START_REF] Vayanos | Robust optimization with decision-dependent information discovery[END_REF] for K-adaptability, and additional statistics on the algorithms applied to the orienteering problem.

Notations

We let s be the number of rows of matrix A. For any w ∈ {0, 1} n , we denote by W 1 the set of indices over which w is equal to 1, and W 0 its complementary. For any integer x, we denote the set {1, . . . , x} by [n]. For any real number x, [x] + denotes the positive part of x. For any set S, we denote its convex hull by conv(S) and the set of its extreme points by ext(S). The identity matrix is denoted Id, and 1 and 0 represent vectors of all ones and zeros, respectively.

Preliminary results and trivial cases

Relationship with robust counterparts

If no cost coefficient can be observed (i.e., W = {0}), we see that (DDID) falls down to (Min-Max). Going one step further, we note that when every cost coefficient can be observed (i.e., 1 ∈ W), (DDID) becomes the (robust) wait-and-see problem, formally defined as

z WS = max ξ∈Ξ min y∈Y i∈[n] (c i + ξ i )y i , (Wait&See)
where a worst-case cost vector can be inferred preliminary to the solution of the combinatorial problem. As a consequence the optimal value of the (DDID) can be bounded as follows.

(c i + ξ i )y i ≤ min y∈Y max ξ∈Ξ i∈[n] (c i + ξ i )y i ⇔ z WS ≤ z DDID ≤ z MM . (1)
We note that if 1 ∈ W, it is trivially an optimal solution to (DDID). As considering this trivial solution raises a technical special case in our reformulations, we rather assume it does not belong to W.

Assumption 1. Set W does not contain the vector of all ones.

We illustrate below the above inequalities on the selection problem with budget uncertainty.

Example 1. Consider an instance of (DDID) where Y = y ∈ {0, 1} 5 i∈ [START_REF] Goerigk | Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty[END_REF] y i = 1 is the selection feasibility set, W = w ∈ {0, 1} 5 i∈ [START_REF] Goerigk | Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty[END_REF] w i = 1 amounts to choose one item among 5 and the uncertainty is the budget uncertainty set from [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF] with nominal values c = (1, 2, 3, 4, 5) and deviations d = [START_REF] Goerigk | Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty[END_REF]4,3,2,1), that is,

Ξ = ξ ∈ R 5 i∈[5] ξ i d i ≤ 1, 0 ≤ ξ i ≤ d i , i ∈ [5] .
Let us first look at the optimal solution to (Min-Max). Since a unique item j is selected in any feasible solution y ∈ Y,

max ξ∈Ξ i∈[n] (c i + ξ i )y i = max ξ∈Ξ c j + ξ j = c j + d j = 6.
Hence, z MM = 6. In the case of (Wait&See), the adversary needs to increase the value of the cheapest item j, thus solving max ξ∈Ξ min j (c j + ξ j ). After some linear algebra, one obtains z WS = 162/47 ≈ 3.4. Consider now (DDID), where we select one item after having observed one of the items cost. Assume that we observe item 1 so the uncertain cost ξ 1 of item 1 is revealed. If y selects item 1, the solution cost is c 1 + ξ1 . If, we select instead item j = 1, the resulting solution cost is c j + d j (1 -ξ1 d 1 ). The previous value is minimized for j = 2, yielding 2 + 4(1 -ξ1 5 ). The worst-case scenario for ξ thus maximizes min{c 1 + ξ1 , 2 + 4(1 -ξ1 5 }, which is a concave piece-wise linear function with maximum value 34/9 reached at ξ1 = 25/9. Therefore, observing item 1 yields an objective value of z DDID = 34/9 ≈ 3.8, one readily verifies by examination that this is the optimal solution to the problem.

We detail next two situations in which one of the bounds is actually equal to z DDID . First, consider the linear programming counterpart of (DDID), in which the feasibility set of the optimization problem consists of a polytope, Q. In this context, it is well-known that

min y∈Q max ξ∈Ξ i∈[n] (c i + ξ i )y i = max ξ∈Ξ min y∈Q i∈[n] (c i + ξ i )y i , (2)
meaning that the robust optimization problem is equivalent to (Wait&See). Combining (2) with (1) immediately shows that (DDID) is equivalent to (Min-Max) in this context.

Observation 2. If Y is a polytope instead of a set of integer points, then z WS = z DDID = z MM .

Observation 2 illustrates the necessity to consider discrete variables for (DDID) to provide an advantage over the min-max approach. In particular, equality (2) does not hold if one optimizes over a discrete set rather than a polytope since in the former case the domain of variables y is no longer convex.

When we are not in one of the two extreme cases where W = {0} or 1 ∈ W, we may still develop some geometrical intuition on the role of information discovery. It may indeed be convenient to see the process of observation as a reduction of the dimension of the uncertainty polytope. To be more accurate, we partition the uncertainty constraints as A + ξ ≤ a + , A = ξ ≤ a = such that A = ξ = a = for all ξ ∈ Ξ and there exists ξ ∈ Ξ with A + ξ < a + . The dimension of polytope Ξ is then given by dim(Ξ) = n -rank(A = ). We also define e i the i th vector of the canonical basis and for I ⊂ [n], E I ∈ R |I|×n the matrix whose rows are the e T i , i ∈ I.

Observation 3. Let w ∈ W, ξ ∈ Ξ and W 1 = {i ∈ [n] | w i = 1 }, then dim Ξ(w, ξ) ≤ n -rank A = E W 1 . Proof. By definition, Ξ(w, ξ) = ξ ∈ R n A + ξ ≤ a + , A = ξ ≤ a = , E W 1 ξ = E W 1 ξ . We know that for all ξ ∈ Ξ(w, ξ), A = E W 1 ξ = a = E W 1 ξ , so dim Ξ(w, ξ) ≤ n -rank A = E W 1 .
In the literature, it is usual to consider the information discovery set

W sel =    w ∈ {0, 1} n i∈[n] w i ≤ q    ,
where one can select up to q cost coefficients, q ∈ Z + . This discovery set allows to provide a more specific description of information discovery. Indeed, we see that matrix

A = E W 1
corresponds to the completion of the rows of A = with row vectors of the canonical basis of R n . We thus know that we may choose w ∈ W sel such that rank

A = E W 1 = rank(A = ) + q if rank(A = ) > n -q, and rank A = E W 1 = n if rank (A = ) ≤ n -q.
We deduce the following.

Corollary 1. There is w ∈ W sel such that, for any ξ ∈ Ξ, dim Ξ(w, ξ) ≤ max{0, dim(Ξ) -q}.

Interestingly, Corollary 1 implies that picking w * ∈ W sel (through basic linear algebra) that most reduces the dimension of Ξ may substantially simplify (DDID) when the dimension of Ξ is not greater than q.

Observation 4. If W = W sel and dim(Ξ) ≤ q, then z DDID = z WS .

Proof. Corollary 1 implies that there exists w * ∈ W sel such that Ξ(w

* , ξ) = { ξ}, ∀ ξ ∈ Ξ. Hence, Φ(w * ) = maxξ ∈Ξ min y∈Y i∈[n] (c i + ξi )y i = z WS

Reformulating the robust counterpart

We generalize below a classical result from the literature [Bertsimas andSim, 2003, Poss, 2018] that essentially shows that, when y is fixed, maximizing over Ξ in (Min-Max) amounts to take the minimum among O(n s ) different affine functions of y. The result involves enumerating over the set defined next. First, let A all ⊆ R s contain the unique solution of each linearly independent subsystem of s equations of

  A T A T Id   α =   1 0 0   . (3)
We define A = A all ∩ R s + , thus keeping only the non-negative vectors in A all .

Observation 5. |A| ∈ O(n s ).

Proof. Forming a linearly independent subsystem of s equations of (3) amounts to choose 0 ≤ k ≤ s rows of matrix A T and s -k rows of matrix Id. Then, for each row of matrix A T that is chosen, we must further decide between the rhs 0 and 1. We obtain

|A| ≤ s k=0 n k 2 k ≤ s×n s ×2 s ∈ O(n s ).
The next result is stated in the context of this paper, thus involving the decision-dependent uncertainty set Ξ(w, ξ) and the set W 0 of components that have not been observed. Nevertheless, one readily writes the counterpart of the result in the context of (Min-Max), by considering instead a polytope Ξ, together with

W 0 = [n] and W 1 = ∅. Theorem 1. Let y ∈ {0, 1} n . We have max ξ∈Ξ(w, ξ) i∈W 0 (c i + ξ i )y i = min α∈A    β α,0 (w, ξ) + i∈W 0 (c i + β α,i )y i    ,
where for each α ∈ A,

β α,0 (w, ξ) = k∈[s]   r k - i∈W 1 a ki ξi   α k + i∈W 0 d i   - k∈[s] a ki α k   + ,
and for each i ∈ [n], α ∈ A,

β α,i = d i     1 - k∈[s] a ki α k   + -   - k∈[s] a ki α k   +   . Proof. Observe first that max ξ∈Ξ(w, ξ) i∈W 0 (c i + ξ i )y i = max ξ ∈Ξ i∈W 0 (c i + ξ i )y i , (4)
where

Ξ =    ξ ∈ R |W 0 | i∈W 0 a ki ξ i ≤ r k - i∈W 1 a ik ξi , k ∈ [s], 0 ≤ ξ i ≤ d i , i ∈ W 0    is the projection of Ξ(w, ξ) into the subset of coordinates indexed by W 0 . Let us denote r k - i∈W 1 a ki ξi by rk for each k ∈ [s]. Notice that by Assumption 1, W 1 < n so Ξ is non-empty.
Let us denote the dual variables of the constraints of Ξ by α k and π i , respectively. Dualizing the maximization problem in the right-hand-side of (4) yields max

ξ ∈Ξ i∈W 0 (c i + ξ i )y i = i∈W 0 c i y i + min    k∈[s] rk α k + i∈W 0 d i π i k∈[s] a ki α k + π i ≥ y i , ∀i ∈ W 0 , α, π ≥ 0    = i∈W 0 c i y i + min (α,π)∈Q(w,y)    k∈[s] rk α k + i∈W 0 d i π i    , (5)
where Q(w, y) is the polyhedron

Q(w, y) =    (α, π) ∈ R s+|W 0 | k∈[s] a ki α k + π i ≥ y i , ∀i ∈ W 0 , α, π ≥ 0    .
We show below that any extreme point (α * , π * ) of Q(w, y) satisfies

π * i =   y i - k∈[s] a ki α * k   + (6)
for each i ∈ W 0 , and α * ∈ A. Let n 0 = |W 0 | denote the dimension of π. The former follows immediately from the fact that each π i appears only in the constraints π i ≥ 0 and k∈[s] a ki α k + π i ≥ y i . Then, being an extreme point, (α * , π * ) is necessarily the unique solution of a linearly independent subsystem of n 0 + s equalities among the constraints of Q(w, y). Among these, n 0 are the equalities mentionned in ( 6). The remaining s equalities are taken among the non-negativity 6), thus corresponding to π * i = 0. Therefore, α * ∈ A follows from y ∈ {0, 1} n . Since the minimum of ( 5) is reached at least at one of the extreme point of Q(w, y), we have min

constraints {α * k ≥ 0 | k ∈ [s] }, and the constraints of k∈[s] a ki α * k + π * i ≥ y i i ∈ W 0 not used in (
(α,π)∈Q(w,y)    k∈[s] rk α k + i∈W 0 d i π i    ≥ min α∈A    k∈[s] rk α k + i∈W 0 d i   y i - k∈[s] a ki α k   +    . (7)
To prove the reverse inequality, we consider any α ∈ A ⊂ R s + and define

π i = y i -k∈[s] a ki α k + for i ∈ [n], so (α, π) ∈ Q(w, y).
Observing that y i ∈ {0, 1} for each i ∈ W 0 , we can reformulate the objective of the rhs of ( 7) to make it linear in y

min α∈A    k∈[s] rk α k + i∈W 0 d i   y i   1 - k∈[s] a ki α k   + + (1 -y i )   - k∈[s] a ki α k   +      = min α∈A    k∈[s] rk α k + i∈W 0 d i   - k∈[s] a ki α k   + + i∈W 0 d i y i     1 - k∈[s] a ki α k   + -   - k∈[s] a ki α k   +      Applying Theorem 1 to (Min-Max) (hence W 0 = [n]
and W 1 = ∅) and switching the two minimizations immediately leads to the following.

Corollary 2. Problem (Min-Max) amounts to solve O(n s ) nominal problems min y∈Y (c + β α ) T y.

Computing Φ

Constraint generation

We present next an algorithm for computing Φ that relies on constraint generation. The first step of the approach described next applies an epigraphic reformulation to the outermost maximization problem

Φ(w) = max ω (8) s.t. ω ≤ min y∈Y max ξ∈Ξ(w, ξ) i∈[n] (c i + ξ i )y i (9) ξ ∈ Ξ. ( 10
)
Then, we introduce dual variables α, π and γ so that linear programming duality yields max ξ∈Ξ(w, ξ)

ξ T y = min (α,π,γ)∈D(y) r T α + d T π + (w • ξ) T γ = min (α,π,γ)∈ext(D(y)) r T α + d T π + (w • ξ) T γ, ( 11
)
where 11) into the right-hand side of ( 9) leads to reformulating Φ(w) as a linear program with many constraints max ω (12)

D(y) = (α, π, γ) ∈ R 2n+s A T α + Idπ + w • γ ≥ y is the dual polytope. Plugging (
s.t. ω ≤ c T y + r T α + d T π + (w • ξ) T γ, ∀y ∈ Y, (α, π, γ) ∈ ext(D(y)) (13) ξ ∈ Ξ. ( 14
)
We now study the complexity of the separation problem associated with constraints (13). Using (11) in the reverse direction, we see that a given candidate solution (ω * , ξ * ) ∈ R × Ξ is feasible for (13) if and only if

ω * ≤ min y∈Y max ξ∈Ξ(w, ξ * ) i∈[n] (c i + ξ i )y i . (15)
Thus, checking whether (ω * , ξ * ) is feasible amounts to solving a problem with same form as (Min-Max). Corollary 2 implies that the right-hand-side of ( 15) can be computed by solving min y∈Y ξ T y for at most O(n s ) vectors ξ. The overall approach leads to a cutting-plane algorithm for computing Φ(w), the separation problem of which is not harder than the nominal problem min y∈Y ξ T y. Then, using the equivalence between separation and optimization [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF], we obtain a polynomial algorithm for computing Φ(w) whenever the nominal counterpart of the problem is polynomially solvable. We observe that the above algorithm is reminiscent of the one developed by [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF] to compute Φ(w), the differences between the two are detailed in Appendix A.

Proposition 1. If the nominal counterpart is polynomially solvable and s is constant, then Φ(w) can be computed in polynomial time.

Assuming that the nominal counterpart is polynomially solvable, Observation 1 and Proposition 1 cover the two possible situations. If s is part of the input, computing Φ(w) is in general N P-hard. Otherwise, it can be computed in polynomial time. Yet, the above algorithm involves the ellipsoid algorithm so it is hardly of any practical interest. For this reason, we provide in the next subsection an alternative approach to computing Φ(w), more amenable to numerical implementations. Before that, we further elaborate on the implications of Proposition 1.

Corollary 3. If |W| is polynomially bounded, the nominal counterpart is polynomially solvable, and s is constant, then (DDID) can be solved in polynomial time.

Proof. Enumerate all w ∈ W and compute Φ(w) for each of them, then return the minimum value.

Corollary 3 implies, for instance, that if P is the matching polytope [START_REF] Pulleyblank | Faces of matching polyhedra[END_REF] (see also [Schrijver, 2003, Theorem 25.5]), the resulting (DDID) is easy. We note that the case of the matching polytope is particular in the sense that, although one can efficiently optimize over this polytope (e.g. [Schrijver, 2003, Section 25.5c]), its description requires exponentially many inequalities in general. Contrasting with the previous example, the polytopes of many polynomial combinatorial optimization problems can be described by polynomially many inequalities. This is the case for the shortest path problem, the minimum spanning tree problem (using the extended multi-commodity flow formulation [START_REF] Magnanti | Optimal trees[END_REF]), or minimizing the weighted sum of completion times (e.g. [Queyranne and Schulz, 1994, Section 4.1]), to name a few. For such problems, we provide below an alternative way to compute Φ that involves solving a compact linear program.

Linear programming formulation

We focus next on an optimization problem having a feasibility set described by a known polynomial number of linear inequalities, meaning that conv(Y) = P. We prove that under this additional assumption, Φ(w) amounts to solving a compact linear program.

Theorem 2. Let w ∈ W. If conv(Y) = P, then Φ(w) =                              max ω s.t. ω ≤ k∈[s]   r k - i∈W 1 a ki ξi   α k + i∈W 0 d i   - k∈[s] a ki α k   + + b T λ α - i∈[n] π α,i , ∀α ∈ A (B •,i ) T λ α -π α,i ≤ c i + ξi , ∀α ∈ A, ∀i ∈ W 1 (B •,i ) T λ α -π α,i ≤ c i + β α,i , ∀α ∈ A, ∀i ∈ W 0 ξ ∈ Ξ λ, π ≥ 0 ( 16
)
where for each i ∈

[n], α ∈ A, β α,i = 1 -k∈[s] a ki α k + --k∈[s] a ki α k + . Proof. Observe that max ξ∈Ξ(w, ξ) i∈[n] ξ i y i = i∈W 1 ξi y i + max ξ∈Ξ(w, ξ) i∈W 0 ξ i y i . (17)
Applying ( 17) to the epigraphic reformulation ( 8)-( 10) presented previously yields max ω (18)

s.t. ω ≤ min y∈Y   i∈W 1 (c i + ξi )y i + max ξ∈Ξ(w, ξ) i∈W 0 (c i + ξ i )y i   (19) ξ ∈ Ξ. ( 20
)
The main idea of the proof that follows reformulates (19) through two ingredients: we reformulate the maximization over ξ using Theorem 1 (thus minimizing y over Y to use that y is binary), and dualize the minimization over y (thus using that conv(Y) = P to minimize y over P instead of Y).

Let us now work out the details of the above two ideas. Applying Theorem 1 to the last term of (19) yields max ξ∈Ξ(w, ξ) i∈W 0

(c i + ξ i )y i = min α∈A    β α,0 (w, ξ) + i∈W 0 (c i + β α,i )y i    .
Plugging the above expression into the right-hand-side of ( 19) and swapping the minimizations, we obtain

(19) ⇔ ω ≤ min α∈A    β α,0 (w, ξ) + min y∈Y i∈W 1 (c i + ξi )y i + i∈W 0 (c i + β α,i )y i    .
The above may be written equivalently with n + 1 independent constraints:

(19) ⇔ ω ≤ β α,0 (w, ξ) + min y∈Y i∈W 1 (c i + ξi )y i + i∈W 0 (c i + β α,i )y i , ∀α ∈ A. ( 21
)
Thanks to the integrality of P, we can relax the integrality restrictions in Y and replace the inner minimization over Y by the minimization over 21). For each constraint α ∈ A, we then define the dual variables λ α and π α associated respectively with constraints By ≥ b and y ≤ 1. We then dualize the minimization problem over P to get the following equivalent constraint:

P = {y ∈ R n | By ≥ b, 0 ≤ y ≤ 1 } in each constraint of (
ω ≤ β α,0 (w, ξ) + max λα,πα b T λ α - i∈[n] π α,i s.t. (B •,i ) T λ α -π α,i ≤ c i + ξi , ∀i ∈ W 1 (B •,i ) T λ α -π α,i ≤ c i + β α,i , ∀i ∈ W 0 λ α , π α ≥ 0
The maximization over λ α and π α is in the right-hand-side of a ≤ inequality, so the above is equivalent to the following set of constraints.

ω ≤ β α,0 (w, ξ) + b T λ α - i∈[n] π α,i (B •,i ) T λ α -π α,i ≤ c i + ξi , ∀i ∈ W 1 (B •,i ) T λ α -π α,i ≤ c i + β α,i , ∀i ∈ W 0 λ α , π α ≥ 0
Replacing (19) with the corresponding |A| sets of constraints provides the result.

Solving the full problem

We describe below the compact reformulations obtained for (DDID) by dualizing and linearizing the formulation proposed in Theorem 2 using classical techniques.

Proposition 2. If conv(Y) = P, then (DDID) is equivalent to (DDID-WIP), defined as

min α∈A   r T α u α + i∈[n] d i   - k∈[s] a ki α k   + u 0 α,i + i∈[n] c i y α,i + i∈[n] β α,i y 0 α,i   + d T σ + r T µ s.t. α∈A u α = 1 k∈[s] a ki µ k + σ i ≥ - k∈[s] α∈A a ki α k u α + α∈A y α,i -M i (1 -w i ), ∀i ∈ [n] By α ≥ u α b, ∀α ∈ A y α,i ≤ u α , ∀α ∈ A, i ∈ [n] y 0 α,i ≥ y α,i -w i , ∀α ∈ A, i ∈ [n] u 0 α,i ≥ u α -w i , ∀α ∈ A, i ∈ [n] w ∈ W u, u 0 , y, y 0 , µ, σ ≥ 0, (DDID-WIP)
where

M i = 1 + max α∈A -k∈[s] a ki α k .
Proof. See Appendix B.1.

Formulation (DDID-WIP) includes the decision on w with the most natural linearization of the products involving those variables. It is possible though to strengthen this formulation by projecting both y and u variables on the two sets W 1 and W 0 .

Proposition 3. If conv(Y) = P, then (DDID) is equivalent to (DDID-SIP), defined as min α∈A   r T α u α + i∈[n] d i   - k∈[s] a ki α k   + u 0 α,i + i∈[n] c i y α,i + i∈[n] β α,i y 0 α,i   + d T σ + r T µ s.t. α∈A u α = 1 k∈[s] a ki µ k + σ i ≥ - k∈[s] α∈A a ki α k u 1 α,i + α∈A y 1 α,i , ∀i ∈ [n], By α ≥ u α b, ∀α ∈ A, y α,i ≤ u α , ∀α ∈ A, i ∈ [n] u α = u 0 α,i + u 1 α,i , ∀α ∈ A, i ∈ [n], α∈A u 0 α,i ≤ 1 -w i , ∀i ∈ [n], α∈A u 1 α,i ≤ w i , ∀i ∈ [n], Gu 1 α ≤ u α g ∀α ∈ A, y α,i = y 0 α,i + y 1 α,i , ∀α ∈ A, i ∈ [n] y 0 α,i ≤ u 0 α,i , ∀α ∈ A, i ∈ [n] y 1 α,i ≤ u 1 α,i , ∀α ∈ A, i ∈ [n] w ∈ W u, u 0 , u 1 , y, y 0 , y 1 , σ, µ ≥ 0. (DDID-SIP) Proof. See Appendix B.2.
We show below that the formulation of Proposition 3 is in general stronger than the one provided by Proposition 2. Numerical evidence shows that the inclusion may hold strictly.

Proposition 4. Let S weak and S strong denote the projections on w of the formulations (DDID-WIP) and (DDID-SIP), respectively. It holds that S strong ⊆ S weak .

Proof. See Appendix B.3.

The results from the previous section illustrate that whenever conv(Y) = P and |W| is polynomially bounded, (DDID) is polynomially solvable. The reformulations obtained above show instead that when we assume only that |W| can be formulated as a mixed-integer set, s is constant, and conv(Y) = P, then (DDID) is in N P.

Extensions to the case conv(Y) ⊂ P

The results presented so far rely on the fact that conv(Y) = P, meaning that we know a compact description for the convex hull of the set of all feasible solutions to the nominal optimization problem. In particular, the nominal problem, which optimizes a linear function over Y, has so far been assumed to be polynomially solvable. We present next two possible extensions of our reformulations that can address DDID counterparts of problems for which such a compact description is not known.

Convexification

Our first approach to handle N P-hard problems amounts to consider a Dantzig-Wolfe reformulation of set Y. Let us enumerate this set as Y = {ỹ 1 , . . . , ỹt }. Introducing the convex multipliers λ α,1 , . . . , λ α,t for each α ∈ A, we can substitute y α with s∈[t] λ α,s ỹs , and the constraints By α ≥ u α b with the convexification constraints, so (DDID-SIP) becomes

min α∈A   r T α u α + i∈[n] d i   - k∈[s] a ki α k   + u 0 α,i + i∈[n] s∈[t] c i λ α,s ỹs,i + i∈[n] β α,i y 0 α,i   + d T σ + r T µ s.t. s∈[t] λ α,s = u α , ∀α ∈ A, [ν α ] s∈[t] λ α,s ỹs,i = y 0 α,i + y 1 α,i , ∀α ∈ A, i ∈ [n], [ρ α i ] α∈A u α = 1 k∈[s] a ki µ k + σ i ≥ - k∈[s] α∈A a ki α k u 1 α,i + α∈A y 1 α,i , ∀i ∈ [n], u α ≤ 1 -w α , ∀α ∈ A, u α = u 0 α,i + u 1 α,i , ∀α ∈ A, i ∈ [n], (DDID-CG) α∈A u 0 α,i ≤ 1 -w i , ∀i ∈ [n], α∈A u 1 α,i ≤ w i , ∀i ∈ [n], Gu 1 α ≤ u α g, ∀α ∈ A, y 0 α,i ≤ u 0 α,i , ∀α ∈ A, i ∈ [n] y 1 α,i ≤ u 1 α,i , ∀α ∈ A, i ∈ [n] w ∈ W u, u 0 , u 1 , y 0 , y 1 , σ, λ ≥ 0.
where the right brackets denote dual variables. Formulation (DDID-CG) can be used in two different ways. First, for some strongly constrained problems, it may happen that t is a moderately large integer so the formulation can be directly fed into a solver. In this case, if all costs are positive, one may further reduce the value of t by observing that only minimal ỹ, with respect to inclusion, need to be considered.

(c i + ξ i )ỹ s,i > z MM , (22)
and let Ỹ = Y \ {ỹ s } and zDDID denote the optimal value of (DDID) associated to Ỹ. We have z DDID = zDDID .

Proof. See Appendix C.2.

Despite Observations 6 and 7, one cannot expect, in general, to be able to handle the entire problem at once. This leads to considering column-generation based algorithms which, essentially, generate appropriate subsets T α ⊆ [t], α ∈ A, on the fly by exploiting dual information (see for instance [START_REF] Wolsey | Integer programming[END_REF]). Let us describe this idea more precisely in what follows, denoting by DLR(T ) the dual of the linear relaxation of (DDID-CG) associated to subsets T α , α ∈ A, while DLR denotes the dual of the full linear relaxation of (DDID-CG). Let υ denote the vector of all dual variables and consider an optimal dual solution υ * of DLR(T ). Notice that DLR has the same variables as DLR(T ) but contains additional constraints. Hence, solution υ * is feasible for DLR as soon as it satisfies these additional constraints. In fact, the only constraints of DLR that are missing in DLR(T ) are those associated with the primal variables λ α,s for each α ∈ A and s ∈

[t] \ T α , namely i∈[n] c i ỹs,i - i∈[n] ρ α * i ỹs,i -ν α * ≥ 0. ( 23
)
Therefore, all constraints (23) are satisfied by υ * if and only if for each α ∈ A, the optimal solution of the following optimization problem is not smaller than

ν α * min y∈Y    i∈[n] c i y i - i∈[n] ρ α * i y i    . ( 24
)
If, on the contrary, there exists α ∈ A for which we are able to identify ỹs ∈ Y such that the corresponding dual constraint ( 23) is violated by υ * , we add the corresponding index s to T α and solve the resulting linear program DLR(T ) again.

The above procedure generates all required variables of (DDID-CG) at the root node of the branch-and-bound tree solving the problem. However, these do not cover all the variables that may be generated in the subsequent linear programs that result from adding the branching constraints. Repeating the above procedure at each node of the branch-and-bound tree leads to a branch-andprice algorithm. While this particular type of branch-and-price algorithm is of a rather simple type, as it involves no branching on the set of dynamic variables, λ, its efficient implementation involves clever engineering techniques, such as node selection, heuristic, and stabilization, which is beyond the scope of the current work. Instead, we limit ourselves to the column generation at the root node only, and then feed the resulting MILP to a solver. Doing so, we end up with a heuristic algorithm for (DDID), because the returned observation w * will have considered only a subset of conv(Y). Another direct consequence of the above discussion is that the above column generation algorithm provides yet another way to compute Φ(w).

Observation 8. Φ(w) can be computed by fixing w in (DDID-CG) and solving the resulting linear program with column generation.

Cutting-plane algorithm

The second approach to handling conv(Y) ⊂ P involves the iterative generation of conv(Y) through valid inequalities, essentially cycling between the solution of a sequence of problems of type (DDID-SIP) and the separation of solutions y from conv(Y). The first ingredient of this algorithm is thus a separation oracle for conv(Y) as detailed next.

Assumption 2. Given y ∈ R n , we have a separation oracle that returns either true if y ∈ conv(Y) or a hyperplane separating y from conv(Y).

The second ingredient of the algorithm is the extension of (DDID-SIP) to any polytope P = {y ∈ R n | B y ≥ b , 0 ≤ y ≤ 1 }. Specifically, we introduce the concatenated decision vector θ = (w, u, u 0 , u 1 , y, y 0 , y 1 , σ) and define Θ(P ) as the feasible set defined by all constraints of (DDID-SIP), using (B , b ) instead of (B, b). Introducing further f for the objective function of (DDID-SIP), we can formulate the following MILP

z DDID P = min θ∈Θ(P ) f (θ), (25)
Observe that when P = conv(Y), the condition of Proposition 3 is satisfied and (25) coincides with the exact reformulation (DDID-SIP), so z DDID P = z DDID in this case.

Observation 9. If conv(Y) ⊂ P , then min θ∈Θ(P ) f (θ) is a relaxation of the exact formulation min θ∈Θ(conv(Y)) f (θ).

Proof. We see that conv(Y) ⊆ P implies Θ(conv(Y)) ⊆ Θ(P ), proving the statement.

The algorithm starts with P 0 = P and solves (25), yielding the optimal solution θ * and its cost z DDID P 0

. Then, observe that θ * ∈ Θ(conv(Y)) if and only if for each α ∈ A, either u α = 0 and y * α = 0 or y * α ∈ conv(Y). Hence, we can use Assumption 2 to check whether θ * ∈ Θ(conv(Y)). If this is the case, Observation 9 implies that θ * is optimal for the exact formulation min θ∈Θ(conv(Y)) f (θ) so z DDID P 0 = z DDID . Otherwise, we rely on the oracle from Assumption 2 to obtain a separating hyperplane h T y ≤ h 0 , define

P 1 = P 0 ∩ y ∈ R n h T y ≤ h 0 ,
and repeat the procedure.

We note that an alternative stopping criterion involves the computation of Φ(w * ) at each iteration, which can be computed by using one of the algorithms proposed in Section 3 or the column-generation algorithm described in Section 5.1.

Observation 10. Let θ * = (w * , u * , u 0 * , u 1 * , y * , y 0 * , y 1 * , σ * , µ * ) be the solution returned at the i-th iteration of the algorithm. If Φ(w * ) ≤ z DDID P i , then z DDID

P i = z DDID .
Proof. For any w ∈ W, we have that Φ(w) ≥ z DDID ≥ z DDID P i

, where the second inequality follows from Observation 9. Combining the above with Φ(w * ) ≤ z DDID P i proves the result.

The resulting algorithm is finitely convergent if the oracle returns facet-defining inequalities. In practice, one may interrupt the algorithm at any time and consider the solution w * returned after a certain number of iterations.

Numerical experiments

We next describe the numerical assessment of the different formulations and algorithms presented thus far. All our experiments have been realized in Julia language [START_REF] Bezanson | Julia: A fresh approach to numerical computing[END_REF], using JuMP [START_REF] Dunning | Jump: A modeling language for mathematical optimization[END_REF] to interface the mixed integer linear programming (MILP) solver CPLEX 20.01. We ran our experiments on a processor Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz, letting CPLEX handle the parallelism and reporting the total CPU times. We set the same time limit to two hours in all our experiments. The source code of every algorithm is publicly available at https://plmlab.math.cnrs.fr/mposs/ddid/.

A further simplification when s = 1

All the numerical experiments reported in the following consider variants of the budget uncertainty set, so s = 1. It so happens that in this case, writing down the complementarity conditions between (16) and its dual, we are always able to construct an optimal solution where µ = 0. Proposition 5. When s = 1, there is an optimal solution (w * , u * , u 0 * , u 1 * , y * , y 0 * , y 1 * , µ * , σ * ) to the compact formulation (DDID-WIP) such that µ * = 0.

Proof. See Appendix D.

Selection problem

We first experiment the reformulation from Proposition 2 with the selection problem, where the decision maker wishes to choose p out of n items, so Y sel = y ∈ {0, 1} n i∈[n] y i = p . The selection problem has been used in numerous papers addressing complex robust variants [Goerigk andLendl, 2021, Goerigk et al., 2022a,b], including DDID itself under the name of two-stage robust best box selection [START_REF] Vayanos | Robust optimization with decision-dependent information discovery[END_REF], in which p = 1.

We use the budget uncertainty set of Bertsimas andSim [2003, 2004], defined as w ∈ {0, 1} n i∈[n] w i ≤ q , where one can investigate up to q items. We consider n ∈ {10, 20, 30, 40, 50}, p, q, Γ ∈ {n/10, n/5} and generate randomly 10 instances (meaning the generation of vectors c, d and f in [0, 1] n ) for each quadruplet of parameters. For each instance, we further consider a variant where only n/2 parameters are uncertain, the other being fixed to their nominal values.

Ξ Γ = ξ ∈ R n i∈[n] ξ i ≤ Γ, 0 ≤ ξ ≤ 1 ,
We first illustrate in Table 1 the distance between z DDID and the bounds z WS and z MM . These results illustrate that for our instances, the average gaps are often below 10%, and hardly higher than 20%. As expected, looking at column q wee see how investigating more parameters moves z DDID towards z WS . We also see that larger values of Γ leads to smaller gaps, often significantly.

Table 2 reports the solution times in seconds and root gaps in % for the two formulations presented in Section 4. We see immediately the importance of strengthening the formulation as described in (DDID-SIP). This reduces the root gaps to close to 0% on average, thereby reducing the solving times by more than one order of magnitude. Looking more precisely at Table 3: Average solution times in centiseconds (T) and root gaps in % (gap) for the K-adaptability reformulation presented in Section E.

We compared the above results with our own implementation of the K-adaptability reformulation proposed [START_REF] Vayanos | Robust optimization with decision-dependent information discovery[END_REF], see Section E for details of the resulting formulation. The solution times are presented in Table 3 for n ∈ {10, 15}; larger values of n are not presented as many instances could not be solved be solved in one hour for n = 20. These results illustrate that the reformulations for K-adaptability are several orders of magnitude slower than the exact reformulations proposed in this paper. The results of Table 3 might seem contradictory with the results presented in [Vayanos et al., 2022, Table 1], which report instances of up to 50 items being solved in a few seconds for K ∈ [10]. However, notice that [START_REF] Vayanos | Robust optimization with decision-dependent information discovery[END_REF] model uncertainty by projecting a 4-dimensional box into R n , specifically,

Ξ factor = ξ ∈ R n ∃ζ ∈ [-1, 1] L : ξ i = ψ i (ζ) ,
for given affine mappings ψ i , and L = 4 risk factors. As stated in Observation 4, (DDID) is then equivalent to (Wait&See) as soon as 4 items or more can be investigated, probably explaining the relative simplicity of the instances tested in [START_REF] Vayanos | Robust optimization with decision-dependent information discovery[END_REF]. In fact, a preliminary version of their work used instead L ∈ {20, 30} factors, reporting solution times more aligned with those presented in Table 3, see [Vayanos et al., 2020, Figure 3]. Another source of simplification in [START_REF] Vayanos | Robust optimization with decision-dependent information discovery[END_REF] is that they consider p = 1, while we consider larger values of this parameter here, which appears to have a significant impact on the solution times.

Orienteering problem

Our second set of experiments focuses on a particular routing problem considered by [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF]: the orienteering problem. That problem is most naturally stated as the maximization problem max

w∈W OP min ξ∈Ξ OP max y∈Y OP min ξ∈Ξ OP (w, ξ) i∈[n] (c i + ξ i )y i ,
which we specify next by defining Y OP , Ξ OP , and W OP . Consider a complete and undirected graph with n + 2 nodes, numbered from 0 to n + 1, where nodes 0 and n + 1 denote the start and destination nodes, respectively, so [n] indexes all nodes different from the depot. We denote by t ij the travel time of edge {i, j} and by T the maximum travel time. Any feasible element in Y OP is an elementary path from 0 to n + 1 having a total weight that does not exceed T . Introducing binary variable x e to model the use of edge e in the path, and denoting the star of node i as

E(i) = {e ∈ E | i ∈ e }, we formulate Y OP as Y OP =        y ∈ {0, 1} n : ∃z ∈ {0, 1} |E| s.t. t T z ≤ T, e∈E(0) z e = e∈E(n+1) z e = 1, e∈E(i) z e = 2y i , ∀i ∈ [n],
subtour elimination constraints

      
, where "subtour elimination constraints" denotes any set of constraints preventing cycles in y (e.g. [START_REF] Taccari | Integer programming formulations for the elementary shortest path problem[END_REF]). Polytope P OP is obtained from Y OP by removing the integrality restrictions on y and z and projecting the resulting polytope on variables y. Furthermore, we follow [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF], and define c = 0, W OP = w ∈ {0, 1} n i∈[n] w i ≤ q , and

Ξ OP =    ξ ∈ R n i∈[n] ξ i ≥ 1, 0 ≤ ξ i ≤ U, ∀i ∈ [n]    ,
for some given U > 0 and q = δn for some given δ ∈ (0, 1). In general conv(Y OP ) = P OP does not hold, so we cannot apply Proposition 2 to this problem. Therefore, we consider instead the convex hull formulation described in Section 5.1 and test the two approaches described in that section. First, we consider the exact algorithm, based on the full enumeration of the elements in Y OP . We consider the counterpart of Observation 6 for nonpositive costs, thus enumerating only the maximal paths in Y OP . However, Observation 7 could not be leveraged. Indeed, the maximization counterpart of ( 22

) becomes max ξ∈Ξ OP i∈[n] (c i + ξ i )ỹ s,i < max y∈Y OP min ξ∈Ξ OP i∈[n] (c i + ξ i )y s,i .
With the above definitions of c and Ξ OP , the condition becomes min(1, U |ỹ s |) < max 0, 1 -U (n -max y∈Y OP |y|) , which is never satisfied for the values of n and U provided in Table 6, even when |ỹ s | = 1 and max y∈Y OP |y| = 1. Second, we consider the heuristic based on the column-generation at the root node. The "subtour elimination constraints" used in our experiments are the classical Dantzig-Fulkerson-Johnson subtour elimination constraints, separated exactly at the integer node of the branch-and-cut-tree, together with the generalized cutset inequalities, separated heuristically at fractional nodes using Tarjan's algorithm as detailed in [START_REF] Taccari | Integer programming formulations for the elementary shortest path problem[END_REF]. We test the algorithms on a subset of the instances from [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF], consisting of complete graphs with 10 to 31 nodes (excluding the depots), and further described in the appendix.

The results are presented in Table 4. Columns CB, conv and CG respectively denote the combinatorial Benders algorithm from [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF], the exact convexification and the columngeneration algorithm from Section 5.1. The columns "Time" report average solution times over the subset of instances solved by all methods, which may be empty, leading to the entry "-". The additional column "Time (all)" reports the average solution times on all instances. The reported times are rounded to the second apart from the smallest instances for which we keep one more digit. The columns "gap" report the cost difference between Φ(w) for the solution w returned by CG and (i) the best solution returned by CB, and (ii) the best known solution. In particular, the larger gaps values in the second "gap" column reveal that conv may find better solutions than CB. Notice that the results reported for CB have been carried out using a different configuration (processor, CPLEX, parallelism), so the comparison between the respective columns should be made with care.

Overall, our results indicate that conv, despite its exhaustive enumeration, is somewhat competitive, solving nearly as many instances as CB, some of them faster (e.g. TS2N19). More importantly, its heuristic variant CG scales well with the dimensions of the instances, solving them in a few minutes for the largest. always optimal, often beating the best solutions returned by CB for the most difficult instances (corresponding to the negative gaps). We report additional statistics on algorithms conv and CG in Appendix F, including the excellent root gap of the MILP reformulation.

Minimum spanning tree

Our last benchmark focuses on the DDID counterpart of the minimum spanning tree problem (MST), on which we illustrate and compare the three solution methods presented in Sections 4 and 5. As a first approach we solve the compact MILP given by (DDID-SIP) for the directed multicommodity flow formulation of the MST, see [START_REF] Magnanti | Optimal trees[END_REF], denoted compact. This formulation is compact and known to be exact, so Proposition 3 applies. The second approach, CG, relies on the column generation heuristic, already illustrated for the orienteering problem. Each column added corresponds to an optimal tree returned by the Kruskal algorithm. The third approach, CP, is a cutting plane algorithm following the scheme described in Section 5.2. We consider the subtour formulation of the MST, see [START_REF] Magnanti | Optimal trees[END_REF]. For a given solution θ * of the current relaxation, we separate constraints of the subtour formulation by following the algorithm described by [START_REF] Magnanti | Optimal trees[END_REF]. Given that the multi-commodity flow formulation is exact, for each u * α > 0 the maximum flow from one arbitrary root to any other vertex must be equal to u * α if y * l ∈ conv(Y). Otherwise, the minimum cut provides a subtour constraint to be added to the relaxed formulation. To speed-up the cutting plane generation, the initial relaxation of CP includes one set of aggregated multicommodity flow constraints (instead of one set of constraints for each α ∈ A in compact).

The three methods are compared on a benchmark similar to that used by [START_REF] Focke | Minimum spanning tree under explorable uncertainty in theory and experiments[END_REF]. Each instance corresponds to an instance of the TSPLib, where each vertex has a given position and the nominal costs of the edges are given by the distances separating their two endpoints. The deviation are then set as 50% of the nominal values. We limit the density of the graphs by considering only the 6 closest neighbors of each vertex. Table 5 presents solution times and statistics for the three algorithms. In the last two "gap" columns, "root" shows the relative difference between the optimal value found by CP or compact and that of the linear relaxation of compact and "CG" shows the relative difference between the best value obtained by CG and the optimal value found by CP or compact. The results indicate that compact could not solve the three largest instances because of memory issues. In addition to the good root gaps and the good optimality gaps of CG, the table illustrates the solving capability of CP, which is able to solve exactly larger instances than compact. The good performance of CP is partly due to the strong initial relaxation since few subtour inequalities are generated, sometimes even 0.

Conclusion

Decision-Dependent Information Discovery is a recent approach to situations where the decision maker can investigate some of the parameters before taking her actual decision. While the applications for the model are countless, the resulting optimization problems have remained very difficult to solve, even for the budget uncertainty polytope.

We have provided in this paper new efficient solution algorithms for the problem assuming that only the costs are uncertain, and that they belong to a polytope defined by a small number of constraints other than individual bounds. We have proposed a compact MILP formulation for the DDID counterpart of a nominal optimization problem that has a compact linear description. We have illustrated the reformulation on the selection problem, solving exactly instances with 50 items in one second on average, significantly improving over the literature. We have extended our reformulations to problems for which no compact linear formulation is available (such as N Phard problems) through column generation and row generation algorithms. Our experiments have again illustrated the interest of these algorithms. On the one hand, the heuristic based on column generation has provided good results on the orienteering instances considered by [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF], providing better primal bounds than previously known for some of them. On the other hand, the cutting plane algorithm has proved successful in solving exactly larger problem than possible with the compact reformulation alone.

In addition to these numerically-oriented results and formulations, we have also improved the theoretical understanding of DDID, showing that the problem is easy as soon as the nominal problem is polynomially solvable and the number of possible investigations is polynomially bounded.

We have also clarified the link between DDID, the usual min-max counterpart, and the maxmin wait-and-see counterpart, showing how DDID falls down to the latter when the number of components being investigated is not smaller than than the dimension of the uncertainty set.

This work leads to several interesting open questions for future works. On the numerical side, the excellent dual bound provided by the column generation algorithm calls for extending the latter into an exact branch-and-price algorithm, hopefully leading to an efficient way to solve exactly DDID even when the nominal problem is N P-hard. On the theoretical side, DDID inherits the N P-hardness of the min-max problem for arbitrary uncertainty sets. However, its complexity is still unknown for a constant number of constraints, even in situations as simple as the selection problem with budget uncertainty.

Dualizing the linear program yields (with the primal variables indicated into brackets)

min α∈A     r T α + i∈W 0 d i   - k∈[s] a ki α k   +   u α + i∈W 1 c i y α,i + i∈W 0 (c i + β α,i )y α,i   + d T σ + r T µ s.t. α∈A u α = 1 [ω] k∈[s] a ki µ k + σ i ≥ - k∈[s] α∈A a ki α k u α + α∈A y α,i , ∀i ∈ W 1 [ ξi ] k∈[s] a ki µ k + σ i ≥ 0, ∀i ∈ W 0 [ ξi ] By α ≥ u α b, ∀α ∈ A [λ α ] y α,i ≤ u α , ∀α ∈ A, i ∈ [n] [π α ]
u, y, µ, σ ≥ 0.

Notice that the constraints corresponding to ξi for i ∈ W 0 are redundant and can be relaxed. Then, we introduce variables w ∈ W to represent W 1 and W 0 , so the above problem is rewritten as

min α∈A   r T α u α + i∈[n] (1 -w i )d i   - k∈[s] a ki α k   + u α + i∈[n] c i y α,i + i∈[n] β α,i y α,i (1 -w i )   + d T σ + r T µ (30) s.t. α∈A u α = 1 (31) k∈[s] a ki µ k + σ i ≥ w i   - k∈[s] α∈A a ki α k u α + α∈A y α,i   , ∀i ∈ [n] ( 32
)
By α ≥ u α b, ∀α ∈ A (33) w ∈ W (34) u, y, µ, σ ≥ 0. ( 35
)
Next, we linearize the product by w i in (32) with a big-M term which yields:

k∈[s] a ki µ k + σ i ≥ - k∈[s] α∈A a ki α k u α + α∈A y α,i -M (1 -w i ), ∀i ∈ [n]. Given that y α,i ≤ u α , ∀i ∈ [n], we have α∈A y α,i ≤ α∈A u α = 1, ∀i ∈ [n].
As a consequence, M can be set to 1 + max α∈A -k∈[s] a ki α k . We conclude by introducing variables y 0 α,i and u 0 α,i to represent the products y α,i (1 -w i ) and u α (1 -w i ), respectively, and adding the linearization constraints y 0 α,i ≥ y α,i -w i and u 0 α,i ≥ u α -w i .

B.2 Proof of Proposition 3

We show that the model is a valid linearization of the intermediary model ( 30)-( 35) of the proof of Proposition 2, having removed variable µ in accordance with Proposition 5. For this, we introduce u 1 i,α := w i u α , u 0 i,α := (1 -w i )u α , y 1 i,α := w i y α,i , y 0 i,α := (1 -w i )y α,i . Variables u 1 and y 1 stand for the decisions whose cost coefficients have been investigated whereas u 0 and y 0 stand for the others. The definitions of u 1 and u 0 may then be enforced in the model by adding the constraints u α = u 0 α,i + u 1 α,i , u 0 α,i ≤ 1 -w i and u 1 α,i ≤ w i , for all α ∈ A and i ∈ [n]. Similar constraints could be added to linearize y 0 and y 1 , but we instead leverage constraints y α,i ≤ u α , α ∈ A, i ∈ [n], to add the tighter constraints y α,i = y 0 α,i + y 1 α,i , y 0 α,i ≤ u 0 α,i and y 1 α,i ≤ u 1 α,i for all α ∈ A and i ∈ [n]. The objective function (30) and constraints (32) are then naturally linearized using the definitions of y 0 , u 1 and y 1 . Finally, constraints Gu 1 α ≤ u α g are not necessary, but they are valid inequalities obtained by multiplying Gw ≤ g by u α for each α ∈ A.

B.3 Proof of Proposition 4

We consider a feasible solution to the linear relaxation of (DDID-SIP) given by vectors w, ū, ū0 , ū1 , ȳ, ȳ0 , ȳ1 , σ, μ and we consider its projection on the variables of (DDID-WIP), w, ū, ū0 , ȳ, ȳ0 , σ, μ. The satisfaction of most constraints is immediate, but some verifications need to be carried out for constraints y 0

α,i ≥ y α,i -w i , u 0 α,i ≥ u α -w i , and k∈[s] a ki µ k + σ i ≥ -k∈[s] α∈A a ki α k u α + α∈A y α,i -M i (1 -w i ).
For the first, we use that ȳ = ȳ0 + ȳ1 and ȳ1 ≤ ū1 to show that ȳ0 α,i ≥ ȳα,i -ū1 α,i ≥ ȳα,i -wi for all α ∈ A, i ∈ [n]. We show similarly for the the second that ū0 α,i ≥ ūα,i -ū1 α,i ≥ ūα,i -wi for all α ∈ A, i ∈ [n]. To show that the last constraints are satisfied, we infer the following sequence of inequalities from the linear constraints of (DDID-SIP).

-

k∈[s] α∈A a ki α k ūα + α∈A ȳα,i -M i (1 -wi ) = - k∈[s] α∈A a ki α k ū1 α,i + α∈A ȳ1 α,i - k∈[s] α∈A a ki α k ū0 α,i + α∈A ȳ0 α,i -   1 + max α∈A    - k∈[s] a ki α k      (1 -wi ) ≤ - k∈[s] α∈A a ki α k ū1 α,i + α∈A ȳ1 α,i - k∈[s] α∈A a ki α k ū0 α,i + α∈A ū0 α,i -   1 + max α∈A    - k∈[s] a ki α k      α∈A ū0 α,i ≤ - k∈[s] α∈A a ki α k ū1 α,i + α∈A ȳ1 α,i ≤ k∈[s] a ki µ k + σ i .
C. Proofs of Section 5.1

C.1 Proof of Observation 6

To prove inequality z DDID ≥ zDDID , let (u * , u 0 * , u 1 * , y 0 * , y 1 * , σ * , µ * , λ * ) be an optimal solution to (DDID-CG) associated to Y. We construct a solution (u * , u 0 * , u 1 * , y 0 * , y 1 , σ * , µ * , λ ) to the formulation associated to Ỹ by setting

λ s = λ * s for s ∈ [t] \ {s 1 , s 2 }, λ s 1 = λ * s 1 + λ * s 2 (notice variable λ s 2 does not exist in the new model) and y 1 α,i = s∈[t] λ α,s ỹs,i -y 0 * α,i , α ∈ A, i ∈ [n]. Observe that ỹs 1 ≤ ỹs 2 implies that s∈[t] λ α,s ỹs,i ≤ s∈[t] λ α,s ỹs,i and y 1 α,i ≤ y 1 * α,i for all α ∈ A, i ∈ [n].
A a consequence, one readily verifies that (u * , u 0 * , u 1 * , y 0 * , y 1 , σ * , µ * , λ ) is feasible and its cost is not larger than that of (u * , u 0 * , u 1 * , y 0 * , y 1 * , σ * , µ * , λ * ). The reverse inequality is even more direct, plugging the solution obtained for Ỹ into the formulation associated to Y.

C.2 Proof of Observation 7

Let (w * , ξ * , y * , ξ * ) be an optimal solution to (DDID). If y * = ỹs , the result is immediate. Otherwise, we detail next the resulting contradiction. Notice first that (22) implies max ξ∈Ξ i∈[n] (c i + ξ i )ỹ s,i > z MM , and therefore min y∈ Ỹ max ξ∈Ξ i∈[n] (c i + ξ i )y i = min y∈Y max ξ∈Ξ i∈[n] (c i + ξ i )y i . On the one hand, Ỹ ⊂ Y implies z DDID ≤ zDDID . On the other hand, we have that

z DDID = Φ(w * ) = i∈[n] (c i + ξ * i )ỹ s,i ≥ min ξ∈Ξ i∈[n] (c i + ξ i )ỹ s,i > min y∈Y max ξ∈Ξ i∈[n] (c i + ξ i )y i = min y∈ Ỹ max ξ∈Ξ i∈[n] (c i + ξ i )y i = min y∈ Ỹ max ξ∈Ξ max ξ∈Ξ(w * , ξ) i∈[n] (c i + ξ i )y i ≥ max ξ∈Ξ min y∈ Ỹ max ξ∈Ξ(w * , ξ) i∈[n] (c i + ξ i )y i ≥ min w∈W max ξ∈Ξ min y∈ Ỹ max ξ∈Ξ(w, ξ) i∈[n] (c i + ξ i )y i = zDDID ,
where the third inequality arises from (22).

D. Proof of Proposition 5

We consider in this proof the case s = 1. In that case, we see that we can assume a i > 0 for each i ∈ [n] otherwise ξ i = d i in any optimal solution to the adversarial problem. We obtain the uncertainty polytope

ξ ∈ R n a T ξ ≤ r, 0 ≤ ξ ≤ d ,
where r is now a scalar. In this case, we see that any A = 0∪{1/a i | i ∈ [n] }, so we use throughout the proof the notations α = 1/a for each ∈ [n], and for each i, ∈

[n], β ,i = d i [1 -a i /a ] + , while α 0 = 0 and β i,0 = d i , ∀i ∈ [n]. We further note |n] ∪ {0} as [n] 0 .
Referring to the counterparts of Theorem 2 and to the proof of Proposition 2 to the above setting, we will consider the pair of primal-dual adversary formulations given by

P(w)                                    max ω s.t. ω ≤   r - i∈W 1 a i ξi   α + b T λ - i∈[n] π ,i , ∀ ∈ [n] 0 [u ] (B •,i ) T λ -π ,i ≤ c i + ξi , ∀ ∈ [n] 0 , ∀i ∈ W 1 [y ,i ] (B •,i ) T λ -π ,i ≤ c i + β ,i , ∀ ∈ [n] 0 , ∀i ∈ W 0 [y ,i ] a T ξ ≤ r [µ] ξ ≤ d [σ] ξ ≥ 0, λ , π ≥ 0, ∀ ∈ [n] 0 , D(w) :                                      min ∈[n] 0   rα u + i∈[n] c i y ,i + i∈W 0 β ,i y ,i   + i∈[n] d i σ i + rµ s.t. ∈[n] 0 u = 1 [ω] a i µ + σ i ≥ -a i ∈[n] 0 α u + ∈[n] 0 y ,i , ∀i ∈ W 1 [ ξi ] By ≥ u b, ∀ ∈ [n] 0 [λ ] y ,i ≤ u , ∀ ∈ [n] 0 , i ∈ [n] [π ]
u, y, µ, σ ≥ 0.

, and let ( ξ * , λ * , π * ) and (u * , y * , µ * , σ * ) be a pair of optimal solutions to P(w) and D(w).

Assume now that µ * > 0. We show next that it means that for each

∈ [n] and i ∈ W 0 , β ,i y * ,i = 0. Let ∈ [n] such that u * > 0 and i ∈ W 0 such that y * ,i > 0. By complementarity, we have (B •,i ) T λ * -π * ,i = c i + β ,i . If β ,i > 0, (36)
we build a new solution of P(w * ), (ω * , ξ * , λ , π ), by slightly modifying λ * and π * . We set λ := λ * i and π := π * i while keeping the other components of π * and λ * unchanged. Observe that µ * > 0 implies par complementarity that i∈W 1 a i ξ * i = r, so the constraints dual to u can be simplified to

ω * ≤ b T λ * - i∈[n] π * ,i , ∀ ∈ [n] 0 . (37)
Observing further that (36) is equivalent to a > a i and using (37), one can verify that (ω * , ξ * , λ , π ) is feasible for P(w * ) and (B •,i ) T λ -π ,i < c i + β ,i . However, by complementarity, we also get (B •,i ) T λ -π ,i = c i + β ,i , a contradiction. Therefore, β ,i = 0 (and thus 1 -a i a + = 0) for all i ∈ W 0 and ∈ [n] 0 such that y * ,i > 0. Transposing the above reasoning to = 0, we have β 0,i > 0 so that y * 0,i = 0 for each i ∈ W 0 . Using the above, we get that the objective value of D(w * ) is given by

r   µ * + ∈[n] α u *   + i∈[n]   d i σ * i + c i ∈[n] y * ,i   . ( 38
)
The rest of the proof constructs an algorithm that iteratively modifies the dual solution without changing the variables σ * and the values of the sums µ * + ∈[n] α u * and ∈[n] y * ,i Thanks to (38), the algorithm does therefore not modify the cost of the solution.

The dual constraint of ξi , i ∈ W 1 may be rewritten as:

µ * ≥ 1 a i   -σ * i + ∈[n] y * ,i   - ∈[n]
α u * , which must be active for at least one element of W 1 , which we denote j. Recalling 1/a j = α j , this means in particular that

µ * ≤ α j ∈[n]
y * ,j -

∈[n] α u * ≤ ∈[n]
(α j -α ) u * .

As a consequence, there is ∈ [n] 0 such that u * > 0 and α < α j . Using the above, we build another optimal solution of D(w * ), (y , u , µ , σ * ), where µ = 0, by iteratively decreasing the values of nonzero variables u , and increasing the value of u j while keeping constant the value of µ * + ∈[n] α u * . The iterative construction is formalized in Algorithm 1. At each step, one index such that u * > 0 and α < α j is considered. The first computed value, δ, is the largest decrease of u k such that u k ≥ 0 and µ ≥ 0 at the end of the algorithm. The update of y k and y j then guarantee that y ≤ u , ∀ ∈ Applying [Vayanos et al., 2022, Corollary 1] to (K-ADAPT) together with the symmetry breaking constraints detailed in Section EC.3.1. of [START_REF] Vayanos | Robust optimization with decision-dependent information discovery[END_REF], leads to the formulation presented name U T TS1N15 0.10 {5, 10, . . . , 70} TS2N10 0.20 {15,20,23,25,27,30,32,35,38} TS3N16 0.10 {5,10,. . . ,80} TS1N30 0.05 {5,10,. . . ,85} TS2N19 0.15 {15,20,23,25,27,30,32,35,38,40,45} TS3N31 0.05 {15,20,. . . ,120} Table 6: Instances taken from [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF], N being equal to n.

below. For readability, we subdivide the dual variables β into β Γ , β ub (for the upper bounds on ξ) and β lb (for the lower bounds on ξ) and similarly for β k . We model the constraints γ k i = w i γ k i with indicator constraints to avoid the burden of computing tight big M . Furthermore, we define

Γ = Γ + i∈[n] c i /d i . min Γ   β Γ + k∈[K] β k,Γ   + i∈[n] (c i + d i )   β ub i + k∈[K] β k,ub i   - i∈[n] c i   β lb i + k∈[K] β k,lb i   s.t. i∈[n] w i = q i∈[n] y k i = p, ∀k ∈ [K] k∈[K] α k = 1 β k,Γ d i + β k,ub i -β k,lb i + γ k i = y k i , ∀i ∈ [n], k ∈ [K] β Γ d i + β ub i -β lb i = k∈[K] γ k i , ∀i ∈ [n] w i = 1 =⇒ γ k i = γ k i , ∀i ∈ [n], k ∈ [K] w i = 0 =⇒ γ k i = 0, ∀i ∈ [n], k ∈ [K] y k i ≤ y k i , y k i ≤ α k , y k i ≥ α k -1 + y k i ∀i ∈ [n], k ∈ [K] z k,k+1 i ≤ y k i + y k+1 i , z k,k+1 i ≤ 2 -y k i -y k+1 i ∀i ∈ [n], k ∈ [K -1] z k,k+1 i ≥ y k i -y k+1 i , z k,k+1 i ≥ y k+1 i -y k i ∀i ∈ [n], k ∈ [K -1] y k i ≥ y k+1 i - i-1 j=1 z k,k+1 j ∀i ∈ [n], k ∈ [K -1]
β ≥ 0, β k ≥ 0, α ≥ 0, y, z binary

F. Additional details for the orienteering problem

The details of the instances used in our experiments are displayed in Table 6. gap of the MILP reformulation, which decreases as the amount of possible observation increases. It also shows how small instances lead on average to sets Y of small cardinality, explaining the very quick solution times of conv for the small instances.

  ξ) i∈[n] (c i + ξ i )y i , (DDID)where c is a given cost vector and Ξ(w, ξ) = ξ ∈ Ξ w • ξ = w • ξ , where v•w = (v 1 w 1 , . . . , v n w n ) for any pair of vectors v, w ∈ R n . Observe that constraint w •ξ = w • ξguarantees that the observed cost values are not modified after setting the solution y to the combinatorial optimization problem. Remark 1. The lower bounds equal to 0 in the definition of Ξ is without loss of generality. If the polytope were instead defined by Ξ = {ξ ∈ R n | Aξ ≤ r, d ≤ ξ ≤ d }, we could change variables by setting ξ := ξ -d and obtain a new polytope Ξ that satisfies d = 0, together with a new cost vector c and a new rhs r .We define next the outermost objective function of (DDID)

Observation 6 .

 6 Suppose c + ξ ≥ 0 for each ξ ∈ Ξ and consider ỹs 1 , ỹs 2 ∈ Y such that ỹs 1 ≤ ỹs 2 and let Ỹ = Y \ {ỹ s 2 }. Let zDDID denote the optimal value of (DDID-CG) associated to Ỹ. We have z DDID = zDDID . Proof. See Appendix C.1. We can filter Y similarly by relying on bounds. Observation 7. Consider ỹs ∈ Y such that min ξ∈Ξ i∈[n]

δµ

  [n], By ≥ u b, ∀ ∈ [n], and∈[n] y = ∈[n] y * . Finally, the update of µ is such that µ + ∈[n] α u = µ * + ∈[n] α u * .It is then straightforward to verify that each step keeps (y , u , µ , σ * ) feasible and leaves its objective value unchanged. Moreover, we can verify that either µ = 0 at the end of an iteration or δ = u * k . At the end of the algorithm, we thus haveµ ≤ µ * -k∈K (α j -α k ) u * k ≤ ∈[n] (α j -α ) u * -∈[n]:a >a j (α j -α ) u * ≤ 0. initialization: y := y * , u := u * , µ := µ * , K = {k ∈ [n] | u * k > 0, α k < α j }. 1 for k ∈ K do 2 ← µ -δ (α j -α k ) 8 if µ = 0 then 9 break 10 return (y , u , µ )Algorithm 1: Construction of an solution optimal solution where µ = 0E. Compact reformulation for selection problem with K-adaptabilityThe K-adaptability approximation amounts to pre-select K recourse policies and choose the best of them upon realization of the uncertain parameters. Applied to (DDID), one obtainsz ξ) i∈[n] (c i + ξ i )y i . (K-ADAPT)Consider the sets Y sel , W sel and the budget uncertainty

ξ

  i -c i d i ≤ Γ, ξ ≤ c + d, -ξ ≤ -c    .

Table 1 :

 1 largely used in the scientific literature on robust combinatorial optimization. We further consider the selection set for information discovery, W sel = Average relative gaps in %. Left and right values are 100 × z DDID -z WS

			uncertainty			p				q					Γ
	n	n/2		n		n/10		n/5		n/10		n/5			n/10		n/5
		WS MM WS MM WS MM WS MM WS MM WS MM WS MM WS MM
	10	8	11		7	12	7	11	9	13	9	10	7	13		9	19	7	4
	20	8	10		7	13	7	11	8	12	10	9	5	15		8	19	7	4
	30	11	7		8	10	8	8	10	9	11	6	8	11	11	14	8	3
	40	8	6		7	8	5	5	10	9	9	6	6	9	10	11	5	3
	50	8	7		7	9	6	6	9	10	9	6	6	10	10	13	6	3
	100 × z MM -z DDID z DDID	(denoted MM), respectively.				z DDID	(denoted WS) and
			uncertainty			p			q					Γ
		n	n/2		n		n/10		n/5		n/10	n/5		n/10	n/5
			T gap	T gap	T gap	T gap		T gap	T gap	T gap	T gap
		10	5 28	5 36	5 39	5 26		5 33	5 32	5 28	5 37
		20 12 45	13 61	10 60	15 45		12 54	13 52 12 50	13 55
		30 26 37	69 56	39 54	57 39		32 47	64 46 35 43	60 50
		40 66 39 280 48	92 48 260 39 130 44 220 43 75 40 270 47
		50 430 47 6200 58 1300 59 5300 47 1400 53 5300 52 680 50 5900 55
							(a) Weak formulation (DDID-WIP)
			uncertainty		p			q				Γ
		n	n/2	n	n/10		n/5	n/10	n/5	n/10		n/5
			T gap T gap T gap T gap	T gap T gap	T gap T gap
		10 5 0.01	6 0.14 5 0.00	6 0.15		5 0.00	6 0.15	5 0.09	6 0.06
		20 6 0.26 10 0.26 8 0.29	9 0.24		8 0.39	8 0.14	9 0.48	8 0.05
		30 16 0.08 26 0.39 18 0.16 24 0.30 18 0.16 24 0.30 22 0.35 20 0.11
		40 31 0.06 49 0.16 27 0.11 53 0.11 37 0.14 44 0.09 41 0.19 39 0.04
		50 75 0.14 160 0.22 79 0.14 150 0.22 100 0.21 130 0.15 110 0.25 120 0.11
							(b) Strong formulation (DDID-SIP)

Table 2 :

 2 Average solution times in centiseconds (T) and root gaps in % (gap).

  Table2b, we see that only p and the proportion of uncertain items have a significant impact on the solution times. Unreported results show that (DDID-SIP) scales well for larger instances, solving problems with up to 200 items in a couple of minutes.

			uncertainty			p				q			Γ
	n K	n/2		n		n/10		n/5		n/10		n/5		n/10		n/5
			T gap	T gap	T gap	T gap	T gap	T gap	T gap	T gap
	10	2 3	5 21	9 10	7 24	10 11	5 11	8 9	11 173	8 9	6 25	9 9 1694 26	8 10	6 18	15 16 1402 24	7 8
	15	2 3	40 2557	6 8 3275 46	7 9 173 11	8 9 5520 72	8 9 1694 26	8 10 2463 40	7 9 1402 24	7 8 3056 44	3 5

Table 4 :

 4 The results also indicate that the best solution returned by CG is almost Numerical results on the orienteering problem. Italicized results have been provided byParadiso [2023] and have been run on a configuration different than ours. Entries "-" indicate no subset of instances solved by all methods.

	instance	δ	Opt (#)	time (s) (solved) time (s) (all)	gap (%) w.r.to
			CB	conv	CB conv CG	CG CB max(CB, conv)
		0.25	9/9	9/9	5.4	0.1 0.4	0.4 0.0	0.0
	TS2N10	0.5	9/9	9/9	3.5	0.1 0.6	0.6 0.0	0.0
		0.75	9/9	9/9	2.3	0.1 0.7	0.7 0.0	0.0
		0.25 14/14 14/14	122	72	1	1 0.0	0.0
	TS1N15	0.5	14/14 14/14	69	71	2	2 0.2	0.2
		0.75 14/14 14/14	13	70	3	3 0.0	0.0
		0.25 14/14 13/14	66	463	2	2 0.0	0.0
	TS3N16	0.5	14/14 13/14	94	464	6	6 0.2	0.2
		0.75 14/14 13/14	18	464	7	6 0.0	0.0
		0.25	6/11	7/11 2534	101	2	2 0.5	0.5
	TS2N19	0.5	8/11	7/11 3122	612 29	24 0.2	0.2
		0.75 11/11 7/11	602	718 33	30 0.0	0.0
		0.25	6/18	6/18	1	1	2	16 -4.1	-0.3
	TS1N30	0.5	6/18	6/18	1	1	2	81 -2.7	-1.1
		0.75 10/18 6/18	233	707 63	260 -0.3	-0.3
		0.25	6/20	4/20	-	-	-	42 -5.4	-0.8
	TS3N31	0.5	6/20	4/20	-	-	-	225 -3.3	-0.6
		0.75	8/20	4/20 2994	4 65	409 -0.6	-0.3

Table 5 :

 5 Results for the MST presenting solution times, numbers of cuts and columns generated, root gaps and optimality gaps for CG.

	name	nodes edges Γ	q	time (s)		cols cuts	gap (%)
						compact	CG	CP	CG	CP root	CG
	burma14.tsp	14	51	3	3	19	3	4	42 104 0.11 1.70
	ulysses22.tsp	22	85	4	4	148	16	25 114 430 0.00 6.60
	bays29.tsp	29	105	6	6	-	34	200	53 636 0.15 0.49
	swiss42.tsp	42	159	8	8	-118	102 249	0 0.20 2.40
	eil51.tsp	51	186	10 10	-906 3478 572 561 0.21 0.95

Table 7 ,

 7 displaying the root gap of CG, the number of paths generated by both algorithms and the average fraction of time spent generating these paths. The table illustrates again the excellent root

	instance	δ	root gap	|Y OP |		% time generating Y OP
				conv	CG conv	CG
		0.25	2.2	12	7	36	3.3
	TS2N10	0.5	1.8	12	9	35	2.5
		0.75	0.0	12	10	38	1.6
		0.25	1.4	80	9	12	5.6
	TS1N15	0.5	0.7	80	15	16	6.2
		0.75	0.0	80	24	16	5.7
		0.25	4.0	121*	19	15*	1.2
	TS3N16	0.5	1.0	121*	33	20*	1.0
		0.75	0.1	121*	34	16*	0.6
		0.25	2.6	898*	13	1*	1.5
	TS2N19	0.5	2.6	898*	49	2*	0.2
		0.75	0.1	898*	55	2*	0.2
		0.25	0.5 2132*	36	29*	1.0
	TS1N30	0.5	0.6 2132*	86	35*	0.7
		0.75	0.1 2132* 190	26*	0.6
		0.25	1.7 3088*	66	4*	0.2
	TS3N31	0.5	0.6 3088* 154	5*	0.2
		0.75	0.0 3088* 237	7*	0.1

Table 7 :

 7 Additional average statistics on conv and CG on solved instances, mark "*" indicates there are unsolved instances in the group.

Acknowledgment

The authors thank Rosario Paradiso for sharing his detailed computational results. They also thank Boris Detienne for useful suggestions regarding the efficient application of Observation 6 with BitArrrays.

A. Comparison with the algorithm of [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF] First, the dualized formulation ( 12)-( 14) requires only constraint generation, while the approach from [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF]

where ξ(y) plays the role of adjustable variables depending on y. Hence, [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF] generate constraints ( 27) and ( 28) as well as variables ξ(y) in the course of their algorithm. Second, we leverage Corollary 2 to reduce the separation to solving O(n s ) nominal problems, while [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF] address the problem though MILP formulations. These two differences have a theoretical impact, since the running time of the algorithm from [START_REF] Paradiso | Exact and approximate schemes for robust optimization problems with decision dependent information discovery[END_REF] cannot be polynomially bounded in general under the assumptions of Proposition 1. From the numerical viewpoint, the supremacy of one algorithm over the other will depend on the sets Y and Ξ.

B. Proofs of Section 4 B.1 Proof of Proposition 2

Consider the linear program introduced in Theorem 2, and let us introduce dual variables u α and y α,i for the first three groups of constraints, together with µ and σ i for the constraints defining Ξ.