# The robust selection problem with information discovery

Xiaoyu Chen, Marc Goerigk, Michael Poss

► To cite this version:

Xiaoyu Chen, Marc Goerigk, Michael Poss. The robust selection problem with information discovery. Discrete Applied Mathematics, 2026, 382, pp.277-292. hal-05414100

HAL Id: hal-05414100

https://hal.science/hal-05414100v1

Submitted on 12 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# The robust selection problem with information discovery

Xiaoyu Chen*¹, Marc Goerigk², and Michael Poss¹

¹LIRMM, University of Montpellier, CNRS, Montpellier, France

²Business Decisions and Data Science, University of Passau, Germany

## Abstract

We explore a multiple-stage variant of the min-max robust selection problem with budgeted uncertainty that includes queries. First, one queries a subset of items and gets the exact values of their uncertain parameters. Given this information, one can then choose the set of items to be selected, still facing uncertainty on the unobserved parameters. In this paper, we study two specific variants of this problem. The first variant considers objective uncertainty and focuses on selecting a single item. The second variant considers constraint uncertainty instead, which means that some selected items may fail. We show that both problems are NP-hard in general. We also propose polynomial-time algorithms for special cases where the sets of items that can be simultaneously queried are defined by a cardinality or a knapsack constraint. For the problem with constraint uncertainty, we also show how the objective function can be expressed as a linear program, leading to a mixed-integer linear programming reformulation for the general case. We illustrate the performance of this formulation using numerical experiments.

**Keywords:** selection, robust optimization, decision-dependent uncertainty, combinatorial optimization, NP-hardness

## 1 Introduction

Robust optimization is an increasingly popular approach to handle the uncertainty that arises in mixed-integer linear optimization problems. Leading to compact reformulations and requiring only to describe the uncertain parameters by their possible realizations, robust optimization is easy to apply and to manipulate. Among the different uncertainty sets that have been proposed in the literature, budgeted uncertainty is particularly convenient for combinatorial problems as it essentially preserves the complexity of the nominal problem when the number of robust constraints is constant [4, 2]. The model considers that each uncertain cost (resp. weight) has a nominal cost $\bar{c}_j$ (resp. nominal weight $\bar{a}_{ij}$) and a possible deviation $\hat{c}_j$ (resp. $\hat{a}_{ij}$) and that in any possible scenario, at most $\Gamma \in \mathbb{Z}$ uncertain parameters will take their high costs $\bar{c}_j + \hat{c}_j$ (resp. high weight $\bar{a}_{ij} + \hat{a}_{ij}$), the other ones taking instead the low value $\bar{c}_j$ (resp. $\bar{a}_{ij}$). This uncertainty model is motivated by the observation that it is *unlikely* that all components of the cost or weight vector simultaneously take their worst-case, which can be formalized with the probabilistic bounds discussed in [5, 26]. Let $[n] = \{1, \dots, n\}$ and define

$$ \Delta^{\Gamma} = \left\{ \delta \in \{0, 1\}^n \mid \sum_{i \in [n]} \delta_i \leq \Gamma \right\}. $$

<footnote>*Corresponding author. Email: xiaoyu.chen@lirmm.fr</footnote>
Then, a general robust combinatorial optimization problem with $n$ variables and $m$ robust constraints can be defined as

$$ \min_{\mathbf{x} \in \mathcal{X}} \left\{ \max_{\boldsymbol{\delta} \in \Delta^{\Gamma}} \sum_{j \in [n]} (\bar{c}_j + \delta_j \hat{c}_j) x_j \left| \sum_{j \in [n]} (\bar{a}_{ij} + \delta_j \hat{a}_{ij}) x_j \le b_i, \forall i \in [m], \forall \boldsymbol{\delta} \in \Delta^{\Gamma} \right\}, \quad (\text{RCO}) $$

where $\mathcal{X} \subseteq \{0, 1\}^n$ is the feasibility set of the deterministic problem. Observe that different values of $\Gamma$ could be used in the different uncertainty sets appearing in the objective and each of the constraints. In addition to its theoretical tractability, and its probabilistic bounds, strong formulations [8] and ad-hoc branch-and-bound algorithms [7] have recently been proposed, leading to efficient algorithms for solving problem (RCO).

This optimistic outlook has made it possible to consider more complex robust problems than before. Among these richer models, some now consider the endogenous nature of the uncertain parameters, meaning that the value taken by the uncertain parameters depend on the decision that has been taken. Decision-dependent uncertainty arises in a wide variety of settings, in particular when some investment can be made to reduce the size of the uncertainty set [3, 23]. Herein we are interested in the problem where some binary measurements (or queries) model the investments that can be made on the uncertain parameters, leading to the following problem with four levels of decisions: (i) the set of queried parameters $I$ is selected, (ii) the adversary selects the worst-case values of the queried parameters with vector $\gamma$, (iii) the actual solution $\mathbf{x} \in \mathcal{X}$ is selected, and (iv) the adversary chooses the value for the remaining uncertain parameters in $\Delta^{\Gamma}(I, \gamma) = \{\boldsymbol{\delta} \in \Delta^{\Gamma} | \delta_i = \gamma_i, \forall i \in I\}$, which enforces the coherence between the uncertain vector $\boldsymbol{\delta} \in \Delta^{\Gamma}(I, \gamma)$ and the initial observations $\gamma \in \Delta^{\Gamma}$. The complete decision-dependent information discovery (DDID) problem can thus be stated as follows:

$$ \min_{I \in \mathcal{I}} \max_{\gamma \in \Delta^{\Gamma}} \min_{\mathbf{x} \in \mathcal{X}} \left\{ \max_{\boldsymbol{\delta} \in \Delta^{\Gamma}(I, \gamma)} \sum_{j \in [n]} (\bar{c}_j + \delta_j \hat{c}_j) x_j \left| \sum_{j \in [n]} (\bar{a}_{ij} + \delta_j \hat{a}_{ij}) x_j \le b_i, \forall i \in [m], \forall \boldsymbol{\delta} \in \Delta^{\Gamma}(I, \gamma) \right\}, \quad (\text{DDID}) $$

where $\mathcal{I} \subseteq 2^{[n]}$ contains the sets of items that can be queried simultaneously. Observe that the values of $\gamma$ chosen for $j \in [n] \setminus I$ in the outermost maximization are irrelevant since these can be freely modified when choosing the vectors $\boldsymbol{\delta} \in \Delta^{\Gamma}(I, \gamma)$.

Model (DDID) has many applications in urban planning, project management, resource allocation, and scheduling, among many others. Early papers involving DDID, for instance, considered applications in production planning [18]. The more recent paper [29] details applications in a R&D project portfolio optimization problem, where a company must choose how to prioritize the projects in its pipeline [27, 10]. That paper also describes a preference elicitation with real-valued recommendations where one can investigate how much users like any particular item. The paper further applies the latter model to improve the US kidney allocation system. Even more recently, Paradiso et al. [25] consider combining a routing problem with sensor location, which is motivated by the problem of collecting medicine crates at the Alrijne hospital.

Despite the many applications of (DDID), solution methodology for the problem has stayed behind. To the best of our knowledge, the only general approach to (DDID) is that of [29], who proposed a heuristic reformulation based on the application of the $K$-adaptability paradigm [17]. Unfortunately, the resulting MILP reformulations are large and heavily rely on big-$M$ coefficients, therefore limiting their use to rather small instances. The problem appears to be easier to solve when there are no robust constraints ($m = 0$), and [25] and [24] proposed exact algorithms in this case. On the one hand, [25] proposed an exact combinatorial Benders decomposition algorithm which can reasonably well solve (DDID), making no particular assumption about $\mathcal{X}$. On the other hand, [24]
leverages the explicit description of conv($\mathcal{X}$) to propose strong MILP reformulations, possibly coupled with a branch-and-price algorithm in the case the description of conv($\mathcal{X}$) is obtained through Dantzig-Wolfe decomposition.

Furthermore, very little is known about the theoretical complexity even for very simple cases of (DDID), which is the gap we intend to start filling in this work. Specifically, we consider two simple cases of (DDID) based on the selection problem, which is characterized by the feasibility set $\mathcal{X}^{SEL} = \{\mathbf{x} \in \{0, 1\}^n \mid \sum_{i \in [n]} x_i = p\}$. Due to their simple structure, selection problems are frequently studied in robust combinatorial optimization, see, e.g., [11, 20, 9, 21]. We show under which conditions the resulting special cases (DDID) are polynomially solvable or NP-hard. First, let us recall that solving the (deterministic) selection problem for cost vector $\mathbf{c}$ is equivalent to optimizing $\mathbf{c}^T\mathbf{x}$ over $\mathcal{X}^{SEL}$, which can be done in $O(n)$ thanks to the following result, see also [15] for an overview.

**Theorem 1 ([6]).** The i-th smallest of n numbers can be computed in $O(n)$.

By determining the p-th smallest item with respect to $\mathbf{c}$, we can then construct an optimal solution to the selection problem in linear time.

The first of the two problems we study in this paper considers more specifically the 1-selection problem under *Objective Uncertainty* (thus assuming $m = 0$):

$$ \min_{I \in \mathcal{I}} \max_{\gamma \in \Delta^{\Gamma}} \min_{j \in [n]} \max_{\delta \in \Delta^{\Gamma}(I, \gamma)} \bar{c}_j + \delta_j \hat{c}_j, \quad (\text{OU}) $$

where the inner minimization over $j$ has replaced the minimum over $\mathbf{x} \in \mathcal{X}$ because a unique item is being chosen (i.e., $p = 1$). We mention that problem (OU) has been first introduced in [29] under the name of *preference elicitation*. This problem refers to developing a decision support system capable of generating recommendations to a user, by letting that person ask a limited number of questions from a potentially large set before making a recommendation [30]. In what follows, we denote the objective function of the first stage of the problem as

$$ \Psi(I) = \max_{\gamma \in \Delta^{\Gamma}} \min_{j \in [n]} \max_{\delta \in \Delta^{\Gamma}(I, \gamma)} \bar{c}_j + \delta_j \hat{c}_j. $$

The second problem we study considers a variant of the selection problem where some selected items can fail, and it is uncertain which ones will fail. We may query items beforehand to determine whether they will fail. We want to ensure that amongst the $p$ selected items, at most $b$ will fail. Protecting against failing items is an often-studied variant of robust combinatorial optimization, see, e.g., [1, 16]. We obtain the *Constraint Uncertainty* optimization problem from (DDID) by considering a single robust constraint with $\bar{a}_j = 0$ and $\hat{a}_j = 1$ and a known objective:

$$ \min_{I \in \mathcal{I}} \max_{\gamma \in \Delta^{\Gamma}} \min_{\mathbf{x} \in \mathcal{X}^{SEL}} \left\{ \sum_{i \in [n]} c_i x_i \mid \sum_{i \in [n]} \delta_i x_i \le b, \forall \delta \in \Delta^{\Gamma}(I, \gamma) \right\}. \quad (\text{CU}) $$

Observe that we allow an item to be packed, even if we know that it will fail. In what follows, we denote the objective function of this problem as

$$ \Phi(I) = \max_{\gamma \in \Delta^{\Gamma}} \min_{\mathbf{x} \in \mathcal{X}^{SEL}} \left\{ \sum_{i \in [n]} c_i x_i \mid \sum_{i \in [n]} \delta_i x_i \le b, \forall \delta \in \Delta^{\Gamma}(I, \gamma) \right\}. $$

While we use the terminology that items “fail” for simplicity, the meaning of the uncertain constraint will depend on the application that is modeled. For example, if we select a team of $p$
employees, the uncertain constraint means that at most *b* should have some specific property; if we select a basket of *p* options within a recommender system, at most *b* should be of a specific category; or if we select *p* assets for a project portfolio, at most *b* should invoke a specific resource. More generally, problems of type (CU) model cardinality-constrained problems (see [28]), where it is uncertain if an item contributes to the cardinality constraint.

We consider three types of query sets. First we consider the set that allows to query any set of *q* items

$$ \mathcal{I}^{SEL} = \{I \subseteq [n] \mid |I| \le q\}. $$

Second, we consider a generalization of that set, the knapsack set defined by a given vector of weights **d** and a capacity *C*,

$$ \mathcal{I}^{KP} = \left\{ I \subseteq [n] \mid \sum_{i \in I} d_i \le C \right\}. $$

Last, we consider a generalization of the knapsack set, assuming that the set of queried items is characterized by *L* linear constraints

$$ \mathcal{I}^{GEN} = \{I \subseteq [n] \mid \sigma_{\ell}(I) \le 0, \forall \ell \in [L]\}, $$

where $\sigma_{\ell}(I) = \sum_{i \in I} \sigma_{\ell i} - \sigma_{\ell 0}$.

**Contributions and structure of the paper** We first consider in Section 2 the case of 1-selection problem under objective uncertainty (OU). We provide analytical solutions for $\Phi(I)$, and prove the problem to be NP-hard for the general set $\mathcal{I}^{GEN}$. We next focus on the set $\mathcal{I}^{SEL}$ and show that optimizing $\Phi(I)$ over this set can be done in $O(n)$ by querying the *q* smallest items in terms of $\bar{c}$. We further extend our result to $\mathcal{I}^{KP}$ and obtain that, somewhat surprisingly, optimizing $\Phi(I)$ over $\mathcal{I}^{KP}$ can be done in $O(n \log n)$ by using a slightly more complicated algorithm.

Turning to the *p*-selection problem with constraint uncertainty (CU) in Section 3, we provide a condition on the problem input to ensure its feasibility. We then show that the problem is NP-hard already for $\mathcal{I}^{KP}$. Then, we focus on the case of $\mathcal{I}^{SEL}$ and show which items should always be selected in an optimal *I*, leading again to an algorithm in $O(n)$ thanks to Theorem 1. Last, we provide a linear programming reformulation for $\Phi(I)$. The formulation can be further leveraged to obtain a (compact) mixed-integer linear programming reformulation for the full problem with $\mathcal{I}^{GEN}$, proving that the problem belongs to NP in this general case. The construction of the linear programming reformulations combines the linear programming duality classically used in robust optimization with some new ad-hoc ingredients specific to (CU).

The paper is concluded in Section 4.

**Additional references** We mention that other models with queries have been considered in the literature, for instance under the name of explorable uncertainty, which is usually traced back to [19]. In that work, the author studies the problem of how many queries are necessary to find the optimal solution to the selection problem with cost uncertainty. Subsequent papers have later studied the minimal number of queries to guarantee optimality for other optimization problems, such as the shortest path problem [13], the knapsack problem [14], and the spanning tree problem [12, 22].

**Further notation** For any integer *n*, we denote by $[n]_0$ the set $\{0, 1, 2, \dots, n\}$. For a set $I \subseteq [n]$, we denote by $\bar{I} = [n] \setminus I$ all items not in *I*. Throughout, we also use the notation $\hat{\Gamma} = \sum_{i \in I} \gamma_i$ and $\bar{\Gamma} = \Gamma - \hat{\Gamma}$ to distinguish the budgets spent on the observed and unobserved items, respectively. Furthermore, we denote by $\mathcal{G}_I = [\min(|I|, \Gamma)]_0$ the set of values that $\hat{\Gamma}$ can take. We also introduce
the set $\Delta_{\Gamma} = \{\delta \in \{0, 1\}^n \mid \sum_{i \in [n]} \delta_i = \Gamma\}$ to represent the case where the budget constraint must be satisfied at equality. Last, as we focus on the selection feasibility set in what remains, we denote $\mathcal{X}^{SEL}$ shortly as $\mathcal{X}$. For clarity, we assume that all involved parameters are non-negative, namely $c, \bar{c}, \hat{c}, p, b, q, C$ and $\Gamma$.

# 2 Objective uncertainty

In this section, we discuss problem (OU). We provide elementary observations and derive a closed-form expression of the optimal objective value for a given query set $I$ in Section 2.1. We prove in Section 2.2 that the whole problem is NP-hard in general. In Section 2.3, we show that the special cases that use query sets $\mathcal{I}^{SEL}$ or $\mathcal{I}^{KP}$ can be solved in polynomial time.

## 2.1 Additional definitions and basic properties

To simplify expressions, for any $I \in \mathcal{I}$ and $\hat{\Gamma} \in \mathcal{G}_I$, we define the cost of query set $I$ using exactly $\hat{\Gamma}$ deviations on $I$ and $\bar{\Gamma} = \Gamma - \hat{\Gamma}$ deviations on $\bar{I}$ as

$$ \psi(I, \hat{\Gamma}) = \max_{\gamma \in \Delta_{\hat{\Gamma}}} \min_{j \in [n]} \max_{\delta \in \Delta_{\Gamma}(I, \gamma)} \bar{c}_j + \delta_j \hat{c}_j. $$

Observe that $\Psi(I) = \max_{\hat{\Gamma} \in \mathcal{G}_I} \psi(I, \hat{\Gamma})$. Throughout this section, we assume the following to ease the analysis of the algorithms.

**Assumption 1.** We assume that the items are sorted such that $\bar{c}$ is non-decreasing, and this order is maintained within the subsets $I$ and $\bar{I}$.

Observe that to ensure Assumption 1, a sorting step in $O(n \log n)$ is necessary. However, for algorithms that run in $O(n)$, we can justify that the assumption is for ease of presentation only. We next provide two simple observations that will be used frequently throughout.

**Observation 1.** The value $\min_{j \in [n]} \bar{c}_j + \hat{c}_j$ represents an upper bound of problem (OU).

*Proof.* $\min_{I \in \mathcal{I}} \max_{\gamma \in \Delta_{\Gamma}} \min_{j \in [n]} \max_{\delta \in \Delta_{\Gamma}(I, \gamma)} \bar{c}_j + \delta_j \hat{c}_j \le \min_{j \in [n]} \max_{\delta \in \Delta_{\Gamma}} \bar{c}_j + \delta_j \hat{c}_j \le \min_{j \in [n]} \bar{c}_j + \hat{c}_j$. $\square$

Therefore, solving the problem relies on identifying the items whose costs are guaranteed to remain nominal under the worse-case scenario, and comparing the cheapest among them with the upper bound given in Observation 1.

For any $\hat{\Gamma} \in \mathcal{G}_I$, let us introduce the notation $I_{\hat{\Gamma}} \subseteq I$ to denote the set of the first $\hat{\Gamma}$ elements of $I$. Given $\hat{\Gamma} \in \mathcal{G}_I$, let $\gamma^*$ be an optimal solution to the maximization problem defining $\psi(I, \hat{\Gamma})$. The following observation characterizes the structure of $\gamma^*$.

**Observation 2.** For any $I \in \mathcal{I}$ and any $\hat{\Gamma} \in \mathcal{G}_I$, there exists an optimal solution $\gamma^*$ to the maximization problem defining $\psi(I, \hat{\Gamma})$ such that $\gamma_j^* = 1$ for $j \in I_{\hat{\Gamma}}$.

*Proof.* Define any solution $\gamma'$ different from $\gamma^*$, i.e., $\exists j \in I_{\hat{\Gamma}}$ such that $\gamma'_j = 0$, and $\exists i \in I \setminus I_{\hat{\Gamma}}$ such that $\gamma'_i = 1$. Since $\min_{j \in I: \gamma'_j = 0} \bar{c}_j \le \min_{j \in I: \gamma'_j = 0} \bar{c}_j$, we have $\min_{j \in I} \bar{c}_j + \gamma'_j \hat{c}_j = \min \{\min_{j \in I} \bar{c}_j + \gamma'_j \hat{c}_j = \min \{\min_{j \in I} \bar{c}_j + \gamma'_j \hat{c}_j = 0\}$.
$\hat{c}_j, \min_{j \in I : \gamma'_j = 0} \bar{c}_j \} \le \min \{ \min_{j \in I} \bar{c}_j + \hat{c}_j, \min_{j \in I : \gamma_j^* = 0} \bar{c}_j \} = \min_{j \in I} \bar{c}_j + \gamma_j^* \hat{c}_j$. Thus,

$$
\begin{aligned}
\min_{j \in [n]} \max_{\delta \in \Delta_{\leq}^{\hat{\Gamma}}(I, \gamma')} \bar{c}_j + \delta_j \hat{c}_j &= \min \left\{ \min_{j \in I} \bar{c}_j + \gamma'_j \hat{c}_j, \min_{j \in \bar{I}} \max_{\delta \in \Delta_{\leq}^{\hat{\Gamma}}} \bar{c}_j + \delta_j \hat{c}_j \right\} \\
&\le \min \left\{ \min_{j \in I} \bar{c}_j + \gamma_j^* \hat{c}_j, \min_{j \in \bar{I}} \max_{\delta \in \Delta_{\leq}^{\hat{\Gamma}}} \bar{c}_j + \delta_j \hat{c}_j \right\} \\
&= \min_{j \in [n]} \max_{\delta \in \Delta_{\leq}^{\hat{\Gamma}}(I, \gamma^*)} \bar{c}_j + \delta_j \hat{c}_j.
\end{aligned}
$$

<figure><img src="image_2.png" /></figure>

Thanks to Observation 2, $\psi(I, \hat{\Gamma})$ can be reformulated as follows:

$$
\begin{aligned}
\psi(I, \hat{\Gamma}) &= \max_{\gamma \in \Delta_{\leq}^{\hat{\Gamma}}} \min_{j \in [n]} \max_{\delta \in \Delta_{\leq}^{\hat{\Gamma}}(I, \gamma)} \bar{c}_j + \delta_j \hat{c}_j \\
&= \min \left\{ \min_{j \in I_{\hat{\Gamma}}} \bar{c}_j + \hat{c}_j, \min_{j \in I \setminus I_{\hat{\Gamma}}} \bar{c}_j, \min_{j \in \bar{I}} \max_{\delta \in \Delta_{\leq}^{\hat{\Gamma}}(I, \gamma)} \bar{c}_j + \delta_j \hat{c}_j \right\} \\
&= \min \left\{ \min_{j \in [n]} \bar{c}_j + \hat{c}_j, \min_{j \in I \setminus I_{\hat{\Gamma}}} \bar{c}_j, \min_{j \in \bar{I}} \max_{\delta \in \Delta_{\leq}^{\hat{\Gamma}}(I, \gamma)} \bar{c}_j + \delta_j \hat{c}_j \right\} \\
&= \begin{cases}
\min \left\{ \min_{j \in [n]} \bar{c}_j + \hat{c}_j, \min_{j \in I \setminus I_{\hat{\Gamma}}} \bar{c}_j \right\} & \text{if } \hat{\Gamma} \ge 1 \text{ and } I \setminus I_{\hat{\Gamma}} \ne \emptyset \\
\min \left\{ \min_{j \in [n]} \bar{c}_j + \hat{c}_j, \min_{j \in (I \setminus I_{\hat{\Gamma}}) \cup \bar{I}} \bar{c}_j \right\} & \text{if } \hat{\Gamma} = 0 \text{ and } (I \setminus I_{\hat{\Gamma}}) \cup \bar{I} \ne \emptyset
\end{cases}
\end{aligned}
\tag{1}
$$

From this reformulation, we obtain the following two results.

**Lemma 1.** Let $I \in \mathcal{I}$ such that $|I| < \Gamma$, then $\Psi(I) = \min_{j \in [n]} \bar{c}_j + \hat{c}_j$.

$$
\textit{Proof.} \quad \Psi(I) = \max_{\hat{\Gamma} \in \mathcal{G}_I} \psi(I, \hat{\Gamma}) = \psi(I, |I|) = \min_{j \in [n]} \bar{c}_j + \hat{c}_j \quad \square
$$

**Proposition 1.** If $|I| \ge \Gamma$, then $\Psi(I) = \max \{\psi(I, \Gamma), \psi(I, \Gamma - 1)\}$.

*Proof.* First, if $\bar{\Gamma} \ge 1$, then since $|I| \ge \Gamma \ge \hat{\Gamma} + 1$, it follows that $I \setminus I_{\hat{\Gamma}} \ne \emptyset$. Moreover, we observe that, $\psi(I, \Gamma - 1) \ge \psi(I, \Gamma - 2) \ge \dots \ge \psi(I, 0)$, which allows us to eliminate suboptimal values of $\hat{\Gamma}$. Therefore, the worst-case value of $\hat{\Gamma}$ lies in $\{\Gamma, \Gamma - 1\}$, and hence

$$
\Psi(I) = \max\{\psi(I, \Gamma), \psi(I, \Gamma - 1)\}.
$$

<figure><img src="image_3.png" /></figure>

Note that, when $\Gamma = n$, the optimal value of Problem (OU) is $\min_{j \in [n]} \bar{c}_j + \hat{c}_j$. We thus only consider the case $\Gamma < n$. Based on Proposition 1, we obtain the following two lemmas.

**Lemma 2.** Let $I = \{j_1, j_2, \dots, j_{\Gamma}\} \in \mathcal{I}$, then

$$
\Psi(I) = \min \left\{ \min_{j \in [n]} \bar{c}_j + \hat{c}_j, \max \left\{ \min_{j \in \bar{I}} \bar{c}_j, \bar{c}_{j_\Gamma} \right\} \right\}.
$$
Proof.

$$
\begin{align*}
\Psi(I) &= \max\{\psi(I, \Gamma), \psi(I, \Gamma - 1)\} \tag{From Proposition 1} \\
&= \max \left\{ \min \left\{ \min_{j \in [n]} \bar{c}_j + \hat{c}_j, \min_{j \in \bar{I}} \bar{c}_j \right\}, \min \left\{ \min_{j \in [n]} \bar{c}_j + \hat{c}_j, \bar{c}_{j\Gamma} \right\} \right\} \tag{From (1)} \\
&= \min \left\{ \min_{j \in [n]} \bar{c}_j + \hat{c}_j, \max \left\{ \min_{j \in \bar{I}} \bar{c}_j, \bar{c}_{j\Gamma} \right\} \right\}.
\end{align*}
$$

<figure><img src="image_4.png" /></figure>

**Lemma 3.** Let $I = \{j_1, j_2, \dots, j_\Gamma, j_{\Gamma+1}, \dots, j_m\} \in \mathcal{I}$ with $\Gamma + 1 \le m \le n$, then

$$
\Psi(I) = \min \left\{ \min_{j \in [n]} \bar{c}_j + \hat{c}_j, \max \left\{ \min \left\{ \bar{c}_{j_{\Gamma+1}}, \min_{j \in \bar{I}} \bar{c}_j \right\}, \bar{c}_{j_{\Gamma}} \right\} \right\}.
$$

Proof.

$$
\begin{align*}
\Psi(I) &= \max\{\psi(I, \Gamma), \psi(I, \Gamma - 1)\} \tag{From Proposition 1} \\
&= \max \left\{ \min \left\{ \min_{j \in [n]} \bar{c}_j + \hat{c}_j, \min \left\{ c_{j_{\Gamma+1}}, \min_{j \in \bar{I}} \bar{c}_j \right\} \right\}, \min \left\{ \min_{j \in [n]} \bar{c}_j + \hat{c}_j, \bar{c}_{j_{\Gamma}} \right\} \right\} \tag{From (1)} \\
&= \min \left\{ \min_{j \in [n]} \bar{c}_j + \hat{c}_j, \max \left\{ \min \left\{ \bar{c}_{j_{\Gamma+1}}, \min_{j \in \bar{I}} \bar{c}_j \right\}, \bar{c}_{j_{\Gamma}} \right\} \right\}.
\end{align*}
$$

<figure><img src="image_5.png" /></figure>

Note that if $\bar{I}$ is empty, the term $\min_{j \in \bar{I}} \bar{c}_j$ disappears from the expressions above, which does not affect the validity of the results. Consequently, given a query set $I$, $\Psi(I)$ can be computed in polynomial time.

## 2.2 NP-hardness of the general case

We now show that Problem (OU) is computationally hard for $\mathcal{I}^{GEN}$.

**Proposition 2.** *Problem (OU) with $\mathcal{I}^{GEN}$ is NP-hard in the strong sense even when $L \le n^2$.*

*Proof.* Consider the independent set decision problem: Given a graph $G(V, E)$ and a positive integer $K \le |V|$, does $G$ contain an independent set of size $K$ or more, i.e., a subset $V' \subseteq V$ such that $|V'| \ge K$ and any two vertices in $V'$ are not adjacent? We construct an instance of problem (OU) with $\mathcal{I}^{GEN}$ by setting $n = |V|$, $\Gamma = K$, $\bar{c}_j = 0$ and $\hat{c}_j = 1$, $\forall j \in [n]$, and defining $\sigma_{\ell 0} = 1$ and $\sigma_{\ell k} = 1$ iff $k \in \ell$ for each $\ell \in E$. In particular, we see that $L \le |E| \le n^2$.

From Lemma 1, we know that, when $|I| < \Gamma$, the optimal objective value of this instance is 1. When $|I| \ge \Gamma$, after the discovery of information, there always exists at least one item $j$ with $\delta_j = 0$, either in set $I$, or in set $\bar{I}$, the optimal objective value is thus 0. Therefore, the independent set decision problem has a *yes* solution if and only if the optimal objective value of this instance is 0. $\square$

In the next sections, we discuss special cases for $\mathcal{I}$ that result in polynomially solvable cases. In particular, the fact that optimizing a linear function over $\mathcal{I}$ is a hard problem does not necessarily imply that problem (OU) is also hard, as the knapsack case demonstrates.
## 2.3 Polynomial-time algorithms for special cases

In this section, we provide polynomial algorithms for the two cases $\mathcal{I}^{SEL}$ (selection query sets) and $\mathcal{I}^{KP}$ (knapsack query sets) running in $O(n)$ and $O(n \log n)$, respectively.

### 2.3.1 Selection query sets

In this subsection, we present a polynomial solution for problem (OU) with $\mathcal{I}^{SEL} = \{I \subseteq [n] \mid |I| \le q\}$. Notice that while Assumption 1 is used to prove the correctness of the algorithm, the latter does actually not need to sort the items.

**Proposition 3.** If $\mathcal{I} = \mathcal{I}^{SEL}$ and $\Gamma \le q$, problem (OU) can be solved in $O(n)$ by querying in the optimal $I^*$ the $q$ items with smallest $\bar{c}$, leading to a solution cost of $\min\{\min_{j \in [\Gamma]} \bar{c}_j + \hat{c}_j, \bar{c}_{\Gamma+1}\}$.

*Proof.* To determine the value of $\Psi(I^*)$, we have

$$ 
\begin{aligned}
\Psi(I^*) &= \max_{\hat{\Gamma} \in [\Gamma]_0} \psi(I^*, \hat{\Gamma}) \\
&= \max \{\psi(I, \Gamma), \psi(I, \Gamma - 1)\} \qquad (\text{From Proposition 1}) \\
&= \min \left\{ \min_{j \in [\Gamma]} \bar{c}_j + \hat{c}_j, \bar{c}_{\Gamma+1} \right\}.
\end{aligned}
$$

Now, considering any solution $I \in \mathcal{I}$, we have

$$ 
\begin{aligned}
\Psi(I) &= \max_{\gamma \in \Delta^\Gamma} \min_{j \in [n]} \max_{\delta \in \Delta^\Gamma(I, \gamma)} \bar{c}_j + \delta_j \hat{c}_j \\
&\geq \max_{\gamma \in \Delta^\Gamma} \max_{\delta \in \Delta^\Gamma(I, \gamma)} \min_{j \in [n]} \bar{c}_j + \delta_j \hat{c}_j \\
&= \max_{\delta \in \Delta^\Gamma} \min_{j \in [n]} \bar{c}_j + \delta_j \hat{c}_j \\
&\geq \min_{j \in [n]} \bar{c}_j + \delta'_j \hat{c}_j
\end{aligned}
$$

where $\delta'_j = 1$, for each $j \in [\Gamma]$ and $\delta'_j = 0$, for each $j \in \{\Gamma + 1, \Gamma + 2, \dots, n\}$. Therefore, $\Psi(I) \ge \min\{\min_{j \in [\Gamma]} \bar{c}_j + \hat{c}_j, \bar{c}_{\Gamma+1}\} = \Psi(I^*)$. Finally, the complexity of the algorithm follows from Theorem 1. $\square$

If $\Gamma > q$, then we fall into the case described in Lemma 1.

### 2.3.2 Knapsack query sets

Let us recall that $\mathcal{I}^{KP} = \{I \subseteq [n] \mid \sum_{i \in I} d_i \le C\}$. In this subsection, we discuss how to construct an optimal solution $I^* \in \mathcal{I}^{KP}$ in polynomial time. We propose in lemmas 4 and 5 two rules for identifying dominant solutions, which are also valid for the general case. Finally, we present a pseudo-code for solving the whole problem with $\mathcal{I}^{KP}$ in $O(n \log n)$.

**Lemma 4.** Let $I = \{j_1, j_2, \dots, j_\Gamma\}$ and $I' = \{j'_1, j'_2, \dots, j'_\Gamma\}$ with $j'_\Gamma > j_\Gamma$. Then, $\Psi(I) \le \Psi(I')$.

*Proof.* Let us introduce the additional notation $\bar{I} = \{i_1, i_2, \dots, i_{n-\Gamma}\}$ and $\bar{I}' = \{i'_1, i'_2, \dots, i'_{n-\Gamma}\}$. Since $|I| = |I'| = \Gamma$, from Lemma 2, we know that $\Psi(I) = \min\{\min_{j \in [n]} \bar{c}_j + \hat{c}_j, \max\{\bar{c}_{i_1}, \bar{c}_{j_\Gamma}\}\}$ and $\Psi(I') = \min\{\min_{j \in [n]} \bar{c}_j + \hat{c}_j, \max\{\bar{c}'_{i_1}, \bar{c}'_{j_\Gamma}\}\}$. Furthermore, we have $j'_\Gamma > j_\Gamma \ge \Gamma$. Thus, $j'_\Gamma \ge \Gamma + 1$ and $i'_1 < j'_\Gamma$. Therefore, $\Psi(I') = \min\{\min_{j \in [n]} \bar{c}_j + \hat{c}_j, \bar{c}'_{j_\Gamma}\}$.

To compare $\Psi(I)$ and $\Psi(I')$, we discuss the following cases:

* If $i_1 > j_\Gamma$, then $\Psi(I) = \min\{\min_{j \in [n]} \bar{c}_j + \hat{c}_j, \bar{c}_{i_1}\}$. Since $i_1 = \Gamma + 1$ and $j'_\Gamma \ge \Gamma + 1$, we have $j'_\Gamma \ge i_1$. Thus $\Psi(I) \le \Psi(I')$.
• If $i_1 < j_\Gamma$, then $\Psi(I) = \min\{\min_{j \in [n]} \bar{c}_j + \hat{c}_j, \bar{c}_{j_\Gamma}\}$. Since $j'_\Gamma > j_\Gamma$, $\Psi(I) \le \Psi(I')$.

Overall, we have $\Psi(I) \le \Psi(I')$.

<figure><img src="image_6.png" /></figure>

**Lemma 5.** Let $I = \{j_1, j_2, \dots, j_\Gamma\}$ and $I' = I \cup \{j_{\Gamma+1}, j_{\Gamma+2}, \dots, j_m\}$ with $\Gamma + 1 \le m \le n$. Then, $\Psi(I) = \Psi(I')$.

*Proof.* Let us introduce the additional notation $\bar{I} = \{i_1, i_2, \dots, i_{n-\Gamma}\}$ and $\bar{I}' = \{i'_1, i'_2, \dots, i'_{n-m}\}$. Since $|I| = \Gamma$ and $|I'| > \Gamma$, from Lemma 2 we know that $\Psi(I) = \min\{\min_{j \in [n]} \bar{c}_j + \hat{c}_j, \max\{\bar{c}_{i_1}, \bar{c}_{j_\Gamma}\}\}$ while Lemma 3 yields $\Psi(I') = \min\{\min_{j \in [n]} \bar{c}_j + \hat{c}_j, \max\{\min\{\bar{c}_{j_{\Gamma+1}}, \bar{c}_{i'_1}\}, \bar{c}_{j_\Gamma}\}\}$.

To compare $\Psi(I)$ and $\Psi(I')$, we discuss the following cases:

• If $j_\Gamma < j_{\Gamma+1} = i_1 < i'_1$, then $j_\Gamma = \Gamma$, $j_{\Gamma+1} = i_1 = \Gamma+1$, $i'_1 \ge \Gamma+2$ and $\Psi(I) = \min\{\min_{j \in [n]} \bar{c}_j + \hat{c}_j, \bar{c}_{\Gamma+1}\} = \Psi(I')$.

• If $j_\Gamma < i_1 = i'_1 < j_{\Gamma+1}$, then $j_\Gamma = \Gamma$, $i_1 = i'_1 = \Gamma+1$, $j_{\Gamma+1} \ge \Gamma+2$ and $\Psi(I) = \min\{\min_{j \in [n]} \bar{c}_j + \hat{c}_j, \bar{c}_{\Gamma+1}\} = \Psi(I')$.

• If $i_1 = i'_1 < j_\Gamma < j_{\Gamma+1}$, then $\Psi(I) = \min\{\min_{j \in [n]} \bar{c}_j + \hat{c}_j, \bar{c}_{j_\Gamma}\} = \Psi(I')$.

Notice that, if $\bar{I}'$ is empty, then $|I'| = n$ and $I = \{1, 2, \dots, \Gamma\}$. In this case, we again have $\Psi(I) = \min\{\min_{j \in [n]} \bar{c}_j + \hat{c}_j, \bar{c}_{\Gamma+1}\} = \Psi(I')$. Overall, we conclude that $\Psi(I) = \Psi(I')$.

<figure><img src="image_7.png" /></figure>

Lemma 5 implies that, if we have a solution $I$ such that $|I| = \Gamma$, then it is meaningless to observe any additional items with $\bar{c}$ greater than or equal to $\max_{j \in I} \bar{c}_j$ (i.e., $c_{j_\Gamma}$). Furthermore, from Lemma 4, we know that, an optimal solution $I$ with $|I| = \Gamma$ seeks to minimize the value of $\max_{j \in I} \bar{c}_j$. However, such a solution must also satisfy $\sum_{i \in I} d_i \le C$, leading to solving

$$ \min_{I=\{j_1, \dots, j_\Gamma\} \subseteq [n]} \left\{ j_\Gamma \left| \sum_{i \in I} d_i \le C \right. \right\}. \quad (2) $$

If problem (2) is infeasible, then by Lemma 1, the optimal solution of problem (OU) selects an item $j^* \in \arg\min_{j \in [n]} \bar{c}_j + \hat{c}_j$. In other words, if no solution $I \in \mathcal{I}$ satisfies $|I| \ge \Gamma$, then we can simply select an item $j^* \in \arg\min_{j \in [n]} \bar{c}_j + \hat{c}_j$, making further information discovery unnecessary.

We propose a polynomial algorithm to solve problem (2). For each $j \in \{\Gamma, \Gamma+1, \dots, n\}$, the solution is constructed as $I(j) = \{j\} \cup D(j)$ where the set $D(j)$ contains $\Gamma-1$ items with the smallest $d$ values from the set of indices $[j-1]$. If this solution satisfies the constraint $\sum_{i \in I(j)} d_i \le C$, $I(j)$ is an optimal solution. If not, we increment $j$ by 1. If, until $j = n$, we have not found a solution $I \in \mathcal{I}^{KP}$ such that $|I| = \Gamma$, then problem (2) is infeasible. At each iteration, we can obtain the set $D(j)$ by re-sorting the items according to $d$. Thus, the whole problem can be solved in $O(n^2 \log n)$.

The previous algorithm can be improved by observing that $D(j)$ can be constructed based on $D(j-1)$ by finding the item $i^*$ in $\arg\min_{i \in [j] \setminus D(j-1)} d_i$ in $O(n)$. Based on this idea, we propose a more effective algorithm (see Algorithm 1). Specifically, we first place all items in a list $L$ in non-decreasing order of $\bar{c}$ and place the first $\Gamma$ items in the list $I$ as an initial solution. At each iteration, we add an additional item into $I$, in sequence according to the order. We next remove the item with the highest value of $d$ from $I$. Once the constraint $\sum_{i \in I} d_i \le C$ is satisfied, the algorithm returns the optimal objective value: $\min\{\min_{j \in [n]} \bar{c}_j + \hat{c}_j, \max\{\min_{j \in \bar{I}} \bar{c}_j, \max_{j \in I} \bar{c}_j\}\}$, as given in Lemma 2. If, by the end, we have not found a set $I$ containing $\Gamma$ items and satisfying the constraint, the algorithm returns the optimal objective value: $\min_{j \in [n]} \bar{c}_j + \hat{c}_j$, as given in Lemma 1. Hence, problem (OU) with $\mathcal{I} = \mathcal{I}^{KP}$ can be solved in $O(n^2)$, which can be reduced to $O(n \log n)$ using a binary heap.

We have thus proved the following result.
**Proposition 4.** If $\mathcal{I} = \mathcal{I}^{KP}$, problem (OU) can be solved in $O(n \log n)$ using Algorithm 1.

<table><caption>**Algorithm 1:** 1-Selection with DDID</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>$I \leftarrow \emptyset, \bar{I} \leftarrow \emptyset$;</td></tr><tr><td>2</td><td>Compute upper bound $\bar{z} = \min_{j \in [n]} \bar{c}_j + \hat{c}_j$;</td></tr><tr><td>3</td><td>Sort all items based on $\bar{c}$ non-decreasing in $L$;</td></tr><tr><td>4</td><td>Add the first $\Gamma$ items of $L$ to $I$;</td></tr><tr><td>5</td><td><b>if</b> $\sum_{i \in I} d_i \le C$ <b>then return</b> $\min\{\bar{z}, \bar{c}_{\Gamma+1}\}$;</td></tr><tr><td>6</td><td>$k \leftarrow \Gamma + 1$;</td></tr><tr><td>7</td><td><b>while</b> $k \le n$ <b>do</b></td></tr><tr><td>8</td><td>Add $k$-th item of $L$ to $I$;</td></tr><tr><td>9</td><td>Identify the item $j$ with the highest value of $d_j$ in $I$ (break ties by choosing the largest index), then remove it from $I$ and place it into $\bar{I}$;</td></tr><tr><td>10</td><td><b>if</b> $\sum_{i \in I} d_i \le C$ <b>then return</b> $\min\{\bar{z}, \max\{\min_{i \in \bar{I}} \bar{c}_i, \max_{j \in I} \bar{c}_j\}\}$;</td></tr><tr><td>11</td><td><b>else</b></td></tr><tr><td>12</td><td><b>if</b> $k < n$ <b>then</b> $k \leftarrow k + 1$;</td></tr><tr><td>13</td><td><b>else return</b> $\bar{z}$;</td></tr></tbody></table>

In Algorithm 1, before the loop begins, the upper bound $\bar{z}$ can be computed in $O(n)$, and sorting all items in non-decreasing order of $\bar{c}$ requires $O(n \log n)$ time. A binary heap ordered by non-increasing $d$-values is built in $O(n)$ time. Within the loop, each iteration involves maintaining the heap, which takes $O(\log n)$ time. Note that although the expressions $\min_{i \in \bar{I}} \bar{c}_i$ and $\max_{j \in I} \bar{c}_j$ appear inside the loop, they are evaluated at most once per execution of the algorithm. Overall, Algorithm 1 runs in $O(n \log n)$ time.

# 3 Constraint uncertainty

In this section, we study problem (CU). We derive basic properties in Section 3.1 and show that the general case is NP-hard in Section 3.2. In Section 3.3, we prove that the special case of $\mathcal{I}^{SEL}$ can be solved in polynomial time. Last, we propose a linear programming formulation for computing the cost of $I$, and dualize it to provide an MILP reformulation of the problem in Section 3.4.

## 3.1 Additional definitions and basic properties

Throughout the section, we assume the following without loss of generality.

**Assumption 2.** All items are sorted so that the costs $c$ are non-decreasing.

To simplify expressions, for any $I \in \mathcal{I}$ and $\hat{\Gamma} \in \mathcal{G}_I$, we define the cost of solution $I$ using exactly $\hat{\Gamma}$ deviations on $I$ and $\bar{\Gamma} = \Gamma - \hat{\Gamma}$ deviations on $\bar{I}$ as

$$ \phi(I, \hat{\Gamma}) = \max_{\gamma \in \Delta_{\hat{\Gamma}}} \min_{\mathbf{x} \in \mathcal{X}} \left\{ \sum_{i \in [n]} c_i x_i \left| \sum_{i \in [n]} \delta_i x_i \le b, \forall \mathbf{\delta} \in \Delta^{\Gamma}(I, \gamma) \right. \right\}. \quad (3) $$

Observe that $\Phi(I) = \max_{\hat{\Gamma} \in \mathcal{G}_I} \phi(I, \hat{\Gamma})$. We start this section by providing a reformulation for $\phi(I, \hat{\Gamma})$ that will be instrumental to derive the positive results in sections 3.3 and 3.4.

$$ \textbf{Proposition 5.} \quad \phi(I, \hat{\Gamma}) = \max_{\gamma \in \Delta_{\hat{\Gamma}}} \min_{\mathbf{x} \in \mathcal{X}} \left\{ \mathbf{c}^T \mathbf{x} \left| \sum_{i \in I} \gamma_i x_i + \min \left\{ \sum_{i \in \bar{I}} x_i, \Gamma - \sum_{i \in I} \gamma_i \right\} \le b \right. \right\} $$
Proof. The robust constraint of the minimization problem in (3) can be written as:

$$ \sum_{i \in I} \gamma_i x_i + \max_{\delta \in \{0,1\}^{|\bar{I}|}} \left\{ \sum_{i \in \bar{I}} \delta_i x_i \left| \sum_{i \in \bar{I}} \delta_i \le \Gamma - \sum_{i \in I} \gamma_i \right. \right\} \le b. \quad (4) $$

Observe that $\boldsymbol{x}$ and $\boldsymbol{\gamma}$ are fixed binary vectors when considering the inner maximization problem over binary decision variables $\boldsymbol{\delta}$. Thus, the maximization problem reduces to selecting up to $\Gamma - \sum_{i \in I} \gamma_i$ indices from $\bar{I}$ with $x_i = 1$, yielding

$$ \max_{\boldsymbol{\delta} \in \{0,1\}^{|\bar{I}|}} \left\{ \sum_{i \in \bar{I}} \delta_i x_i \left| \sum_{i \in \bar{I}} \delta_i \le \Gamma - \sum_{i \in I} \gamma_i \right. \right\} = \min \left\{ \sum_{i \in \bar{I}} x_i, \Gamma - \sum_{i \in I} \gamma_i \right\}. \quad (5) $$

The result follows by plugging the right-hand-side (5) into (4), and replacing the robust constraint in (3) by the obtained reformulation. □

Next, we consider an optimal solution $\boldsymbol{\gamma}^*$ to the maximization problem defining $\phi(I, \hat{\Gamma})$ and describe its structural property. We use again the notation $I_{\hat{\Gamma}} \subseteq I$ introduced in the previous section to denote the set of the first $\hat{\Gamma}$ elements of $I$, for any $\hat{\Gamma} \in \mathcal{G}_I$.

**Proposition 6.** For any $I \in \mathcal{I}$ and any $\hat{\Gamma} \in \mathcal{G}_I$, there exists an optimal solution $\boldsymbol{\gamma}^*$ to the maximization problem defining $\phi(I, \hat{\Gamma})$ such that $\gamma_i^* = 1$ for all $i \in I_{\hat{\Gamma}}$.

*Proof.* Suppose there exists a solution $\boldsymbol{\gamma}'$ such that $\gamma_i' = 1$ and $\gamma_j' = 0$, where $i \in I \setminus I_{\hat{\Gamma}}$ and $j \in I_{\hat{\Gamma}}$. We show that swapping the values of $\gamma_i'$ and $\gamma_j'$ yields a solution $\boldsymbol{\gamma}^*$ with a cost no less than that of the original one. Specifically, we set $\gamma_j^* = \gamma_i' = 1$, $\gamma_i^* = \gamma_j' = 0$ and $\gamma_k^* = \gamma_k'$, for all $k \in I \setminus \{i, j\}$. Let

$$ \boldsymbol{x}' \in \arg \min_{\boldsymbol{x} \in \mathcal{X}} \left\{ \sum_{k \in [n]} c_k x_k \left| \gamma_i' x_i + \gamma_j' x_j + \sum_{k \in I \setminus \{i, j\}} \gamma_k' x_k + \sum_{k \in \bar{I}} \delta_k x_k \le b, \forall \boldsymbol{\delta} \in \Delta_{\bar{I}}^{\hat{\Gamma}}(I, \boldsymbol{\gamma}) \right. \right\}, $$

and

$$ \boldsymbol{x}^* \in \arg \min_{\boldsymbol{x} \in \mathcal{X}} \left\{ \sum_{k \in [n]} c_k x_k \left| \gamma_i^* x_i + \gamma_j^* x_j + \sum_{k \in I \setminus \{i, j\}} \gamma_k^* x_k + \sum_{k \in \bar{I}} \delta_k x_k \le b, \forall \boldsymbol{\delta} \in \Delta_{\bar{I}}^{\hat{\Gamma}}(I, \boldsymbol{\gamma}) \right. \right\}. $$

We next prove that $\boldsymbol{c}^T \boldsymbol{x}^* \ge \boldsymbol{c}^T \boldsymbol{x}'$ by constructing a feasible solution $\hat{\boldsymbol{x}}'$ under $\boldsymbol{\gamma}'$ from the solution $\boldsymbol{x}^*$ such that $\boldsymbol{c}^T \boldsymbol{x}^* \ge \boldsymbol{c}^T \hat{\boldsymbol{x}}'$.

Consider the following cases:

* If $x_i^* = x_j^* = 0$, or $x_i^* = x_j^* = 1$, or $x_i^* = 0$ and $x_j^* = 1$, we can simply set $\hat{\boldsymbol{x}}' = \boldsymbol{x}^*$, which remains feasible under $\boldsymbol{\gamma}'$.

* If $x_i^* = 1$ and $x_j^* = 0$, we define $\hat{\boldsymbol{x}}'$ by setting $\hat{x}_i' = 0$, $\hat{x}_j' = 1$ and $\hat{x}_k' = x_k^*$ for all $k \in [n] \setminus \{i, j\}$. Since $c_j \le c_i$ (as $j \in I_{\hat{\Gamma}}$ and $i \in I \setminus I_{\hat{\Gamma}}$), it follows that $\boldsymbol{c}^T \boldsymbol{x}^* \ge \boldsymbol{c}^T \hat{\boldsymbol{x}}'$.

Since $\boldsymbol{c}^T \hat{\boldsymbol{x}}' \ge \boldsymbol{c}^T \boldsymbol{x}'$, we conclude that $\boldsymbol{c}^T \boldsymbol{x}^* \ge \boldsymbol{c}^T \boldsymbol{x}'$. This shows that $\boldsymbol{\gamma}'$ is a suboptimal solution to $\phi(I, \hat{\Gamma})$. □
Last, we provide a condition on the input that guarantees the feasibility of (CU). Recall that the nominal problem aims to select $p$ items with the minimum total cost. If $p \le b$ or $\Gamma \le b$, the uncertain constraint in problem (CU) becomes redundant, and the robust problem reduces to the nominal problem. Therefore, in this section, we focus on the case where $p > b$ and $\Gamma > b$. Furthermore, let us denote by $Q = \max_{I \in \mathcal{I}} |I|$ the cardinality of the largest set in $\mathcal{I}$. Next, we provide a condition that $Q$ must satisfy to guarantee that problem (CU) is feasible. While this condition is interesting on its own, it will be leveraged later in Section 3.3 to prove the polynomiality of the problem in the case of $\mathcal{I}^{SEL}$.

**Proposition 7.** When $n \ge p+Q$, $p > b$ and $\Gamma > b$, Problem (CU) is feasible if and only if $p \le 2b+Q-\Gamma+1$.

*Proof.* Sufficiency(=$\Leftarrow$): Suppose $p \le 2b+Q-\Gamma+1$, we show that there exists a feasible solution for $\mathbf{x} \in \mathcal{X}$.

* When $\hat{\Gamma} = Q$, since $p \le 2b+Q-\Gamma+1$ and $p > b$, it follows that $\sum_{i \in \bar{I}} \delta_i = \Gamma - \hat{\Gamma} = \Gamma - Q \le 2b - p + 1 \le b$. Given that $n \ge p+Q$, there is a feasible solution $\mathbf{x}$ such that $\sum_{i \in \bar{I}} x_i = p$.

* When $\hat{\Gamma} < Q$, we discuss two subcases.

- If $\sum_{i \in \bar{I}} \delta_i = \Gamma - \hat{\Gamma} \le b$, then the condition $n \ge p+Q$ again guarantees the feasibility of $\sum_{i \in \bar{I}} x_i = p$.

- If $\sum_{i \in \bar{I}} \delta_i = \Gamma - \hat{\Gamma} > b$, and there is a feasible solution $\mathbf{x}$ if and only if $p \le Q - \hat{\Gamma} + b$. The worst-case scenario occurs when $\hat{\Gamma}$ takes its largest value (not greater than $Q$). We claim that this is when $\hat{\Gamma} = \Gamma - b - 1$: since $b+1 \le \Gamma \le 2b+Q-p+1 \le b+Q$, we have $0 \le \Gamma - b - 1 \le Q - 1$, proving the claim. Therefore, the condition $p \le 2b+Q-\Gamma+1$ is sufficient to ensure feasibility.

Necessity(=$\Rightarrow$): Suppose $p > 2b+Q-\Gamma+1$. Consider the case where $\hat{\Gamma} = \Gamma - b - 1$, so that $\sum_{i \in \bar{I}} \delta_i = \Gamma - \hat{\Gamma} = b+1$. Then, feasibility requires $p \le Q - \hat{\Gamma} + b \le 2b+Q-\Gamma+1$, which contradicts the assumption. $\square$

Therefore, if the condition stated in Proposition 7 fails to hold, there always exists a scenario that leads to an unbounded (infinite) objective value.

## 3.2 NP-hardness of the general case

We now show that problem (CU) is hard to solve already when $\mathcal{I} = \mathcal{I}^{KP}$, in contrast to Proposition 4.

**Proposition 8.** *Problem (CU) is NP-hard even when $\mathcal{I} = \mathcal{I}^{KP}$.*

*Proof.* We consider a reduction from the partition problem, which given the integers $k_1, \dots, k_m$ that sum up to $2K$, seeks a set $S$ of cardinality $|S| = m/2$ such that $\sum_{i \in S} k_i = \sum_{i \in [m] \setminus S} k_i = K$. We define the following instance of (CU) by setting $n = m+1$, $d_i = k_i$ and $c_i = -k_i$ for each $i \in [m]$, $d_{m+1} = K+1$, $c_{m+1} = -K-1$, $C = K$, $p = m/2$, $\Gamma = 1$ and $b = 0$. We prove next that there exists a *yes* solution to the partition problem if and only if the optimal solution cost of the constructed instance of (CU) has a cost of $-K$.

Let $S \subseteq [m]$ be some set and define $I = S$. We see that $I$ is feasible for the outermost minimization problem if and only if $k(S) \le C$.
Suppose first that $|S| < m/2$ and consider the solution $\gamma = (0, \dots, 0)$ for the maximization problem. Then, for any solution $\boldsymbol{x} \in \mathcal{X}$, there must be $i' \in [n] \setminus S$ such that $x_{i'} = 1$, so $\boldsymbol{x}$ turns out to be infeasible for the constraint associated with $\boldsymbol{\delta} \in \Delta^\Gamma(I, (0, \dots, 0))$ such that $\delta_{i'} = 1$.

Therefore, we assume next that $|S| = m/2$ and we look at the maximization problem. Suppose $\gamma_{i'} = 1$ for some $i' \in S$. In this case, there is a feasible solution for the inner minimization problem for which $x_i = 1$ for $i \in S \setminus \{i'\}$ and $x_{m+1} = 1$, with cost less than $-K$. Otherwise, suppose $\gamma = (0, \dots, 0)$. Then, the only feasible solution for the inner minimization problem is $x_i = 1$ if and only if $i \in S$, with cost exactly $-K$. Thus, this latter choice of $\gamma$ is optimal for the maximization problem and the overall cost of the solution is $-k(S)$, which is equal to $-K$ if and only if $S$ is a yes solution to the partition problem. $\square$

### 3.3 Selection query sets

We prove in this subsection that in the special case $\mathcal{I}^{SEL} = \{I \subseteq [n] \mid |I| \le q\}$ (so $Q = q$), the optimal solution is to query from the $(b+1)$-st to the $(b+q)$-th cheapest items, where $b$ is the right-hand side of the uncertain constraint. Hence, thanks to Theorem 1, the resulting optimization problem can be solved in $O(n)$. Notice that here also, Assumption 2 is only made to ease the proofs, as the algorithm itself does not require to sort the items.

The following result proves that $I^* = \{b+1, b+2, \dots, b+q\}$ is an optimal solution. The main part of the proof lies in determining its objective value defined by $\Phi(I^*)$. We begin by establishing the rules for constructing an optimal selection of variables $\boldsymbol{x}$ under a given $\hat{\Gamma} \in \mathcal{G}_I$, and derive a closed-form expression for $\phi(I^*, \hat{\Gamma})$. We next identify the worst-case value of $\hat{\Gamma}$ to determine the value of $\Phi(I^*)$. Finally, we construct a scenario under which no solution $I \in \mathcal{I}^{SEL}$ can achieve a better objective value than $\Phi(I^*)$.

**Theorem 2.** If $n \ge p+q$, $p > b$ and $\Gamma > b$, there is an optimal solution to problem (CU) with $\mathcal{I} = \mathcal{I}^{SEL}$ such that $I^* = \{b+1, b+2, \dots, b+q\}$, whose value is $\sum_{i=1}^b c_i + \sum_{i=\Gamma+1}^{p-b+\Gamma} c_i$.

*Proof.* We assume that the two conditions of Proposition 7 are verified. Our aim is to prove that $I^* = \{b+1, b+2, \dots, b+q\}$ dominates every solution $I \in \mathcal{I}^{SEL}$, that is, $\Phi(I^*) \le \Phi(I)$ for all $I \in \mathcal{I}^{SEL}$. We first determine the value of $\Phi(I^*) = \max_{\hat{\Gamma} \in \mathcal{G}_I} \phi(I^*, \hat{\Gamma})$ by proving that

$$ \Gamma - b \in \arg\max_{\hat{\Gamma} \in \mathcal{G}_I} \phi(I^*, \hat{\Gamma}). \qquad (6) $$

For any given $\hat{\Gamma} \in \mathcal{G}_I$, by Proposition 6, the worst-case of uncertainty in $I^*$ is attained when $\gamma_i = 1$ for all $i \in I^*_{\hat{\Gamma}} = \{b+1, b+2, \dots, b+\hat{\Gamma}\}$, and $\gamma_i = 0$ for all $i \in I^* \setminus I^*_{\hat{\Gamma}} = \{b+\hat{\Gamma}+1, b+\hat{\Gamma}+2, \dots, b+q\}$. Thus, by Proposition 5,

$$ \phi(I^*, \hat{\Gamma}) = \min_{\boldsymbol{x} \in \mathcal{X}} \sum_{i \in [n]} c_i x_i \qquad (7a) $$

$$ \text{s.t.} \quad \sum_{i \in I^*_{\hat{\Gamma}}} x_i + \min \left\{ \sum_{i \in \bar{I}^*} x_i, \bar{\Gamma} \right\} \le b. \qquad (7b) $$

For ease of discussion, let $\bar{I}_1^* = \{1, 2, \dots, b\}$ and $\bar{I}_2^* = \{b+q+1, b+q+2, \dots, n\}$. We decompose the decision vector $\boldsymbol{x}$ into selection decisions over the disjoint subsets $I^*_{\hat{\Gamma}}, I^* \setminus I^*_{\hat{\Gamma}}, \bar{I}_1^*$, and $\bar{I}_2^*$, which we denote $X^1, X^2, X^3$, and $X^4$, respectively. Introducing first a minimization over the sizes of
these sets, the problem defined by (7) can be reformulated as:

$$ \min_{\substack{p^1 \in [\hat{\Gamma}]_0, p^2 \in [q-\hat{\Gamma}]_0, \\ p^3 \in [b]_0, p^4 \in [n-b-q]_0}} \left\{ \min_{\substack{X^1 \subseteq I_*^\cdot: X^2 \subseteq (I^* \setminus I_*^\cdot): X^3 \subseteq \hat{I}_*^\cdot: X^4 \subseteq \hat{I}_*^\cdot: \\ |X^1|=p^1, |X^2|=p^2, |X^3|=p^3, |X^4|=p^4}} \sum_{i \in X^1} c_i + \sum_{i \in X^2} c_i + \sum_{i \in X^3} c_i + \sum_{i \in X^4} c_i \right\} \quad (8a) $$

$$ \text{s.t.} \quad p^1 + \min\{p^4 + p^4, \bar{\Gamma}\} \leq b \qquad (8b) $$

$$ p^1 + p^2 + p^3 + p^4 = p \qquad (8c) $$

Observe that, within each set $X^k$, selecting the cheapest items (i.e., the first items) ensures minimal total cost without affecting feasibility. Then, (8) can be reformulated as follows:

$$ \min_{\substack{p^1 \in [\hat{\Gamma}]_0, p^2 \in [q-\hat{\Gamma}]_0, \\ p^3 \in [b]_0, p^4 \in [n-b-q]_0}} \sum_{i \in p^1(I_*^\cdot)} c_i + \sum_{i \in p^2(I_*^\cdot \setminus I_*^\cdot)} c_i + \sum_{i \in p^3(\bar{I}_1^\cdot)} c_i + \sum_{i \in p^4(\bar{I}_2^\cdot)} c_i \quad (9a) $$

$$ \text{s.t.} \quad p^1 + \min\{p^3 + p^4, \bar{\Gamma}\} \leq b \qquad (9b) $$

$$ p^1 + p^2 + p^3 + p^4 = p \qquad (9c) $$

where $k(X)$ denotes the first $k$ elements of set $X$.

Recalling that $c_i \le c_j \le c_k \le c_\ell$, for all $i \in \bar{I}_1^*$, $j \in \bar{I}_2^*$, $k \in I^* \setminus \bar{I}_1^*$ and $\ell \in \bar{I}_2^*$, we now construct an optimal solution to the problem defined by (9) for any given $\hat{\Gamma} \in \mathcal{G}_I$. We discuss the following cases:

* $\bar{\Gamma} > b$: In this case, the constraint (9b) is satisfied if and only if $p^1 + p^3 + p^4 \le b$. As the items in $\bar{I}_1^*$ are the cheapest ones, and $p^3 \in [b]_0$, an optimal solution in this case is thus given by $p^3 = b$, $p^1 = p^4 = 0$, and $p^2 = p-b$. Since $p^2 \in [q-\hat{\Gamma}]_0$, we need to show that $q-\hat{\Gamma} \ge p-b$ to ensure that this solution is feasible. This holds because: $p-b-(q-\hat{\Gamma}) = p-b-q+\Gamma-\bar{\Gamma} \le p-b-q+\Gamma-b-1 \le 0$, where the last inequality follows from the feasibility condition stated in Proposition 7.

* $\bar{\Gamma} \le b$: In this case, due to the min operator in (9b), we distinguish two subcases:

- If $p^3 + p^4 \ge \bar{\Gamma}$, then (9b) becomes $p^1 + \bar{\Gamma} \le b$. An optimal selection that minimizes the cost is achieved with $p^3 = b$, $p^1 = b-\bar{\Gamma}$ and $p^2 + p^4 = p-2b+\bar{\Gamma}$.

- If $p^3 + p^4 < \bar{\Gamma}$, then (9b) becomes $p^1 + p^3 + p^4 \le b$, which implies that $p^4 = 0$. Thus, a feasible solution exists if and only if $p^2 \ge p-b$, which requires that $p-b \le q-\hat{\Gamma} = q-\Gamma+\bar{\Gamma}$. Equivalently, this condition is $\bar{\Gamma} \ge p-b-q+\Gamma$. Observe that if $p-b-q+\Gamma > b$, there does not exist a feasible solution. Otherwise, since $p^3+p^4 < \bar{\Gamma}$, an optimal feasible solution is given by $p^3 = \bar{\Gamma}-1(<b)$, $p^1 = b-\bar{\Gamma}+1$ and $p^2 = p-b(>p-2b+\bar{\Gamma})$, whose cost is not less than the first subcase.

Overall, when $\bar{\Gamma} \le b$, an optimal solution is attained at $p^3 = b$, $p^1 = b-\bar{\Gamma}$ and $p^2 + p^4 = p-2b+\bar{\Gamma}$.

Hence, we have

$$ \phi(I^*, \hat{\Gamma}) = \begin{cases} \sum_{i=1}^{b} c_i + \sum_{i=b+\hat{\Gamma}+1}^{p+\hat{\Gamma}} c_i & \text{if } \hat{\Gamma} \le \Gamma - b, \\ \sum_{i=1}^{2b-\Gamma+\hat{\Gamma}} c_i + \sum_{i=b+\hat{\Gamma}+1}^{p-b+\Gamma} c_i & \text{if } \hat{\Gamma} \ge \Gamma - b + 1 \text{ and } 2b - \Gamma + \hat{\Gamma} \le p - 1, \\ \sum_{i=1}^{p} c_i & \text{if } \hat{\Gamma} \ge \Gamma - b + 1 \text{ and } 2b - \Gamma + \hat{\Gamma} \ge p. \end{cases} \quad (10) $$
In the case where $\hat{\Gamma} \le \Gamma - b$, the function $\phi(I^*, \hat{\Gamma})$ is non-decreasing in $\hat{\Gamma}$, so it is maximized when $\hat{\Gamma} = \Gamma - b$, in which case $\phi(I^*, \Gamma - b) = \sum_{i=1}^b c_i + \sum_{i=\Gamma+1}^{p-b+\Gamma} c_i$. In the case where $\Gamma - b + 1 \le \hat{\Gamma} \le \Gamma - 2b + p - 1$, the function $\phi(I^*, \hat{\Gamma})$ is non-increasing in $\hat{\Gamma}$, so it is maximized when $\hat{\Gamma} = \Gamma - b + 1$. Furthermore,

$$ \phi(I^*, \Gamma - b + 1) = \sum_{i=1}^{b+1} c_i + \sum_{i=\Gamma+2}^{p-b+\Gamma} c_i \le \sum_{i=1}^{b} c_i + \sum_{i=\Gamma+1}^{p-b+\Gamma} c_i = \phi(I^*, \Gamma - b). $$

In the last case, the function is independent of $\hat{\Gamma}$ and $\sum_{i=1}^p c_i \le \phi(I^*, \Gamma - b)$. To conclude the proof of (6), it remains to show that there always exists a $\hat{\Gamma} \in \mathcal{G}_I$ such that $\hat{\Gamma} = \Gamma - b$. This holds since $0 \le \Gamma - b \le q$, as ensured by the conditions given in Proposition 7.

Now, we consider any solution $I \in \mathcal{I}^{SEL}$. Consider the indicator function $1_{\delta^T x > b}$. Observe that because $x$ is binary, we can substitute the constraint on $x$ with a penalization term in the objective function, so for $M$ large enough, we have

$$ \begin{aligned} \Phi(I) = \max_{\gamma \in \Delta^\Gamma} \min_{x \in \mathcal{X}} \max_{\delta \in \Delta^\Gamma(I, \gamma)} \mathbf{c}^T x + M 1_{\delta^T x > b} &\ge \max_{\gamma \in \Delta^\Gamma} \max_{\delta \in \Delta^\Gamma(I, \gamma)} \min_{x \in \mathcal{X}} \mathbf{c}^T x + M 1_{\delta^T x > b} \\ &= \max_{\delta \in \Delta^\Gamma} \min_{x \in \mathcal{X}} \mathbf{c}^T x + M 1_{\delta^T x > b} \\ &\ge \min_{x \in \mathcal{X}} \mathbf{c}^T x + M 1_{(\delta')^T x > b}, \end{aligned} $$

where $\delta'_i = 1$, for each $i \in [\Gamma]$ and $\delta'_i = 0$, for each $i \in \{\Gamma + 1, \Gamma + 2, \dots, n\}$. We see that the optimal solution to the minimization problem picks at most $b$ items from the first $\Gamma$ items, and the remaining items must be picked from the set $\{\Gamma + 1, \Gamma + 2, \dots, n\}$. Therefore, $\Phi(I) \ge \sum_{i=1}^b c_i + \sum_{i=\Gamma+1}^{p-b+\Gamma} c_i = \Phi(I^*)$. $\square$

If $\mathcal{I} = \mathcal{I}^{SEL}$, thanks to Theorem 2, the problem can be solved in $O(n)$ by relying on Theorem 1. Notice that while the optimal value of this case does not depend on the value of $q$, the value of $q$ determines the feasibility of the problem. We state this result in the following corollary.

**Corollary 1.** If $\mathcal{I} = \mathcal{I}^{SEL}$, problem (CU) can be solved in $O(n)$.

## 3.4 Linear programming formulations

We clarify that in this section, since all costs are assumed to non-negative, the constraint in $\mathcal{X}$ can be equivalently rewritten as an inequality (i.e., $\sum_{i \in [n]} x_i \ge p$), which simplifies the reformulations.

### 3.4.1 Linear formulation for $\Phi$

From Proposition 5, $\Phi(I)$ can be rewritten as

$$ \Phi(I) = \max_{\hat{\Gamma} \in \mathcal{G}_I} \phi(I, \hat{\Gamma}) = \max_{\gamma \in \Delta^\Gamma} \min_{x \in \mathcal{X}} \left\{ \mathbf{c}^T x \left| \sum_{i \in I} \gamma_i x_i + \min \left\{ \sum_{i \in \bar{I}} x_i, \Gamma - \sum_{i \in I} \gamma_i \right\} \le b \right. \right\}. $$
Expressing the inner minimization problem over **x** as the minimum of two separate optimization problems leads to

$$
\Phi(I) = \max_{\gamma \in \Delta^\Gamma} \min \left[ \min \left\{ \mathbf{c}^T \mathbf{x} \mid \sum_{i \in I} \gamma_i x_i + \sum_{i \in \bar{I}} x_i \le b, \sum_{i \in [n]} x_i \ge p, \mathbf{x} \in \{0, 1\}^n \right\}, \right. \\
\left. \min \left\{ \mathbf{c}^T \mathbf{x} \mid \sum_{i \in I} \gamma_i x_i + \Gamma - \sum_{i \in I} \gamma_i \le b, \sum_{i \in [n]} x_i \ge p, \mathbf{x} \in \{0, 1\}^n \right\} \right].
$$

We next introduce a property of the two inner minimization problems. Given a binary vector
**μ** and an integer **ν**, we define the following general set

$$
\mathcal{X}' = \left\{ \mathbf{x} \in \mathbb{R}_+^n \mid \mathbf{\mu}^T \mathbf{x} \le \mathbf{\nu}, \sum_{i \in [n]} x_i \ge p, x_i \le 1, \forall i \in [n] \right\}.
$$

**Observation 3.** $\mathcal{X}'$ is an integral polytope.

Proof. We prove that the matrix defining the constraints is Totally Unimodular (TU). We begin by analyzing the coefficient matrix associated with **x** in the first two constraints: **μ**<sup>T</sup>**x** ≤ **ν** and Σ<sub>i∈[n]</sub> -**x**<sub>i</sub> ≤ -**p**, where **μ** = {0, 1}<sup>n</sup>. Every 2 × 2 submatrix of this matrix has determinant 0, +1 or -1. Therefore, the first two rows form a totally unimodular matrix. Last, the constraints **x** ≤ **1** form an identity matrix, so overall, the constraints of the problem form a TU matrix. □

Thanks to Observation 3, we can relax the integrality restriction on **x**. Introducing an epigraphic
formulation for the outermost minimum, we obtain:

$$
\begin{array}{ll}
\Phi(I) = \max \omega & \\
\text{s.t. } \omega \le \min c^T x & \\
\qquad \text{s.t. } \sum_{i \in I} \gamma_i x_i + \sum_{i \in \bar{I}} x_i \le b & [\lambda^0] \\
\qquad \sum_{i \in [n]} x_i \ge p & [\alpha^0] \\
\qquad x_i \le 1, & \forall i \in [n] \\
\qquad x_i \ge 0, & \forall i \in [n] \\
\omega \le \min c^T x & \\
\qquad \text{s.t. } \sum_{i \in I} \gamma_i x_i + \Gamma - \sum_{i \in I} \gamma_i \le b & [\lambda^1] \\
\qquad \sum_{i \in [n]} x_i \ge p & [\alpha^1] \\
\qquad x_i \le 1, & \forall i \in [n] \\
\qquad x_i \ge 0, & \forall i \in [n]
\end{array}
$$

We introduce dual variables for each constraint in the above reformulation, as indicated in the
corresponding brackets. Dualizing the two inner linear programs, and removing the maximizations,
we obtain

$$
\begin{align*}
\Phi(I) &= \max \omega \\
\text{s.t.} \quad &\omega \le p \cdot \alpha^0 - \mathbf{1}^T \boldsymbol{\beta}^0 - b \cdot \lambda^0 \\
&\omega \le p \cdot \alpha^1 - \mathbf{1}^T \boldsymbol{\beta}^1 - (b + \sum_{i \in I} \gamma_i - \Gamma)\lambda^1 \\
&\alpha^\ell - \beta_i^\ell - \gamma_i \cdot \lambda^\ell \le c_i, \qquad \forall i \in I, \forall \ell \in \{0, 1\} \\
&\alpha^\ell - \beta_i^\ell - (1-\ell)\lambda^\ell \le c_i, \qquad \forall i \in \bar{I}, \forall \ell \in \{0, 1\} \\
&\sum_{i \in I} \gamma_i \le \Gamma \\
&\boldsymbol{\gamma} \in \{0, 1\}^{|I|}, \alpha^0, \boldsymbol{\beta}^0, \lambda^0, \alpha^1, \boldsymbol{\beta}^1, \lambda^1 \ge 0.
\end{align*}
$$

Thanks to Proposition 6, given a budget $\hat{\Gamma}$ of deviations for $\gamma$, we have $\gamma_i^* = 1$, for all $i \in I_{\hat{\Gamma}}$.
Thus, recalling that $\Phi(I) = \max_{\hat{\Gamma} \in \mathcal{G}_I} \phi(I, \hat{\Gamma})$, we can formulate $\phi(I, \hat{\Gamma})$ as follows

$$
\begin{align*}
\phi(I, \hat{\Gamma}) &= \max \omega \\
\text{s.t.} \quad &\omega \le p \cdot \alpha^0 - \mathbf{1}^T \boldsymbol{\beta}^0 - b \cdot \lambda^0 \quad [e^0] \\
&\omega \le p \cdot \alpha^1 - \mathbf{1}^T \boldsymbol{\beta}^1 - (b + \hat{\Gamma} - \Gamma)\lambda^1 \quad [e^1] \\
&\alpha^\ell - \beta_i^\ell - \lambda^\ell \le c_i, \quad \forall i \in I_{\hat{\Gamma}}, \forall \ell \in \{0, 1\} \quad [f_i^\ell] \\
&\alpha^\ell - \beta_i^\ell \le c_i, \quad \forall i \in I \setminus I_{\hat{\Gamma}}, \forall \ell \in \{0, 1\} \quad [g_i^\ell] \\
&\alpha^\ell - \beta_i^\ell - (1-\ell)\lambda^\ell \le c_i, \quad \forall i \in \bar{I}, \forall \ell \in \{0, 1\} \quad [h_i^\ell] \\
&\alpha^0, \boldsymbol{\beta}^0, \lambda^0, \alpha^1, \boldsymbol{\beta}^1, \lambda^1 \ge 0
\end{align*}
$$

The dual variables corresponding to each constraint are indicated in the brackets of the above reformulation. Specifically, **f** is introduced for all $i \in I_{\hat{\Gamma}}$; **g** for all $i \in I \setminus I_{\hat{\Gamma}}$; and **h** for all $i \in \bar{I}$.
Dualizing the above linear programs, we obtain

$$
\phi(I, \hat{\Gamma}) = \min \sum_{\ell \in \{0,1\}} \sum_{i \in I_{\hat{\Gamma}}} c_i f_i^{\ell} + \sum_{\ell \in \{0,1\}} \sum_{i \in I \setminus I_{\hat{\Gamma}}} c_i g_i^{\ell} + \sum_{\ell \in \{0,1\}} \sum_{i \in \bar{I}} c_i h_i^{\ell} \quad (11a)
$$

$$
\text{s.t.} \quad e^0 + e^1 = 1 \tag{11b}
$$

$$
-p \cdot e^{\ell} + \sum_{i \in I_{\hat{\Gamma}}} f_i^{\ell} + \sum_{i \in I \setminus I_{\hat{\Gamma}}} g_i^{\ell} + \sum_{i \in \bar{I}} h_i^{\ell} \ge 0, \qquad \forall \ell \in \{0, 1\} \quad (11c)
$$

$$
e^{\ell} - f_{i}^{\ell} \ge 0, \qquad \forall i \in I_{\hat{\Gamma}}, \forall \ell \in \{0, 1\} \quad (11d)
$$

$$
e^{\ell} - g_{i}^{\ell} \ge 0, \qquad \forall i \in I \setminus I_{\hat{\Gamma}}, \forall \ell \in \{0, 1\} \quad (11e)
$$

$$
e^{\ell} - h_{i}^{\ell} \ge 0, \qquad \forall i \in \bar{I}, \forall \ell \in \{0, 1\} \quad (11f)
$$

$$
b \cdot e^0 - \sum_{i \in I_{\hat{\Gamma}}} f_i^0 - \sum_{i \in \bar{I}} h_i^0 \ge 0 \qquad (11g)
$$

$$
(b + \hat{\Gamma} - \Gamma)e^1 - \sum_{i \in I_{\hat{\Gamma}}} f_i^1 \ge 0 \qquad (11h)
$$

$$
e^{\ell}, \boldsymbol{f}^{\ell}, \boldsymbol{g}^{\ell}, \boldsymbol{h}^{\ell} \ge 0, \qquad \forall \ell \in \{0, 1\} \quad (11i)
$$
Introducing the variable $\eta$ as an epigraphic reformulation of the maximum over $\hat{\Gamma}$ in the definition of $\Phi(I)$, and adding the index $\hat{\Gamma}$ to the variables of (11a)-(11i), we obtain that

$$ \Phi(I) = \min \eta \tag{12a} $$

$$ \text{s.t. } \eta \ge \min \left\{ \sum_{\ell \in \{0,1\}} \sum_{i \in I_{\hat{\Gamma}}} c_i f_{i, \hat{\Gamma}}^{\ell} + \sum_{\ell \in \{0,1\}} \sum_{i \in I \setminus I_{\hat{\Gamma}}} c_i g_{i, \hat{\Gamma}}^{\ell} + \sum_{\ell \in \{0,1\}} \sum_{i \in \bar{I}} c_i h_{i, \hat{\Gamma}}^{\ell} \mid \right. \tag{12b} $$

$$ (e_{\hat{\Gamma}}^{0}, \mathbf{f}_{\hat{\Gamma}}^{0}, \mathbf{g}_{\hat{\Gamma}}^{0}, \mathbf{h}_{\hat{\Gamma}}^{0}, e_{\hat{\Gamma}}^{1}, \mathbf{f}_{\hat{\Gamma}}^{1}, \mathbf{g}_{\hat{\Gamma}}^{1}, \mathbf{h}_{\hat{\Gamma}}^{1}) \text{ satisfies (11b) - (11i)} \right\}, \quad \forall \hat{\Gamma} \in \mathcal{G}_I. $$

We finally obtain the linear programming formulation for $\Phi(I)$ by observing that the minimization can be removed in the right-hand-side of (12b):

$$ \Phi(I) = \min \eta \tag{13a} $$

$$ \text{s.t. } \eta \ge \sum_{\ell \in \{0,1\}} \sum_{i \in I_{\hat{\Gamma}}} c_i f_{i, \hat{\Gamma}}^{\ell} + \sum_{\ell \in \{0,1\}} \sum_{i \in I \setminus I_{\hat{\Gamma}}} c_i g_{i, \hat{\Gamma}}^{\ell} + \sum_{\ell \in \{0,1\}} \sum_{i \in \bar{I}} c_i h_{i, \hat{\Gamma}}^{\ell}, \quad \forall \hat{\Gamma} \in \mathcal{G}_I \tag{13b} $$

$$ e_{\hat{\Gamma}}^{0} + e_{\hat{\Gamma}}^{1} = 1, \quad \forall \hat{\Gamma} \in \mathcal{G}_I \tag{13c} $$

$$ -p \cdot e_{\hat{\Gamma}}^{\ell} + \sum_{i \in I_{\hat{\Gamma}}} f_{i, \hat{\Gamma}}^{\ell} + \sum_{i \in I \setminus I_{\hat{\Gamma}}} g_{i, \hat{\Gamma}}^{\ell} + \sum_{i \in \bar{I}} h_{i, \hat{\Gamma}}^{\ell} \ge 0, \quad \forall \hat{\Gamma} \in \mathcal{G}_I, \forall \ell \in \{0,1\} \tag{13d} $$

$$ e_{\hat{\Gamma}}^{\ell} - f_{i, \hat{\Gamma}}^{\ell} \ge 0, \quad \forall i \in I_{\hat{\Gamma}}, \forall \hat{\Gamma} \in \mathcal{G}_I, \forall \ell \in \{0,1\} \tag{13e} $$

$$ e_{\hat{\Gamma}}^{\ell} - g_{i, \hat{\Gamma}}^{\ell} \ge 0, \quad \forall i \in I \setminus I_{\hat{\Gamma}}, \forall \hat{\Gamma} \in \mathcal{G}_I, \forall \ell \in \{0,1\} \tag{13f} $$

$$ e_{\hat{\Gamma}}^{\ell} - h_{i, \hat{\Gamma}}^{\ell} \ge 0, \quad \forall i \in \bar{I}, \forall \hat{\Gamma} \in \mathcal{G}_I, \forall \ell \in \{0,1\} \tag{13g} $$

$$ b \cdot e_{\hat{\Gamma}}^{0} - \sum_{i \in I_{\hat{\Gamma}}} f_{i, \hat{\Gamma}}^{0} - \sum_{i \in \bar{I}} h_{i, \hat{\Gamma}}^{0} \ge 0, \quad \forall \hat{\Gamma} \in \mathcal{G}_I \tag{13h} $$

$$ (b + \hat{\Gamma} - \Gamma) e_{\hat{\Gamma}}^{1} - \sum_{i \in I_{\hat{\Gamma}}} f_{i, \hat{\Gamma}}^{1} \ge 0, \quad \forall \hat{\Gamma} \in \mathcal{G}_I \tag{13i} $$

$$ e^{\ell}, \mathbf{f}^{\ell}, \mathbf{g}^{\ell}, \mathbf{h}^{\ell} \ge 0, \quad \forall \ell \in \{0,1\} \tag{13j} $$

### 3.4.2 Mixed-integer linear programming formulation for $\mathcal{I}^{GEN}$

To present the mixed-integer linear programming reformulation of this subsection, we define the set of binary vectors that represent the support of some $I \in \mathcal{I}^{GEN}$, formally:

$$ \mathcal{W}^{GEN} = \left\{ \mathbf{w} \in \{0,1\}^n \mid \sum_{i \in [n]} \sigma_{\ell i} w_i \le \sigma_{\ell 0}, \forall \ell \in [L] \right\}. $$

Each vector $\mathbf{w} \in \mathcal{W}^{GEN}$ corresponds bijectively to a set $I \in \mathcal{I}^{GEN}$, where $w_i = 1$ if and only if $i \in I$, and $w_i = 0$ otherwise. Further, for each $\hat{\Gamma} \in [\Gamma]_0$, we introduce binary variables $u_{i, \hat{\Gamma}}$ for all $i \in [n]$, indicating whether item $i$ belongs to the set $I_{\hat{\Gamma}}$ derived from $I$. That is, $u_{i, \hat{\Gamma}} = 1$ if $i \in I_{\hat{\Gamma}}$, and $u_{i, \hat{\Gamma}} = 0$ otherwise. These definitions enable us to derive the following reformation for
the problem $\min_{I \in \mathcal{I}} \Phi(I)$, containing polynomially many variables and constraints:

$$ \min \eta \tag{14a} $$

$$ \begin{array}{l} \text{s.t.} \quad \eta \ge \sum_{\ell \in \{0,1\}} \sum_{i \in [n]} c_i f_{i, \hat{\Gamma}}^{\ell} + \sum_{\ell \in \{0,1\}} \sum_{i \in [n]} c_i g_{i, \hat{\Gamma}}^{\ell} + \sum_{\ell \in \{0,1\}} \sum_{i \in [n]} c_i h_{i, \hat{\Gamma}}^{\ell}, \quad \forall \hat{\Gamma} \in [\Gamma]_0 \tag{14b} \\ \phantom{\text{s.t.} \quad \eta \ge \sum_{\ell \in \{0,1\}} \sum_{i \in [n]} c_i f_{i, \hat{\Gamma}}^{\ell} + \sum_{\ell \in \{0,1\}} \sum_{i \in [n]} c_i g_{i, \hat{\Gamma}}^{\ell} + \sum_{\ell \in \{0,1\}} \sum_{i \in [n]} c_i h_{i, \hat{\Gamma}}^{\ell}} & \end{array} $$

$$ e_{\hat{\Gamma}}^{0} + e_{\hat{\Gamma}}^{1} = 1, \quad \forall \hat{\Gamma} \in [\Gamma]_0 \tag{14c} $$

$$ -p \cdot e_{\hat{\Gamma}}^{\ell} + \sum_{i \in [n]} f_{i, \hat{\Gamma}}^{\ell} + \sum_{i \in [n]} g_{i, \hat{\Gamma}}^{\ell} + \sum_{i \in [n]} h_{i, \hat{\Gamma}}^{\ell} \ge 0, \quad \forall \hat{\Gamma} \in [\Gamma]_0, \forall \ell \in \{0, 1\} \tag{14d} $$

$$ e_{\hat{\Gamma}}^{\ell} - f_{i, \hat{\Gamma}}^{\ell} \ge u_{i, \hat{\Gamma}} - 1, \quad \forall i \in [n], \forall \hat{\Gamma} \in [\Gamma]_0, \forall \ell \in \{0, 1\} \tag{14e} $$

$$ e_{\hat{\Gamma}}^{\ell} - g_{i, \hat{\Gamma}}^{\ell} \ge w_i - u_{i, \hat{\Gamma}} - 1, \quad \forall i \in [n], \forall \hat{\Gamma} \in [\Gamma]_0, \forall \ell \in \{0, 1\} \tag{14f} $$

$$ e_{\hat{\Gamma}}^{\ell} - h_{i, \hat{\Gamma}}^{\ell} \ge -w_i, \quad \forall i \in [n], \forall \hat{\Gamma} \in [\Gamma]_0, \forall \ell \in \{0, 1\} \tag{14g} $$

$$ b \cdot e_{\hat{\Gamma}}^{0} - \sum_{i \in [n]} f_{i, \hat{\Gamma}}^{0} - \sum_{i \in [n]} h_{i, \hat{\Gamma}}^{0} \ge 0, \quad \forall \hat{\Gamma} \in [\Gamma]_0 \tag{14h} $$

$$ (b + \hat{\Gamma} - \Gamma)e_{\hat{\Gamma}}^{1} - \sum_{i \in [n]} f_{i, \hat{\Gamma}}^{1} \ge 0, \quad \forall \hat{\Gamma} \in [\Gamma]_0 \tag{14i} $$

$$ u_{i, \hat{\Gamma}} \le w_i, \quad \forall i \in [n], \forall \hat{\Gamma} \in [\Gamma]_0 \tag{14j} $$

$$ u_{i, \hat{\Gamma}} \ge u_{j, \hat{\Gamma}} - 1 + w_i, \quad \forall i \in [n], \forall j \in [n] : j > i, \forall \hat{\Gamma} \in [\Gamma]_0 \tag{14k} $$

$$ f_{i, \hat{\Gamma}}^{\ell} \le u_{i, \hat{\Gamma}}, \quad \forall i \in [n], \forall \hat{\Gamma} \in [\Gamma]_0, \forall \ell \in \{0, 1\} \tag{14l} $$

$$ g_{i, \hat{\Gamma}}^{\ell} \le w_i - u_{i, \hat{\Gamma}}, \quad \forall i \in [n], \forall \hat{\Gamma} \in [\Gamma]_0, \forall \ell \in \{0, 1\} \tag{14m} $$

$$ h_{i, \hat{\Gamma}}^{\ell} \le 1 - w_i, \quad \forall i \in [n], \forall \hat{\Gamma} \in [\Gamma]_0, \forall \ell \in \{0, 1\} \tag{14n} $$

$$ \sum_{i \in [n]} u_{i, \hat{\Gamma}} = \min \left\{ \hat{\Gamma}, \sum_{i \in [n]} w_i \right\}, \quad \forall \hat{\Gamma} \in [\Gamma]_0 \tag{14o} $$

$$ \mathbf{w} \in \mathcal{W}^{\text{GEN}} \tag{14p} $$

$$ \mathbf{u} \in \{0, 1\}^{n \times (\Gamma+1)} \tag{14q} $$

$$ e_{\hat{\Gamma}}^{0}, e_{\hat{\Gamma}}^{1}, \mathbf{f}_{\hat{\Gamma}}^{0}, \mathbf{g}_{\hat{\Gamma}}^{0}, \mathbf{h}_{\hat{\Gamma}}^{0}, \mathbf{f}_{\hat{\Gamma}}^{1}, \mathbf{g}_{\hat{\Gamma}}^{1}, \mathbf{h}_{\hat{\Gamma}}^{1} \ge 0, \quad \forall \hat{\Gamma} \in [\Gamma]_0, \tag{14r} $$

In the above MILP formulation, the constraints (14b)–(14i) are reformulated from the constraints (13b)–(13i) using the variables $\mathbf{w}$ and $\mathbf{u}$. Recall that the items are indexed in non-decreasing order of their costs. Then, the constraints (14j)–(14k) ensure that if $w_i = 1$ and $u_j = 1$ for some $j > i$, then $u_i$ must also be set to one, in accordance with the definition of $I_{\hat{\Gamma}}$. Note that the variables $\mathbf{f}$, $\mathbf{g}$, $\mathbf{h}$ correspond to items in the sets $I_{\hat{\Gamma}}$, $I \setminus I_{\hat{\Gamma}}$, $\bar{I}$, respectively. Hence, they should be set to zero for any items not belonging to their respective sets. This requirement is enforced by the constraints (14l)–(14n). Observe that constraint (14o) is non-linear and could be linearized using the big-$M$ technique. Nevertheless, modern solvers such as Gurobi can handle this type of constraints directly, so it is unnecessary (and less efficient) to provide an explicit big-$M$ reformulation in the model.
### 3.4.3 Numerical illustration

We next provide a short numerical illustration of the solving capability of the MILP reformulation derived in Section 3.4.2 for the case $\mathcal{I} = \mathcal{I}^{KP}$. We generated 200 instances with $n \in \{20, 40, 60, 80, 100\}$, $p \in \{n/5, n/10\}$ and $\Gamma \in \{n/5, n/10\}$. For each parameter choice of $(n, p, \Gamma)$, we randomly generated 10 instances. For each instance, $b$ is a random integer between 1 and $n$, **a** and **c** are two vectors, each containing $n$ random values between 0 and 50, and $C$ is a random integer between 1 and the sum of the values in vector **a**. One of the instances led to an infeasible model. Consequently, the results in Table 1, which displays the average solution times across various $n, p, \Gamma$, are obtained from 199 instances. Among these instances, one did not reach an optimal solution within the set time limit of 3600 seconds, with parameter values $n = 100, p = 20$ and $\Gamma = 20$. Its solving time is recorded as 3600 seconds, and the average solution time for this size is therefore marked with an asterisk in the table. All experiments have been realized in Python 3.6, using Gurobi 11.01, on a processor Intel Xeon E312xx (Sandy Bridge) with a clock speed of 2.29GHz.

<table><caption>Table 1: Average solution times (in seconds) of MILP reformulation</caption><thead><tr><th>n</th><th>p = n/10</th><th>Γ = n/10</th><th>p = n/10</th><th>Γ = n/5</th><th>p = n/5</th><th>Γ = n/10</th><th>p = n/5</th><th>Γ = n/5</th></tr></thead><tbody><tr><td>20</td><td></td><td>0.0</td><td></td><td>0.1</td><td></td><td>0.0</td><td></td><td>0.1</td></tr><tr><td>40</td><td></td><td>0.3</td><td></td><td>0.2</td><td></td><td>0.4</td><td></td><td>0.9</td></tr><tr><td>60</td><td></td><td>0.5</td><td></td><td>0.7</td><td></td><td>0.9</td><td></td><td>32.9</td></tr><tr><td>80</td><td></td><td>2.6</td><td></td><td>6.1</td><td></td><td>5.7</td><td></td><td>40.6</td></tr><tr><td>100</td><td></td><td>6.1</td><td></td><td>303.9</td><td></td><td>85.1</td><td></td><td>396.6*</td></tr></tbody></table>

Our computational results indicate the viability of compact formulation (14a)-(14r), which solves all instances with up to 80 items to optimality. The choice of $p$ and $\Gamma$ affects the average computation times, with the smallest choices $p = n/10$ and $\Gamma = n/10$ resulting in the easiest of the considered problems. In particular, the instances we considered with $n = 100, p = 10$ and $\Gamma = 10$ can still be solved in 6.1 seconds on average.

## 4 Conclusion

Decision-dependent information discovery (DDID) is a powerful and flexible modeling approach that extends classic robust optimization problems by another decision-making stage, in which the decision maker is allowed to query uncertain parameters before choosing a solution. This additional stage means that classic robust optimization approaches cannot be directly applied, which has sparked interest in new solution algorithms for this setting. However, little is known about the complexity of DDID for specific underlying optimization problems.

This paper has started the study of this complexity with particularly simple special cases based on the selection feasibility set. We differentiated between uncertainty in the objective and uncertainty in the constraints. In the first case, we showed that the problem is NP-hard if the set of possible queries is not further restricted, but were able to derive strongly polynomial solution methods in the case of selection query sets or more general knapsack query sets. In the second case, we can give a complete analytical description when the optimization problem is feasible. While the problem is NP-hard even for knapsack query sets, we showed that it remains solvable in strongly polynomial time for selection query sets. Finally, we derived a compact mixed-integer linear programming formulation and showed that using this formulation, problems with knapsack query sets remain solvable within one hour with up to 80 items. Future work will see to extend these results
to continuous budget uncertainty set and to problems with objective uncertainty and more than one item to select.

## References

[1] David Adjiashvili, Sebastian Stiller, and Rico Zenklusen. Bulk-robust combinatorial optimization. *Mathematical Programming*, 149:361–390, 2015.

[2] Eduardo Álvarez-Miranda, Ivana Ljubic, and Paolo Toth. A note on the Bertsimas & Sim algorithm for robust combinatorial optimization problems. *4OR*, 11(4):349–360, 2013.

[3] Ayse N. Arslan and Michael Poss. Uncertainty reduction in robust optimization. *Operations Research Letters*, 55:107131, 2024.

[4] Dimitris Bertsimas and Melvyn Sim. Robust discrete optimization and network flows. *Mathematical Programming*, 98(1-3):49–71, 2003.

[5] Dimitris Bertsimas and Melvyn Sim. The price of robustness. *Operations Research*, 52(1):35–53, 2004.

[6] Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, Robert Endre Tarjan, et al. Time bounds for selection. *Journal of Computer and System Sciences*, 7(4):448–461, 1973.

[7] Christina Büsing, Timo Gersing, and Arie M. C. A. Koster. A branch and bound algorithm for robust binary optimization with budget uncertainty. *Mathematical Programming Computation*, 15(2):269–326, 2023.

[8] Christina Büsing, Timo Gersing, and Arie M. C. A. Koster. Recycling inequalities for robust combinatorial optimization with budget uncertainty. In Alberto Del Pia and Volker Kaibel, editors, *Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Madison, WI, USA, June 21-23, 2023, Proceedings*, volume 13904 of *Lecture Notes in Computer Science*, pages 58–71. Springer, 2023.

[9] André Chassein, Marc Goerigk, Adam Kasperski, and Paweł Zieliński. On recoverable and two-stage robust selection problems with budgeted uncertainty. *European Journal of Operational Research*, 265(2):423–436, 2018.

[10] Matthew Colvin and Christos T Maravelias. A stochastic programming approach for clinical trial planning in new drug development. *Computers & Chemical Engineering*, 32(11):2626–2642, 2008.

[11] Eduardo Conde. An improved algorithm for selecting p items with uncertain returns according to the minmax-regret criterion. *Mathematical Programming*, 100(2):345–353, 2004.

[12] Thomas Erlebach, Michael Hoffmann, Danny Krizanc, Matúš Mihalák, and Rajeev Raman. Computing minimum spanning trees with uncertainty. In *STACS 2008*, pages 277–288. IBFI Schloss Dagstuhl, 2008.

[13] Tomás Feder, Rajeev Motwani, Liadan O’Callaghan, Chris Olston, and Rina Panigrahy. Computing shortest paths with uncertainty. *Journal of Algorithms*, 62(1):1–18, 2007.
[14] Marc Goerigk, Manoj Gupta, Jonas Ide, Anita Schöbel, and Sandeep Sen. The robust knapsack problem with queries. *Computers & Operations Research*, 55:12–22, 2015.

[15] Marc Goerigk and Michael Hartisch. *An Introduction to Robust Combinatorial Optimization*, volume 361 of *International Series in Operations Research & Management Science*. Springer, 2024.

[16] Marc Goerigk and Mohammad Khosravi. Robust combinatorial optimization problems under budgeted interdiction uncertainty. *OR Spectrum*, pages 1–31, 2024.

[17] Grani A Hanasusanto, Daniel Kuhn, and Wolfram Wiesemann. K-adaptability in two-stage robust binary programming. *Operations Research*, 63(4):877–891, 2015.

[18] Tore W Jonsbråten, Roger JB Wets, and David L Woodruff. A class of stochastic programs with decision dependent random elements. *Annals of Operations Research*, 82:83–106, 1998.

[19] Simon Kahan. A model for data in motion. In *Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing*, pages 265–277, 1991.

[20] Adam Kasperski and Paweł Zieliński. Robust recoverable and two-stage selection problems. *Discrete Applied Mathematics*, 233:52–64, 2017.

[21] Thomas Lachmann, Stefan Lendl, and Gerhard J. Woeginger. A linear time algorithm for the robust recoverable selection problem. *Discrete Applied Mathematics*, 303:94–107, 2021.

[22] Nicole Megow, Julie Meißner, and Martin Skutella. Randomization helps computing a minimum spanning tree under uncertainty. *SIAM Journal on Computing*, 46(4):1217–1240, 2017.

[23] Omid Nohadani and Kartikey Sharma. Optimization under decision-dependent uncertainty. *SIAM Journal on Optimization*, 28(2):1773–1795, 2018.

[24] Jérémy Omer, Michael Poss, and Maxime Rougier. Combinatorial robust optimization with decision-dependent information discovery and polyhedral uncertainty. *Open Journal of Mathematical Optimization*, Volume 5(5):1–25, 2024.

[25] Rosario Paradiso, Angelos Georghiou, Said Dabia, and Denise Tönissen. Exact and approximate schemes for robust optimization problems with decision dependent information discovery. *INFORMS Journal on Computing*, 2024. In press.

[26] Michael Poss. Robust combinatorial optimization with variable budgeted uncertainty. *4OR*, 11(1):75–92, 2013.

[27] Senay Solak, John-Paul B Clarke, Ellis L Johnson, and Earl R Barnes. Optimization of R&D project portfolios under endogenous uncertainty. *European Journal of Operational Research*, 207(1):420–433, 2010.

[28] Rüdiger Stephan. Cardinality constrained combinatorial optimization: Complexity and polyhedra. *Discrete Optimization*, 7(3):99–113, 2010.

[29] Phebe Vayanos, Angelos Georghiou, and Han Yu. Robust optimization with decision-dependent information discovery. *Management Science*, 2024. In press.

[30] Phebe Vayanos, Yingxiao Ye, Duncan McElfresh, John Dickerson, and Eric Rice. Robust active preference elicitation. *arXiv preprint arXiv:2003.01899*, 2020.