{'fraction_non_alphanumeric': 0.03359715287368533, 'fraction_numerical': 0.00717093381493679, 'mean_word_length': 4.445440740472919, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 29, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Uncertainty Preferences in Robust Mixed-Integer Linear Optimization with Endogenous Uncertainty

In robust optimization one seeks to make a decision under uncertainty, where the goal is to find the solution with the best worst-case performance. The set of possible realizations of the uncertain data is described by a so-called uncertainty set. In many scenarios, a decision maker may influence the uncertainty regime she is facing, for example, by investing in market research, or in machines which work with higher precision. Recently, this situation was addressed in the literature by introducing decision dependent uncertainty sets (endogenous uncertainty), i.e., uncertainty sets whose structure depends on (typically discrete) decision variables. In this way, one can model the trade-off between reducing the cost of robustness versus the cost of the investment necessary for influencing the uncertainty. However, there is another trade-off to be made here. With different uncertainty regimes, not only do the worst-case optimal solutions vary, but also other aspects of that solutions such as max-regret, best-case performance or predictability of the performance. A decision maker may still be interested in having a performance guarantee, but at the same time be willing to forgo superior worst-case performance if those other aspects can be enhanced by switching to a suitable uncertainty regime. We introduce the notion of uncertainty preference in order to capture such stances. We present three ways to formalize uncertainty preferences and study the resulting mathematical models. The goal is to have reformulations/approximations of these models which can be solved with standard methods. The workhorse is mixed-integer linear and conic optimization. We apply our framework to the uncertain shortest path problem and conduct numerical experiments for the resulting models. We can demonstrate that our models can be handled very well by standard mixed-integer linear solvers.


Background and basic ideas
The presence of uncertainty in decision problems has been a driving factor of research in optimization. Sources for uncertainty are numerous: relevant data may not be available at the time of decision making and have to be estimated. Even if available, relevant data may be riddled with measurement errors, and decisions made may not be implementable exactly. Poor understanding, or ignorance, of uncertainty in decision making may lead to bad performance of a decision. The resulting challenges for optimization have been met under two major paradigms, namely robust optimization and stochastic optimization. The latter is concerned with optimizing moments (mostly expected values) of functions that depend on random variables under a known probability law (see e.g. [15,26]). This approach is appealing as it uses the maximum information about an uncertain process, i.e. its probability distribution. Unfortunately, this comes at the cost of having to deal with mathematical optimization models that more often than not are intractable, so that their solutions have to be approximated with computationally expensive methods. Also, the probability distribution in question may be unknown so that a new source for uncertainty arises, which itself poses a major challenge.
The alternative paradigm of dealing with uncertainty is that of robust optimization. Here, uncertain data is assumed to reside within an appropriately structured uncertainty set and one seeks to find the solution with the best worst-case performance among those solutions that are feasible for all possible realizations of the uncertain data (see e.g. [3,10]). This approach requires more modest assumptions, as no probability law has to be assumed. In addition, the robust counterpart of an uncertain problem can often be reformulated as a convex optimization problem that can be solved in polynomial time. The major drawback of this approach is, that the solutions obtained are often too conservative, courtesy of the pessimistic perspective inherent in robust optimization. Many attempts have been made to alleviate this shortcoming which lead to the development of concepts such as adjustable robustness (see [4]), max-regret robustness (see [17]), among others.
A recent line of literature introduced the notion of endogenous uncertainty where the decision maker has control over an additional set of (often binary) variables which govern the structure of the uncertainty. This approach allows the modelling of situations where the uncertainty can be influenced by the decision maker by investing, for instance, in market research or more precise machines. The concept has been known in the stochastic optimization community for some time, see [14] for an early example. Other examples can be found in [9], who applied a stochastic optimization framework with decision dependent uncertainty to capacity expansion of process networks and the sizes problem in production, and in [11], who considered personnel staffing in the presence of endogenous absenteeism. More recently, the concept of endogenous uncertainty was adopted for distributionally robust optimization, see e.g. [19,22,25]. However, in this text we will focus entirely on the robust optimization point of view.
From a robust optimization perspective, an investment in a modified uncertainty set is only acceptable if the expenses do not exceed the gains in worst-case pay-off under the new uncertainty set. The arising decision problem was recently addressed in [18,21], where the authors studied reformulations amenable to techniques for solving a mixed-integer linear optimization problem (MILP) or more generally, a conic mixed-integer linear optimization problem (C-MILP). In [18] it is also proved that the class of robust optimization problems under endogenous uncertainty is NP-hard. We will expand on the idea of endogenous uncertainty by introducing the notion of uncertainty preference, aiming at tractable formulations.

Uncertainty preferences and main motivation of this study
The framework of robust optimization with endogenous uncertainty allows us to model the trade-off between the cost of uncertainty reduction and worst-case performance. However, there is another trade-off to be made in such a scenario. Since we influence the structure of the uncertainty by our decision we do not only change the robustly optimal solution, we also affect other qualities such a solution exhibits, and a decision maker may have a certain preference with respect to that qualities. We chose the name uncertainty preferences as an overarching title for such preferences, regarding the structure of the uncertainty set and the implied quality of robustly optimal solutions. Let us illustrate the core idea of our paper in a simple yet illustrative example. Figure 1. The travel costs along the edges are uncertain, and only known to lie in a given interval. We can choose to influence uncertainty either on the edges that lead to T 1 or on edges that lead to T 2 . We refer to the uncertainty regime where no influence on the uncertainty is taken as U 0 , the one where uncertainty is affected on paths towards T i is referred to as U i , where i = 1, 2. Our aim is to choose a path from the source-vertex S to one of the sink-vertices T 1 or T 2 such that the worst-case traveling time is minimized. The following table gives the travel costs on the edges under different uncertainty regimes. Unless we impose a S T 1 [4,5]  cost on reducing uncertainty, U 0 is the inferior choice to make. Thus, one would either choose U 1 or U 2 as the uncertainty regime under which to operate and then choose only among those paths, that are optimal in the worst case which leaves us with only three choices described in below table.

Example 1. Consider the graph depicted in
The core realization is that, depending on the uncertainty set, the robustly optimal solutions vary substantially with respect to characteristics other than worst-case performance. In fact, in this example, the three robustly optimal decisions do not vary at all with respect to worst-case performance. A decision maker who only seeks to optimize the worst case behavior of the solution would be indifferent between the three choices. However, each of these choices can be clearly ranked with respect to maximum-regret, best-case performance and predictability, i.e. the range of possible outcomes.

Decision
worst-case perf. maximum-regret best-case perf. predictability Example 1 shows that for different uncertainty regimes, robust solutions to the shortest path problem may exhibit additional features beyond robustness, which may be considered when evaluating such choices. Specifically, under different uncertainty regimes the respective robustly optimal solutions differ with respect to the predictability of the outcome, the risk of experiencing regret in hindsight, and the best-case performance. We can also see that under some uncertainty regimes, a robust solution is not unique, and some of the robustly optimal choices may also exhibit said distinguishing features. We conceptualize the notion of uncertainty preference as the desire to operate under uncertainty regimes where there is a robustly optimal solution that performs well with respect to predictability, regret and/or best-case performance.
It is plausible that a decision maker faces this situation under various circumstances. Firstly, robustly optimal solutions may be similar across uncertainty regimes, yet still vary significantly with respect to other characteristics mentioned above. In this case a decision maker may wish to choose, among several nearly identical robustly optimal solutions, those that also incur additional advantages. Secondly, the decision on the uncertainty regime and on the solution to be implemented may be divided between two parties. This could take different forms: having a solution that is worst case optimal for the chosen uncertainty regime could be a requirement that is forced upon the decision maker, for example by company policy. In such a situation, a decision maker may still want to optimize other characteristics via their influence on the uncertainty regime and/or by picking a respective solution from the robustly optimal set. Further, in a setting similar to the classical leader-follower arrangement of bilevel optimization a decision maker who only has influence over the uncertainty regime may want to optimize their choice under the assumption that whoever is in control over the other decision variables will choose a robustly optimal solution.
We will tackle this phenomenon under two major paradigms, namely that of multi-objective optimization and that of bilevel optimization. Again we want to use examples to illustrate our reasoning.

Example 2.
A decision maker is tasked with an investment in public infrastructure such that in case of a natural disasters, important supply routes can be traversed confidently. The investment would reduce uncertainty in the travel time between two neuralgic points A and B that are connected through a network of roads, so that different paths exist between the two. There are not enough funds to fortify all roads. The decision maker knows that in case of an emergency the only acceptable travel route is the robustly optimal one. But at the same time they know that after the fact, their decision will be evaluated with the power of hindsight. In such a situation a decision maker may wish to take a decision on the investment in public infrastructure in such a way that the robustly optimal solution exhibits low risk of regret, such that it withstands the evaluation made in hindsight. Such a decision requires the anticipation of the robustly optimal solution present under the choice on the uncertainty regime that is to be made by the decision maker. Thus, we have a bilevel optimization problem. Example 3. In the above example, even if the decision maker does not bear the risk of unfair evaluation, there may be several robustly optimal solutions under the robustly optimal uncertainty regime, and a decision maker may want to optimize a secondary characteristics over the optimal set of the primary decision problem, or an appropriately chosen set containing the latter. This is a classical problem in multi-objective optimization and can be met by employing so called ε-constraints.
Following the ideas behind these examples, the goal of this paper is to provide models that capture uncertainty preference in a robust optimization problem, and to give examples where these models yield tractable optimization problems which can be handled with standard methods such as conic mixed-integer optimization.

Contribution and organization of this paper
We introduce the notion of uncertainty preference, which accounts for the fact that robustly optimal solutions obtained under different uncertainty regimes may have secondary, yet relevant characteristics (see Subsection 1.2) and formulate two mathematical models that capture the respective optimization problem: a multi-objective optimization model involving ε-constraints and a bilevel optimization model (see Subsection 2.1).
In case the nominal problem is a linear optimization problem, we characterize the set of robustly optimal solutions based on robust optimization duality theory. The resulting reformulation of the bilevel optimization problem is amenable to standard C-MILP solvers. In case the nominal problem is a MILP, we give a finite reformulation of the bilevel optimization problem with a potentially exponential number of constraints. These reformulations can be tackled using lazy constraints in conjunction with C-MILP solvers. These topics are discussed in Sections 2.2 and 2.3.
In Section 3, we describe the objective function terms that capture preferences for predictability, max-regret and best-case performance. Except for predictability, these formulations are in general not easy to handle. We highlight some special cases where we can achieve reformulations or approximations that can be solved with reasonable effort using C-MILP solvers. We apply our framework in Section 4 to the shortest path problem under endogenous uncertainty, which was considered before in [18] and will serve as an extensive illustration of our framework. Numerical experiments are performed in Section 5 basically as a proof of concept. We demonstrate that the proposed reformulations are handled well by C-MILP solvers in interesting and relevant cases, that the results obtained are meaningful and hopefully can aid a decision process.
We want to highlight that we decided, in agreement with the editor, to relegate some additional auxiliary material to an appendix, which can be found in the extended technical report on Arxiv. A short discussion on the generalization of the theory discussed in Section 4 to other network flow problems is presented in Appendix A. Furthermore, to give an alternative account of the applicability of our framework, in Appendix B, where we address a classical example from [6], the knapsack problem under endogenous Γ-uncertainty. For readers who are not familiar with standard robust optimization techniques we put the otherwise trivial proof of Theorem 6 in Appendix C. Some open questions are also briefly discussed in Appendix D.

Notation and preliminaries
In the sequel, matrices are denoted by sans-serif capital letters (e.g. the n × n-identity matrix will be denoted by I n and O will be the zero matrix), vectors by boldface lower case letters (for example e i will denote the i-th column of I n , o will denote the zero vector, and e the vector of all ones) and scalars (real numbers) by lower case letters. The i-th entry of a vector x will be denoted by x i . Matrices and vectors, and matrices and numbers with double indices are treated analogously. That is, for a matrix X, the i-th column or row vector (usage will be pointed out in context) is denoted by x i , and the j-th entry in the i-th row will by given x ij . If the original vector already has an index, that index will be pushed into the exponent for the lower case symbol that denotes an entry, e.g. the i-th entry of δ j is denoted by δ j i . Sets will be denoted using calligraphic letters, e.g., cones will often be denoted by K and uncertainty sets by U. The only exception is the set [1 : k] := {1, . . . , k}, and the function M(., .), which is explained later in the text and which we chose to highlight due to its significance.
Throughout the text, we will make use of conic linear optimization tools. A conic linear optimization problem is given by which is just a linear optimization problem with an extra constraint that restricts the decision variable x to lie in a closed, convex cone K. The dual problem is given by where K * := x ∈ R n : y T x ≥ 0 all y ∈ K is the dual cone of K. Slater's condition says that a relative interior feasible point of (P) guarantees p * = d * and existence of an optimal solution to (D) if it is feasible, and likewise with (D) and (P) in reversed roles. The gap between the two also vanishes if K is polyhedral and one of the problems is feasible.
A central object this paper is concerned with is the endogenously uncertain (mixed-integer) linear optimization problem, Here the problem data are affine functions of u, i.e. c(u) := c 0 + Cu, a i (u) := a 0 i + A i u and b i (u) : and X 0 ∈ R n + , R n 1 + × {0, 1} n 2 . Problem (1) describes a family of instances parametrized by u and s. The former is called the uncertainty parameter, which is not under the control of the decision maker who considers only those realizations of u which belong to certain uncertainty sets U s ⊆ R q . Here we assume that these sets consist of all realizations of u the decision maker need to take into account, according to their responsibility.
The uncertainty sets U s depend on the second parameter s ∈ [1 : S] which in fact is controlled by the decision maker, so that they can choose the uncertainty regime under which they would like to operate. The uncertainty is thus endogenous. Throughout the paper we will model uncertainty sets as compact, convex conic intersections, i.e. U s := u : (1, u) T ∈ K s where K s are appropriate closed, convex, pointed cones. Note that these assumptions, together with boundedness of U s entail the following implication: The construction of uncertainty sets is a well studied field and might be guided by different motivations. The most basic approach is to construct them in a way that guarantees that the robustified constraint is not violated with a certain probability (see [10,Section 3] and references therein). However, other authors have discussed construction schemes based on other principles such as reformulating optimization problems involving certain risk measure (see e.g. [5]). In the endogenously robust setting, [18] give a detailed account on how uncertainty sets can be influenced by the decision maker and how to model these situations. We want to point out that it may not make sense to talk about predictability, max-regret, or best case performance over an uncertainty set that is constructed based on reformulating an optimization problem involving risk measures. These characteristics only make sense if the uncertainty set can be interpreted as a subset of the possible realizations of the uncertain process. We further comment on this issue in the final section of the appendix.
We will employ several concepts associated with (1), namely: row/column wise uncertainty, the nominal problem, robust/optimistic/deterministic counterparts as well as C-MILP reformulations of those. We refer to [2,3,18,21,29,30] for some background on these concepts. Frequently, for example in case of row-and column-wise uncertainty, the uncertainty set will be a Cartesian product of sets U s = U s 1 × · · · × U s k . The factors of such products are likewise modeled as conic intersections with cones K s i , i ∈ [1 : k].

Remark 2.
The choices on x and s a decision maker takes may be entangled in a way that a decision on x limits the options on s (see [21] for examples). Such a situation can always be modeled via constraints of the form However, for the sake of notational simplicity, we will omit these constraints from the models discussed below. Also, in some applications it will be practical to push the dependence on s into the functions c(u), a i (u) and b i (u) while keeping the uncertainty sets constant (see Section 4).

The model 2.1 Endogenous uncertainty
In the case of endogenous uncertainty a decision maker has some level of influence over the shape of the uncertainty set. So they can choose the uncertainty regime under which they would like to operate. For linear and mixed-integer linear optimization problems under endogenous uncertainty, the mathematical model is thus given by inf s∈ [1:S] (ϕ s + γ s ), where Under uncertainty regime s, the term sup u 0 ∈U s 0 c(u 0 ) T x captures the worst-case performance of a solution x ∈ X 0 , and ϕ s is the optimal value of the robust counterpart to (1). The cost of activating uncertainty regime s is given by γ s , which is thus a function of s. C-MILP reformulations of inf s∈ [1:S] ϕ s + γ s have been studied in [18,21]. We define the set of optimal solutions to this problem to be R s opt := x ∈ R n + : x is an optimal solution to (RC-s) We will discuss in Subsection 2.2 how to work with the constraint x ∈ R s opt . Following the ideas conveyed in Example 2 and Example 3, we will now introduce two models in the focus of this text.

A multi-objective optimization approach via ε-constraints
One phenomenon arises quite frequently in the endogenously uncertain settin: the different choices on the uncertainty regime and, subsequently, on the decision variables may perform similar with respect the worst case criterion, but may vary greatly with respect to other characteristics. Multi-objective optimization is the standard paradigm under which we consider problems where more than one characteristics of a solution is to be optimized. In this setting, the objective function is a vector of the respective characteristics of a solution. Ordering cones are used to establish a type of dominance between different solutions. However, we wish to focus on the robust optimization perspective. Hence, we want to look for (nearly) robustly optimal solutions that optimize secondary characteristics. To this end we use the concept of ε-constraints which is well known in the multiobjective optimization literature (see e.g. [8]) . The respective model is given by: Here, ϕ * is the optimal value of the endogenously robust counterpart, gross of the activation cost of the robustly optimal uncertainty regime, and ε ≥ 0 is a degree two which we allow our solution to deviate from that optimal value. The function M(x, s) gives a measure of the performance of a solution (x, s) with respect to predictability, max-regret and best-case performance. This function influences the decision in two ways: firstly, which uncertainty regime is implemented and secondly, which robustly optimal solution is chosen in case the selected uncertainty regime allows for multiple robustly optimal solutions. We will explore different choices for M(x, s) and study their reformulations in Section 3. But first we will introduce an alternative model that is applicable to bilevel optimization setting.

A bilevel optimization approach
Following the idea illustrated in Example 2, we consider a leader-follower situation where the leader has control over the uncertainty regime and wants to optimize their preferred attribute under the assumption that the follower will implement the robustly optimal solution under the chosen uncertainty regime. Thus, in the leader's optimization problem, we need to guarantee that we only consider robustly optimal solution under the uncertainty regime of choice for the decision variable x controlled by the follower. Thus we want to solve Note that (UPP) is feasible if and only if there is at least one s ∈ [1 : S] such that (RC-s) is feasible and attains its optimal value. Here α is a weight given to the robustified objective value. We would like to point out that our model assumes a cooperative relationship between leader and follower. In fact, for any fixed uncertainty regime the set of robustly optimal solutions may not be a singleton, and our model will select among these solutions the one optimizing the objective. However, an adversarial follower might not choose this solution once the leader implemented their preferred uncertainty regime. Example 2 depicts a situation where the assumption of a cooperative follower is justified. Modelling an adversarial follower is a more challenging task, which we will comment on in in the appendix.

The robustly optimal set R s opt
The feasible set of the decision vector x is given by R s opt , i.e. the set of solutions that are robustly optimal under the uncertainty regime indexed by s. Hence, we have to solve a bilevel optimization problem. This class of problems is known to be challenging, in fact it is strongly NP-hard, as shown in [13]. Even if the optimal set of a lower level problem can be characterized, its parametrization via the top-level decision may lead to problem formulations that are not easily handled due to arising bilinear terms. Luckily, the top-level decision on s is discrete, so that these bilinearities can be exactly linearized by using McCormick envelopes [20]. Thus, the characterization of the robustly optimal set for a fixed choice of s is the main issue, which we will address in the sequel here. For cases where X 0 = R n + we will use robust duality theory in order to characterize R s opt . In case of X 0 = R n 1 + × {0, 1} n 2 , this theory does unfortunately not apply, so we provide alternative ways for these cases.
Let us first deal with the case when X 0 = R n + . In recent literature many aspects of duality in robust optimization have been studied (see [2,29]). While the deterministic counterpart of a robust optimization problem, as a convex problem, enjoys rich duality theory, a somewhat surprising observation first made in [2] is that, under mild assumptions, the dual of the robust counterpart of an uncertain linear optimization problem can be identified as the optimistic counterpart of the dual of that optimization problem (where the dualization is with respect to x). Hence the phrase "primal worst equals dual best" was coined in [2]. In case of (RC-s) the corresponding "dual best" problem is given by We have the following result [2, Theorem 3.1]: The problem (4) and the Lagrangian dual of (RC-s) are equivalent.
Note that (RC-s) is convex in x as the inner suprema are convex functions in x. Its deterministic counterpart is obtained by merely finding explicit forms of those functions (a standard procedure in robust optimization). Thus, the dual of (RC-s) is in fact given by the dual of deterministic counterpart, and any condition for this deterministic counterpart to exhibit strong duality also implies strong duality between (RC-s) and (4).

Corollary 1. Assume that strong duality holds between (RC-s) and (4) and that both problems attain their optimal value. Then the optimal primal-dual pairs
These relations therefore characterize R s opt .
Proof. The proof is immediate from Theorem 1.
The inequalities in the above corollary may seem difficult, but we have to bear in mind that all of these have convex reformulations. Minding the discussion succeeding Theorem 1 we can see that the assumptions in Corollary 1 can be guaranteed under well known conditions for full strong duality from convex duality theory.
Let us highlight at this point that not all optimistic counterparts are duals of robust counterparts as defined here. In fact, the structural aspect of (4) which allows for duality (and, thus, a convex reformulation) is that the uncertainty is column-wise (see [29,Theorem 1]). This fact will allow us to reformulate certain models involving max-regret in Subsection 3.1 below.

Finite reformulations for mixed-integer problems
We now consider the case where X 0 = R n 1 + × {0, 1} n 2 so that (RC-s) is a mixed-integer robust optimization problem. In this case, robust duality theory does not apply. However, it is still possible to give a finite reformulation of (UPP) with possibly exponentially many constraints which can be tackled via cutting plane algorithms, especially by using lazy constraints in a branch and bound algorithm. The following theorem is easily checked:

then (x, s) is feasible for (UPP) if and only if the following constraints hold:
where M j are upper bounds for ϕ max − ϕ j , all j ∈ [1 : S] with ϕ max := sup s∈ [1:S] ϕ s , while ϕ j is the optimal value of (RC-s) under uncertainty regime s = j and r j is defined as in (3). Proof. Let (x, s) be feasible for (UPP), then s ∈ [1 : S] and x ∈ R s opt so that it fulfills the last two constraints of (5). Further, by this fact, we have sup (5). For the converse, assume (x, s) is feasible for (5) so that all but the s-th constraint are redundant and by definition and by feasibility we have Finding appropriate M j for all j ∈ [1 : S] can be challenging. At least ϕ j can simply be computed by solving a robust optimization problem, that has to be computed anyway whenever one of the constraints from the first group in Theorem 2 is added. However, ϕ max is the more challenging entity. One way to derive an upper bound would be to solve sup s∈[1:S]φs whereφ s is obtained by changing the outer infimum in ϕ s to a supremum. The resulting problem is a mixed integer bilinear problem that can be exactly reformulated as a mixed integer linear problem, which in turn can be solved using the respective standard solvers. In Appendix B we discuss an example where a cheaper bound is derived easily. However, if (RC-s) is such that the uncertainty in the constraints does not depend on s, we can achieve a general reformulation that does not require a big-M. Note that this covers the case where there is no uncertainty in the constraints.
Proof. Assume (x, s) is feasible for (UPP), then x ∈ R s opt so that it fulfills the last constraint of (6). Also by this fact we have that where the first inequality holds since x is feasible for ϕ s and the second holds by feasibility for (6). So that indeed x ∈ R s opt , and (x, s) is feasible for (UPP).

Modeling uncertainty preference
In this section we will discuss different choices for M(x, s) and various reformulations of the resulting optimization problems. The goal is to have exact reformulations or at least good relaxations that are amendable to various, general off-the-shelf solution techniques such as mixed-integer linear and conic optimization. For some of the models, row-wise uncertainty can be assumed without loss of generality, while in others that is not generally possible. We will point specifically, when this assumption can be made safely and when this is not the case.

Regret
We can think of situations where the ex-ante choice a decision maker would have made in hindsight heavily depends on the outcome of the uncertainty process, while in other situations, a worst-case robust choice is viable in cases other than the worst case. In the former situation, decision makers run the risk of regretting their decision and may prefer an uncertainty regime with low potential regret. The concept of regret is well studied in the robust optimization literature (see [17]). The min-max-regret approach has garnered much attention as an alternative concept to the min-max approach in robust optimization. However, our aim is not to optimize the maximum regret in an uncertain linear problem. Rather we seek a choice of the uncertainty regime such that the robustly optimal solution performs well with respect to its maximum regret.
Since a decision maker prefers uncertainty regimes with small possible regret, we now consider a model that introduces a cost for running the risk of high regret. For fixed s ∈ [1 : S] and x ∈ R s opt the worst-case regret associated with this solution is given by that is, the worst-case difference between the performance of x and the performance we could have achieved in hindsight. The regret function does not have an equivalent row-wise formulation based on the projection method, which is valid for the robust counterpart.
The model that accounts for the worst-case regret of the outcome of the uncertainty under a chosen uncertainty regime can be formulated as: (REG-UPP) Here, β(·) is a convex, non-decreasing function which introduces a cost on the regret associated with a chosen solution and ρ is an auxiliary epigraphical variable. Easy viable choices for β(·) are the identity and simple linear scalings, but more complicated choices are possible without leaving the realm of convex optimization. The last constraint, despite being convex, presents a major complication in general, although in special cases there are manageable reformulations and approximations. In the remainder of the section we discuss problems with appropriate special structure. In Subsection 4.2.1 we also use a reformulation from literature that is specific to the shortest path problem.

Exact reformulation in case of column-wise uncertainty
Note that the innermost supremum-problem in (REG-UPP) is the optimistic counterpart of the uncertain linear problem (plus an additional robust objective term), which in general can be a nonconvex problem but in special cases is in fact convex, by robust duality theory. Obviously, this is a useful circumstance for reformulating (REG-UPP), but caution must be taken since not every optimistic counterpart is the dual of a robust optimization problem (see e.g [2, Example 2.1, Remark 3.1]) and therefore convex. In fact, it was proved in [29, Theorem 1] that an optimistic counterpart of an uncertain linear optimization problem with column-wise uncertainty and non-negative decision vector has a convex feasible set, that is, regarding the decision variable x. Further, it was proved that such a problem is the dual of a robust counterpart of an uncertain linear optimization problem with row-wise uncertainty. Thus, in order for the minimization in the definition of ρ(x, s) to be the "dual best" of a robust linear optimization problem we need the following assumption on the underlying uncertain problem.
where b(u n+1 ) := b 0 + Bu n+1 . For the above formulation we assume that d1) either there is an x ∈ R n + such that there exist u i ∈ int (U s i ) , all i ∈ [1 : n + 1] so that the inequalities are fulfilled, where the int-operator can dropped if the set is polyhedral, or d2) problem (9), i.e. the dual of (7) in the robust duality sense, has a Slater point.
The following lemma provides a useful sufficient condition for Assumption 1 d1): Lemma 4. Consider the following condition on (7) We can generally assume that {o} ∈ int(U s ) since we can always shift the set and adapt the constant terms in a(u), c(u) and b(u) accordingly. Thus condition d') holds if the feasible set of the nominal problem has nonempty interior, which often is established more easily. The more restrictive condition is b), that is column-wise uncertainty. However, this case features prominently in literature and discussions on its relevance can be found in [29,30].
Note that the optimistic counterpart of (7) given by is precisely of the form (4) so that by [2, Theorem 3.1] we can close the duality gap between (8) and if regularity conditions are met (e.g. Slater's condition or polyhedrality). Mindful of this fact, we see that Assumption 1 suffices to prove the following theorem.
Proof. Recall the definition of the max-regret function: which under Assumption 1 reduces to We will first show equivalence between the above infimum and minding the fact that by assumption, is feasible for (11), we set w 0 i = y i and w i = y i u i for i ∈ [1 : n] to get an equivalent solution for (12). Conversely, assuming (w 0 , w 1 , . . . , w n , u n+1 ) is feasible for (12), we set y i = w 0 i and u i = w i w 0 i if w 0 i = 0 and u i = o otherwise to obtain an equivalent solution for (11) (here we use the fact that (2) holds by assumption). By the same construction, any feasible point in (11) with u i ∈ int (U s i ) translates to a Slater point in (12). So, in any case, by Assumption 1 d) we have strong duality with its dual given by This concludes the proof.
The final supremum problem in the above proof is actually the deterministic counterpart of the "primal worst" (9). Thus the above theorem actually rests on robust duality. Rather than referencing this in the proof, we chose to give a simplified, exhaustive proof, firstly for the readers' convenience and secondly to illustrate how Assumption 1 ties in with the final result.

Remark 3.
The necessity for the objective to be free from uncertainty stems from the fact that we require column-wise uncertainty in the max-regret function. The defining feature of column-wise uncertainty is that the i-th portion u i of the uncertainty vector only interacts with the i-th entry of the decision variable or never interacts with any portion of the decision vector. If we introduced uncertainty into the objective this would still hold for the robust counterpart and the optimistic counterpart but not for the max-regret function. Indeed we then would have where u i interacts with y i and stands alone in the product c i (u i )x i . For our relaxation this would mean that we would have to model the interaction between w i and u i in (12), since the latter variable would not disappear, and then find a convex reformulation for the resulting problem, a far more tedious task. This problem would persist even if we pushed the uncertainty into the constraints by means of an epigraphical variable.

RLT-based bounds
Reformulation-linearization techniques (RLTs) are a well developed field in nonlinear optimization originally introduced in [1]. The idea is to generate additional constraints by multiplying existing constraints with terms of the form i∈J 1 x i and i∈J 2 (1 − x i ) for some appropriately chosen J 1 , J 2 ⊆ [1 : n] and replace the nonlinear terms with lifted variables i.e. x i 1 ,...,in = x i 1 . . . x in . This way one can obtain relaxations of good quality and in some cases even tight reformulations. In [27] the authors proved that this strategy is capable of delivering hierarchies of LP-approximations for combinatorial optimization problems that eventually close the relaxation gap. However, the strategy can still be applied for more general problems, see [28] for a full account.
The usefulness of this approach for our purposes stems from the fact that, once a linear relaxation/reformulation is obtained, we can use LP duality in order to resolve the inner supremum defining the max-regret function and so obtain a finite reformulation. Speaking more formally, we construct a linear reformulation/relaxation with a representation of the form below and a respective dual sup The final inequality in (REG-UPP) can then be replaced by as to obtain an upper bound for the original problem, which can be tight in case the LP relaxation is exact.
Though the construction of higher order approximations can be tedious, we have at least one example where a fairly simple relaxation already yields satisfactory results. We will discuss this example in the sequel of this section. Later in Section 4 we will apply this relaxation, also we will demonstrate in Section 5 that, despite its simplicity, it can yield reasonable approximation quality.
Consider the uncertain binary linear problem The robust counterparts of uncertain MILPs in general do not enjoy strong duality and thus we not have an easy way to resolve the inner supremum problem in (REG-UPP) outside of special cases. In Section 4 we will study such cases, where the constraint matrix E ∈ R m×n is totally unimodular. For discussion in this section we will solely focus on deriving a tractable relaxation of the max-regret function of the uncertain MILP, but already entertain the total unimodularity assumption on E. We have The first equality holds due to the total unimodularity assumption an the fact that the objective is bilinear. The second one is easily established. We see, that the optimal solutions are contained in {0, 1} n+2q . First, we introduce additional constraints by multiplying the linear constraints with each of the uncertainty parameters, i.e. u i Ey = u i d, all i ∈ [1 : q]. We now lift the space of variables by replacing the bilinear terms u i y j with ψ ij and construct the McCormick envelope [20] by introducing the constraints The end result is a linear optimization problem the dual of which can be used to replace the inner supremum in (REG-UPP) as discussed above.

Predictability
We have constructed uncertainty regimes where the performance of the robust solution is more predictable than in others. This may be a desired property of a solution next to being robust, for example, if, after implementation of the solution, excess optimal value cannot be harnessed due to its unexpected realization (e.g. a delivery that arrives early and cannot be received). The desire to have a predictable outcome can also extend to the constraints. Being able to better estimate the resource consumption of an activity outside the worst case can be advantageous. Thus, a decision maker may prefer to operate under an uncertainty regime where the performance of the robust solution after implementation does not deviate from the robustly optimal value by too much, and where the resource consumption does not deviate too much across scenarios.
In order to have a predictable outcome, we need to reduce the gap between best-case and worst-case performance of a robust solution, arriving at the following model: Here, q i and q i are auxiliary epi-and hypographical variables, introduced for notational convenience only. The right-hand side suprema/infima are the worst-and best-case performances of a solution x under uncertainty regime s in terms of objective function value and in terms of resource consumption. Since the differences between worst-and best-case performances are independent across rows, we may assume row-wise uncertainty, in a way similar to the robust counterpart. Note that the suprema are convex functions in x, as they are point-wise suprema of linear functions. By the same token, the infima are concave in x. Thus, the respective constraints describe a convex set. The functions β i (q i , q i ) are convex functions that put a cost on the distance between worstand best-case performance of a feasible solution x. Next to convexity we assume A simple choice for β i would be β i := q i − q i and in our applications we will exclusively work with this choice. However, more complicated choices are possible since in any case we will end up with a mixed-integer convex optimization problem.

Theorem 6. Problem (PDA-UPP) is equivalent to the following mixed-integer conic optimization problem:
Proof. The proof relies on standard robust optimization arguments and is therefore relegated to the appendix.
From the above theorem we can see that (PDA-UPP) does not add much difficulty over solving (UPP) with M(x, s) removed.

Best-case performance
In Example 1 we see that there are choices on the uncertainty regime where the resulting robust solution exhibits good performance even in the best case. A decision maker may prefer uncertainty regimes where the conservatism inherent in the robust solution is redeemed by viable best-case performance of that solution. On the other hand, again applying this concept in terms of constraints, a decision maker may value the chance of saving resources in cases other than the worst case.
The model that can account for the best-case performance of the outcome of the uncertainty under a chosen uncertainty regime can be formulated as (using v instead of u to suggest that now uncertainty is not adverse): (BCP-UPP) The function β(.) is assumed to be convex and nondecreasing in each argument; in our applications in later sections it is chosen to be the sum of q i , all i ∈ [0 : m]. Note that we cannot assume row-wise uncertainty, since not all rows can necessarily attain their minimum simultaneously. We would thus underestimate the optimal q i , all i ∈ [0 : m], if we were to use the projection method, that is valid for the robust counterpart (see [3]). The problem (BCP-UPP) is a bilinear mixedinteger optimization problem and as such very challenging. In case X 0 = {0, 1} n 2 one can again use McCormick linearization in order to obtain a problem that is manageable using C-MILP solvers.
In case that all coefficients of x depend on independent portions of the uncertainty vector v one can pre-compute and replace the uncertain coefficients with their respective minima. In the next section we will discuss an application where both of these strategies are feasible.

Exact reformulation in case of column-wise uncertainty
Analogous to the max-regret function, the constraints in (BCP-UPP) can be reformulated exactly in case of column wise uncertainty. For the reformulation we do not need a duality argument so X 0 may be discrete. Also the structure of these "optimistic constraints" is simpler than the optimistic counterpart in the max-regret function, so that we can allow for uncertainty in the objective. Thus, compared to the case of max-regret, merely Assumption 1 b) is needed for the reformulation discussed shortly. Note that under the assumption of column-wise uncertainty we can write the epigraphical constraints in (BCP-UPP) as For the sake of notational simplicity we introducē We can then find vectorsā 0 i and matricesĀ i of appropriate size such thatā We are now ready to state the following theorem.

Theorem 7. Assume that Assumption 1 b) holds, so that (BCP-UPP) can be written as
Then this problem is equivalent to Proof. The proof is similar to that of Theorem 5.

The shortest path problem with endogenous arc-weight uncertainty
In the following section, we will apply our framework to the shortest path problem. As we will see, this problem can manifest in different special cases that will allow us to demonstrate the applications of both Corollary 1 and Theorem 3. We want to highlight the fact that he uncertain shortest path problem appears in pre-desaster network design, which has been previously discussed in the context of robust optimization with endogenous uncertainty (see [21]).
Whenever we present the full models we represent the bilevel and the ε-constraint model at the same time, by explicitly presenting the respective constraints for x ∈ R s opt , and in parentheses we present the ε-constraint. We will maintain this style also in the succeeding section.

The uncertain shortest path problem and its robust counterpart
Consider a directed, weighted graph G = (V, A) where V is the set of vertices and A the set of arcs. We denote by c i the arc weight of arc i. Vertex 1 is marked as source and vertex n is marked as sink. The shortest path problem (SPP) is the combinatorial optimization problem to find a path from the source to the sink such that the sum of the weights of the arcs crossed is minimized. It is well known that the SPP has an exact LP reformulation where each (directed) arc corresponds to a variable x k under some relabeling π(k) = (i, j) and In (R-SPP) integrality can not be relaxed in general, since the objective is no longer linear, but convex. It was proved in [7] that (R-SPP) under ellipsoidal uncertainty is in fact NP-hard, and [31] showed that NP-hardness for finitely generated uncertainty sets. One can formulate it as a conic MILP, but then we lose the duality needed for the characterization of R s opt . In special cases, however, the robust counterpart remains a linear optimization problem so that we can apply Corollary 1, in other cases we can still work with Theorem 3.
In the remainder of this section we discuss various reformulations and approximations of (UPP) for the uncertain SPP under different cases of box uncertainty. All the formulations will involve some interaction between terms in s and x, and since we can model these as bilinear terms between r and x where all these variables are binary and thus between zero and one, the big-M constant for the construction of the McCormick envelope is given by 1. Also we will, in this section, push the dependence on s from the uncertainty set into the description of the uncertain objective coefficients, hence we consider c s (u) while the uncertainty set will remain constant across s ∈ [1 : S].

SPP under structured box uncertainty
Define c s (u) := c 0 s + C s u with c 0 s ∈ R |A| + and C s ∈ R |A|×q , s ∈ [1 : S] and consider the following uncertainty set: U Box := {u ∈ R q : u ∞ ≤ 1} , with K = (v 0 , v) ∈ R m+1 : v ∞ ≤ v 0 and K * = (z 0 , z) ∈ R m+1 : z 1 ≤ z 0 . General box uncertainty can managed by employing Theorem 3. However, there are at least two cases where (R-SPP) under box uncertainty can be reformulated as a linear optimization problem.
Interval uncertainty: q = |A| and C = Diag(ĉ) is diagonal; by flipping u i → −u i if necessary, we can always assume that allĉ i ≥ 0. This is a special case of what we suggest to call Since max u ∞≤1 g T u = g 1 = e T g, with e ∈ R q the all-ones vector, holds for all g ∈ R q + and since g = C T s x ∈ R q + under our assumptions, we have, by total unimodularity, which is a linear optimization problem. It is interesting to note that in the uncorrelated interval case where C s = Diag(ĉ) with diagonal entriesĉ j ≥ 0 we have so the above linear optimization problem has the worst-case realizations per arc as its objective coefficients. Therefore in both of these cases (R-SPP) can be exactly linearized, and we can characterize the respective optimal set using strong linear duality. The reason why we split the presentation into two parts is a discrepancy in case of maximum-regret, as explained in Example 4 below.

SPP with interval uncertainty
In case of endogenous interval uncertainty, the travel time on an individual arc j is known to lie in an interval [c i s , c i s ] if uncertainty regime s is active. Thus the worst and best-case outcomes do not depend on x and are easily identified as the outcomes where the travel time is on the upper and lower bound respectively. Let s ∈ [1 : S] and define c s , and c s , to be the element-wise best-case, or worst-case realizations, respectively, of c(u) under uncertainty regime s. Following above logic, we arrive at a mixed-integer linear model for each of the uncertainty preferences: Here we used Corollary 1 in order to characterize R s opt . To accommodate the three different types of uncertainty preferences, we specify M(x, s) in the following ways (with the simplest choice corresponding to the specification β(q, q) = β(q − q) in (PDA-UPP), which can be generalized in a straightforward manner): The reformulation of the regret function was introduced in [16], where the concept of regret was presented under the name of maximum deviation robustness. The intuition is that, in case of interval uncertainty, the regret is maximized if the ex-post solution may only experience the best-case realization on all arcs except for those who are also crossed by the ex-ante solution.
We see that the problem can be solved exactly using MILP-solvers without any further adaptation. Thus, there is at least one setting where our framework can be applied in its entirety, while never leaving the realm of basic and well-developed optimization techniques.

SPP with correlated interval uncertainty
This type of uncertainty set allows us to model situations where the uncertainty across arcs is positively correlated which is irrelevant for the robust counterpart but impacts the optimistic counterpart es well as the max-regret function, because the optimistic optimizer present in both loses flexibility. In Example 4 we will demonstrate the difference between interval and correlated interval uncertainty.
For the uncertain travel times under uncertainty regime s given by c s (u) := c 0 s + C s u, let C s be non-negative. Then we have C T s x 1 = e T C T s x so that the objective in the robust counterpart has a linear objective and the LP relaxation is still exact. Thus we can again use LP-duality in order to characterize R s opt as follows: Again, M(x, s) can be specified in three different ways according to the respective uncertainty preferences: where b, A, and f are defined as described in Subsection 3.1.2. We further comment on the usefulness of this bound in Section 4.3 and Section 5.

Example 4.
For the best and worst-case calculation, and hence also for predictability, there is no difference between interval uncertainty and correlated interval uncertainty from a modeling standpoint. To see this, let C ∈ R n×m + and consider x T Diag (C T e) 1 , . . . , (C T e) n w .
However, there is a difference when it comes to calculating the maximum regret. To understand this difference, consider the graph depicted in Figure 2 and assume the traveling time on all the edges was known to be between 1 and 2. There are two paths from node 1 to node 4. Under interval uncertainty, regardless of the path chosen, the maximum regret would be 4 − 2 = 2, i.e. the worst case materializes on the path chosen, while the best case materializes for the alternative path. On the other hand, with correlated interval uncertainty we could model the situation with C = 0.5 e and U = {u : u ∈ [−1, 1]} and c 0 = 1.5 e. In this case the same outcome would have to occur on all four edges simultaneously and the maximum regret would always be 0.

SPP with general box uncertainty
If we have box uncertainty where C has negative entries or is not diagonal, the robust counterpart of the uncertainty does no longer have an exact linearization, so that a characterization of R s opt based on Corollary 1 is no longer possible, and hence Theorem 3 has to be invoked. With c s (u) given as above, (UPP) for the SPP with general box uncertainty can be cast as: where z j ∈ R j opt for all j ∈ [1 : S]. The respective specifications for M(x, s) are Since x and s are discrete, we can linearize the multilinear term in the infimum using iteratively McCormick envelopes. For the max-regret calculation we have to work again with the approximations described in Subsection 3.1. However, when we observe the max-regret function for uncertain SPP given by we see that we have a mixed-binary problem where the bilinear terms can be exactly linearized using McCormick envelopes. This allows us at least to easily test the quality of our proposed lower upper bound. The same is true for the regret in the correlated interval uncertainty model. We will report a respective evaluation in Section 5.
As stated above, the constraints enforcing x ∈ R s opt are derived using Theorem 3. The number of these constraints may be exponential (as discussed above) and each requires solving an optimization problem in order to determine the right-hand side. We circumvene these problems in our implementation by applying these constraints as lazy constraints. Thus, in our implementation described in the next section, the constraints are absent at first, and whenever the branch-and-bound solver encounters a feasible solution (x, s), it checks whether If this is not the case, we add the constraint to the model. This process proved to be quite efficient since the robust optimization problem on the right-hand side is a MILP that is quite easily tackled by modern solvers.

Numerical experiments
In this section we will conduct some numerical experiments, where we will apply the concepts introduced in this text to the shortest path problem. We will demonstrate that we can use general MILP solvers in order to solve (UPP) in this setting for interval uncertainty and general box uncertainty. Also we will investigate the trade-off between the different uncertainty preferences and worst-case performance. All instances were solved using Gurobi [12], and the implementation was done in Python [23] and Matlab. The experiments were run using an AMD Ryzen 7 1700X Eight-Core 3.4 GHz CPU, and 16 GB RAM.

The ε-constraint model for the SPP
In this set of experiments we exemplify the use of the ε-constraint model when applied to the uncertain shortest path model under interval uncertainty. To this end, we created 10 instances of these problems by generating networks of size |V| = 150, where nodes i and j where connected with 50% probability if the indexes of the nodes where no further apart than 10 and with probability equal to zero otherwise. For each instances we created S = 10 uncertainty sets by generating uncertainty arc-weights where the lower bound were drawn at random uniformly from the interval [8,10] and upper bounds were drawn from the interval [10,12]. For each instance we solved the endogenously robust counterpart in order to obtain ϕ * . Replacing M(x, s) with the respective terms for predictability, best-case performance and regret one at a time, we resolved each instance allowing for an ε violation of the optimality constraint where ε ∈ {1%, 2%, . . . , 10%}. The blue line in the graphs of Figure 3 depicts the change of the optimal solutions predictability, best-case performance and max regret with ε, while the orange line depicts the change of the solutions worst case performance. The values were normalized by their range across different values of ε and averaged across all 10 instances.
We see that in our experiments on average, allowing for a 1% deviation from the optimal value earned a 50% gain in predictability relative to the performance of the robustly optimal solution. A Figure 3: Trade-off between the secondary characteristics and robustly optimal value. similar outcome is observed when optimizing best-case performance, albeit at a larger sacrifice of worst case performance relative to the range. With regard to regret, the trade-off was even more pronounced. We also report the run time for these experiments in Table 1 Of course the results above cannot be generalized and depending on the instances at hand one could face much more favourable trade-offs. However, these instances at least demonstrate that such favourable trade-offs where small deviations from robust optimality allow for substantial gains in the secondary objective are possible. This also demonstrates how our theory can be applied in practice, as it gives decision makers an idea of how much of protection against worst case performance they have to sacrifice, in order to make a meaningful difference with respect to predictability, best-case performance, or regret.

The bilevel model for the SPP
For these experiments we considered the uncertain SPP under two types of endogenous box uncertainty: interval uncertainty and general box uncertainty. For both types we want to illustrate the trade-off between different contributors of the objective function of (UPP), namely worst-case performance, predictability, maximum regret and best-case performance. We compared the tradeoff between two of these at a time so that in total 6 comparisons were made for both types of uncertainty models. The attributes not considered were dropped from the objective function, while the two that were considered had randomly chosen multipliers from the unit box. We probed 14 random coefficients per instance and generated 20 instances per pair of attributes so that in total we solved 280 problems per pair. The size of the instances was |V| = 300, S = 10 for the interval uncertainty model and |V| = 50, S = 10, q = 10 for the general uncertainty model. Arcs between nodes were established randomly, where an arc between nodes i and j was created if a uniformly distributed random number from the interval [0, 1] was smaller than 0.3/|i − j|. For the general box uncertainty we used the upper bound from Subsection 3.1 for the computation of regret. However, for each solution (x, s) we obtained, we also calculated ρ(x, s) exactly and compared that value to the value from the upper bound. In 1678 of 1680 cases the bound was in fact tight, indicating that it worked reasonably well for problems of the size considered here. In our experience the quality of the bound diminishes as |V| and |A| grow but for medium size problems it is quite acceptable.
We summarize the results in Table 2 and Table 3. The tables report the average computation time in seconds (T ) as well as the range of computation times ([T min , T max ]). The column (#T O) gives a measure of how intensive the trade-off between different attributes has been in our experiments. It reports the number of instances for which the value of the compared attributes changed with different objective function coefficients. The columns (∆ 1 %) and (∆ 2 %) give the percentage difference between the maximum and the minimum value of the first and second attribute within an instance, averaged over all 20 instances.
Further, Figure 4 and Figure 5 illustrate what can be thought of as combined, normalized efficiency frontiers. For every problem solved, we normalized the outcome of the attributes on a scale between 0 and 1 using the formula a % = (a − a min )/(a max − a min ), where a min and a max are the minimum and the maximum the attribute attained in that instance over all 14 probings, and a is the unnormalized value of that attribute in the current problem. After normalizing one can plot the 14 pairs of outcomes for the two attributes being compared in a scatter plot. What is depicted in the figures is the combination of all of these plots per pair. We only included those instances where there was a trade-off between the two attributes.
We summarize the key takeaways from our experiments as follows: Due to the proposed formulations, even the most demanding model with general box uncertainty is manageable using standard software. Solutions were mostly obtained in a matter of minutes. Trade-offs between two attributes were encountered regularly, indicating that different uncertainty preferences have a notable impact on the decision. In instances where there was a trade-off, outcomes of the attributes could vary substantially across the 14 probings.
Our experiments also demonstrate how the bilevel model can be used in practice. The top level decision maker (who controls the uncertainty set) could base their decision on efficiency frontiers displaying the trade-off between different attributes across the different robustly optimal sets and implement the uncertainty regime that optimizes that trade-off.

Conclusion
We have introduced a two models, based on multi-objective optimization and bilevel optimization, for optimization under endogenous uncertainty that capture uncertainty preferences of a decision maker, where the aim is to choose an uncertainty regime such that the robustly optimal solutions under said regime exhibits preferred qualities with respect to predictability, maximum regret and best-case performance. Along with introducing the -apparently novel -models, we  Proof of Theorem 8.
The second equality stems from the fact that for any x, y ∈ {0, 1} |A| we have where I j = {i : x i = j} , j = 0, 1. The third equality is justified since it is optimal to make the constraints as loose as possible, the forth stems from the fact that E is totally unimodular and b is integer and, finally, the fifth equality holds by linear programming duality.

B Knapsack problems with endogenous Γ-uncertainty
In this section we will apply our framework to the knapsack problem with Γ-uncertainty which is a classical example from [6]. In this setting, we want to maximize the utility of packed items under the constraint that their joint weight must not surpass a certain threshold. Let c ∈ R n be the vector of utilities of the n items, and let a ∈ R n their weight, then the knapsack problem is given by max x∈{0,1} n c T x : a T x ≤ b . As in [6] we assume that the weights of the individual items are uncertain, where the number of items whose wight deviates from the nominal value a 0 ∈ R n is restricted by the parameter Γ ∈ N. Denoting the maximum amount of deviation of item i byā i , i ∈ [1 : S] our assumptions so far may be formalized as (a(u)) i := a 0 i +ā i u i where u ∈ U Γ := {u : n i=1 u i = Γ, u ∈ [0, 1] n }. However, we make the additional assumption that we can influence the vector of maximum deviations by makeing a choice on the uncertainty regime, that is we can chose betweenā s ∈ R n , i ∈ [1 : S]. Under these assumptions, the knapsack problem under endogenous Γ-uncertainty is given by while the endogenously robust counterpart is given by max x∈{0,1} n , s∈ [1:S] c T x : a T x + max Following the standard reformulation strategy from [6] we arrive at the deterministic counterpart given by max x,λ,δ,s Again we pushed the dependence on s into the coefficientsā s i and the bilinear terms arising from a s i x i = S j=1ā j i r s j x i can be linearized exactly via McCormick envelopes where the arising big-M constants are equal to one.
When applying the bilevel optimization framework from Section 2.1.2 we have to resort to Theorem 2 for the characterization of R s opt since we have a combinatorial problem with endogenously uncertain constraints. This raises the question of how to construct M j , j ∈ [1 : S], for the respective constraint from (5). In case of the endogenously uncertain knapsack problem this constraint is given by where we had to flip the inequality since we are now dealing with a maximization problem and we need M j , j ∈ [1 : S] to be a upper bound on ϕ min − ϕ j , j ∈ [1 : S] with ϕ min := min j∈[1:S] ϕ j . Although we discussed a general scheme for constructing these constants in Section 2.1.2, we can use special structure to obtain cheaper bounds on ϕ min −ϕ j , j ∈ [1 : S]. Note that M j must be such that the constraint becomes redundant whenever r s j = 0. This is achieved by choosing M j = ϕ j since zero is a trivial lower bound for the objective of the knapsack problem. It is therefore not necessary to pre-calculate ϕ min , but one also has to take into account that the weaker bound will result in weaker relaxations at each node of a branch and bound procedure which may adversely affect the run times of these algorithms.
We will now proceed to discuss the various specifications of M(x, s) for the different types of uncertainty preferences and comment on some of the special issues to be considered when working with these models.

B.1 Regret
As discussed in Section 3.1.2 we can always find exact linearizations of the max-regret function at the cost of introducing an exponential number of variables. For the sake of simplicity we will limit our discussion to a compact linearization based on relaxing the McCormick reformulation and dualization of the latter. The detailed steps are outlined in the following theorem: Assume that there is a value for the uncertain parameter such that the knapsack problem under endogenous Γ-uncertainty is feasible. Then, the max-regret function can be upper bounded in the following way ∆b > 0 such that still b+∆b < a 1 . We can reorder indices j such that c 1 a 1 ≥ c j a j for all j ∈ [1 : n]. Then the last maximization problem in (16) has as a feasible solution y = b a 1 e 1 , z = n j=n−Γ e j , u = o, with objective function value bc 1 a 1 . The problem max y≥0 c T y : a T y ≤ b = bc 1 a 1 is a relaxation, hence the aforementioned feasible solution is actually optimal. Replacing b by b + ∆b does not change above construction whenever the right-hand side b + ∆b stays between zero and a 1 . Therefore the dual solution stays the same, as it is feasible for both variants, and complementary slackness continues to hold (only y 1 changes and the new constraint a T y ≤ b + ∆b is again binding at y). Thus, for the optimal choice µ * , the difference of dual optimal values (by strong duality, equalling the difference of the primal-optimal values) is a 1 ). We will now show that this gives an upper bound for all other values b ≥ a 1 . The reasoning is that the dual price of a resource can only decrease when it becomes more abundant. To see this, consider two generic duals min (µ;μ)≥o b i µ +b Tμ : aµ + Bμ ≥ c for i = 1, 2 with b 1 < b 2 , and their respective optimal solutions (µ * 1 ,μ * 1 ) and (µ * 2 ,μ * 2 ). Assume that µ * 2 > µ * 1 . Since both solutions are feasible for either This yields the final contradiction b 1 µ * 1 +b Tμ * 1 > b 1 µ * 2 +b Tμ * 2 , which establishes the claim.

B.2 Predictability
In contrast to the shortest path problem, we now consider predictability not with respect to the objective function value, but with respect to resource consumption, so we want to optimize the difference between the maximum and the minimum resource consumption of our solution, across all realizations of the uncertainty parameter. It is clear that Theorem 6 is general enough as to cover the knapsack problem with endogenously uncertainty constraints. Still, we want to give a brief presentation of the derivation and the final result for the special case for the readers' convenience. Again making use of the equality max g T z : e T z = Γ, z ≤ e, z ∈ R n + = min λΓ + δ T e : λe + δ ≥ g, λ ∈ R, δ ≥ o we arrive at max x,s,q,q,λ,λ,δ,δ γ s + αc T x − β(q, q) s.t. : q ≥ a T x + λΓ + δ T e , λ + δ i ≥ā s 1 x i , i ∈ [1 : n] , q ≤ a T x + λΓ + δ T e , λ + δ i ≤ā s 1 x i , i ∈ [1 : n] , x ∈ R s opt , s ∈ [1 : S] , δ ≥ o, δ ≤ o, λ, λ ∈ R , c T x ≤ ϕ * + ε , which, besides the linearization ofā s 1 x i we discussed previously, needs no further reformulation.

B.3 Best-case performance
Again it is the best-case performance with respect to resource consumption rather than objective function value, as only the former and not the latter depends on the uncertainty parameter. The model we want to solve is thus max x,s,q γ s + αc T x + β(q) where the inner max-operator can be dropped due to the direction of the inequality, and the multilinear terms u iā s i x i can be exactly realized using McCormick envelopes where the arising big-M constants are all equal to 1.

B.4 Numerical experiments: bilevel model for uncertain knapsack problems
For the uncertain knapsack problem we set up an experiment analogous to the SPP setting and generated instances of this problem with n = 100, Γ = 10, b = 12 and S = 10. The vector of utilities c and the vector of of nominal weights a were created randomly, where each entry was drawn from the interval [1,2]. The entries of the vectors of perturbationā s , i ∈ [1 : S], were uniformly drawn from [1,5].
We want to stress that we chose above parameters for generating the instances deliberately, to ensure strong effects of different uncertainty preferences in the objective for a small number of uncertainty regimes. In any case it should be clear that results from random instances can not be generalized to real world instances in a straightforward way, in particular when S is larger. We will shortly discuss which conclusions can be drawn safely from our experiments.
For the formulation of the bilevel optimization problem we followed the discussion in Appendix B, i.e. we used Theorem 2 for the characterization of R s opt , where we used lazy cuts in order to add the respective constraints as necessary. The rest of the setup was analogous to the experiments in the preceding section.
Again we see from the scatter plots in Figure 6 that, at least in our instances, when optimizing over R s opt there is a trade-off to be made between the different attributes we were considering. Thus, in a bilevel-setting, a leader may exert meaningful influence over the decision of the second-stage    Table 4, where we observe varying degrees of trade-off between the different attributes. We want to highlight that we were able to solve the instances in seconds.

C Appendix: proof of Theorem 6
Proof of Theorem 6. The proof follows immediately from standard arguments based on convex duality that are well known in robust optimization. For the readers' convenience we present the key idea in the notation used here. First, by invoking convex duality we have Here strong duality holds, since we assumed that the uncertainty sets have nonempty interior and thus Slater's condition holds. We thus have the equivalence sup u∈U d T u + d 0 ≤ 0 ⇔ d 0 + ρ ≤ 0 and (ρ, −d) T ∈ K * .
The reformulation follows by using this equivalence with d replaced by x T A i − b T i and x T C respectively. For the infima the analogous procedure holds. Also, we eliminated the epi-and hypographical variables q i and q i , all i ∈ [0 : m].

D Appendix: open questions and outlook
Despite the exhaustive discussion of our framework, we feel that there are still many interesting open questions left. We wish to use this section to give a brief account of what we consider to be interesting directions for future research.
In our discussions on different choices for M(x, s), we introduced convex functions β(.) and β i (.), but settled for very simple choices of those functions in our applications. Obviously other choices would be viable from a computational standpoint, but the question is whether there are meaningful choices that can be justified based upon the decision makers' preferences.
Throughout the paper we assumed that the uncertainty set contains the realizations of the uncertainty parameter for which the decision maker takes responsibility. However, this is not always how we construct uncertainty sets. In literature we find constructions of uncertainty sets that are aimed at at providing an equivalent reformulation for optimization of a risk measure. It does not to make sense to optimize predictability, best-case performance or max-regret over such uncertainty sets. However, the overall philosophy of using the flexibility of the endogenously uncertain setting in order to optimize secondary characteristics related to the uncertainty process might still be applied in these cases, but some extra effort must be made in order to transform assumptions on the uncertainty into meaningful secondary attributes. What these attributes might be and, how they can and should influence the decision is a question that in our opinion is an interesting direction for future research.
In the bilevel optimization model we assumed a cooperative relationship between the leader and the follower, however, in practice this might not be necessarily the case. An alternative approach would be to assume an adversarial relationship where the follower chooses the robustly optimal solution that works against the preference of the leader. We deem such a model an interesting topic for future research.
Some of the appeal of robust optimization stems from the fact that many robust counterparts can be solved using standard optimization solvers. One of our goals was to show that this is at least partly true for our framework. However, in order to have broader range of possible applications and also to have better performance of the solution process, it would be worthwhile to investigate specialized algorithms that are able to solve (UPP) in specified settings.
We hope we can address these points in future research.