# Uncertainty Preferences in Robust Mixed-Integer
Linear Optimization with Endogenous Uncertainty ††thanks: Supported by the
Austrian Science Fund (project DK W 1260-N35).

Immanuel Bomze  ISOR/VCOR/VGSCO and ds:univie, University of Vienna, Austria.
<EMAIL_ADDRESS>
+43-1-4277-[38652|838672] Markus Gabl  ISOR/VCOR/VGSCO and ds:univie,
University of Vienna, Austria<EMAIL_ADDRESS>
+43-1-4277-[38652|838672]

###### Abstract

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 they are 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 those 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 introduce a multi-
objective optimization based and a bilevel optimization based model that
integrate these preferences in a meaningful way. Further, 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.

Keywords: Robust optimization $\cdot$ Discrete Optimization $\cdot$ Endogenous
Uncertainty $\cdot$ Risk Aversion

##  1 Introduction

###  1.1 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.

###  1.2 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.

######  Example 1.

Consider the graph depicted in 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 ${\mathcal{U}}_{0}$, the one where uncertainty is
affected on paths towards $T_{i}$ is referred to as ${\mathcal{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.

$S$$T_{1}$$T_{2}$$E_{2}$$E_{1}$$E_{3}$

Edge | ${\mathcal{U}}_{0}$ | ${\mathcal{U}}_{1}$ | ${\mathcal{U}}_{2}$
---|---|---|---
$E_{1}$ | [4,5] | [3,4] | [2,5]
$E_{2}$ | [4,5] | [2,4] | [2,5]
$E_{3}$ | [4,5] | [3,5] | [1,4]

Figure 1:

Unless we impose a cost on reducing uncertainty, ${\mathcal{U}}_{0}$ is the
inferior choice to make. Thus, one would either choose ${\mathcal{U}}_{1}$ or
${\mathcal{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.

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
---|---|---|---|---
traverse $E_{1}$ under ${\mathcal{U}}_{1}$ | 4 | 2 | 3 | 1
traverse $E_{2}$ under ${\mathcal{U}}_{1}$ | 4 | 1 | 2 | 2
traverse $E_{3}$ under ${\mathcal{U}}_{2}$ | 4 | 3 | 1 | 3

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 $\varepsilon$-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.

###  1.3 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
$\varepsilon$-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
$\Gamma$-uncertainty. For readers who are not familiar with standard robust
optimization techniques we put the otherwise trivial proof of 6 in Appendix C.
Some open questions are also briefly discussed in Appendix D.

###  1.4 Notation and preliminaries

In the sequel, matrices are denoted by sans-serif capital letters (e.g. the
$n\times n$-identity matrix will be denoted by ${\mathsf{I}}_{n}$ and
${\mathsf{O}}$ will be the zero matrix), vectors by boldface lower case
letters (for example $\mathbf{e}_{i}$ will denote the $i$-th column of
${\mathsf{I}}_{n}$, $\mathbf{o}$ will denote the zero vector, and $\mathbf{e}$
the vector of all ones) and scalars (real numbers) by lower case letters. The
$i$-th entry of a vector $\mathbf{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 ${\mathsf{X}}$, the $i$-th column or row vector (usage
will be pointed out in context) is denoted by $\mathbf{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 $\bm{\delta}_{j}$ is
denoted by $\delta^{j}_{i}$. Sets will be denoted using calligraphic letters,
e.g., cones will often be denoted by ${\mathcal{K}}$ and uncertainty sets by
${\mathcal{U}}$. The only exception is the set
$[1\\!:\\!k]\coloneqq\left\\{1,\dots,k\right\\}$, and the function
${\mathcal{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

$\displaystyle
p^{*}=\inf_{\mathbf{x}}\left\\{\langle\mathbf{c},\mathbf{x}\rangle\colon\mathbf{x}\in{\mathcal{K}},\
\langle\mathbf{a}_{i},\mathbf{x}\rangle=b_{i}\,,\mbox{ all
}i\in[1\\!:\\!m]\right\\}\,,$ (P)

which is just a linear optimization problem with an extra constraint that
restricts the decision variable $\mathbf{x}$ to lie in a closed, convex cone
${\mathcal{K}}$. The dual problem is given by

$\displaystyle
d^{*}=\sup_{\bm{\lambda}}\left\\{\sum_{i=1}^{m}\lambda_{i}b_{i}\colon\bm{\lambda}\in\mathbb{R}^{m},\
\mathbf{c}-\sum_{i=1}^{m}\lambda_{i}\mathbf{a}_{i}\in{\mathcal{K}}^{*}\right\\}\,,$
(D)

where
${\mathcal{K}}^{*}\coloneqq\left\\{\mathbf{x}\in\mathbb{R}^{n}\colon\mathbf{y}^{\mathsf{T}}\mathbf{x}\geq
0\ \mbox{ all }\mathbf{y}\in{\mathcal{K}}\right\\}$ is the dual cone of
${\mathcal{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 ${\mathcal{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,

$\displaystyle\inf_{\mathbf{x}}\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{x}\colon\
\mathbf{x}\in{\mathcal{X}}_{0},\
\mathbf{a}_{i}(\mathbf{u})^{\mathsf{T}}\mathbf{x}\leq
b_{i}(\mathbf{u})\,,\mbox{ all }i\in[1\\!:\\!m]\right\\}\ \mbox{ where
}\mathbf{u}\in{\mathcal{U}}^{s},\,\mbox{and }s\in[1\\!:\\!S]\,.$ (1)

Here the problem data are affine functions of $\mathbf{u}$, i.e.
$\mathbf{c}(\mathbf{u})\coloneqq\mathbf{c}_{0}+{\mathsf{C}}\mathbf{u},\
\mathbf{a}_{i}(\mathbf{u})\coloneqq\mathbf{a}^{0}_{i}+{\mathsf{A}}_{i}\mathbf{u}$
and $b_{i}(\mathbf{u})\coloneqq
b^{0}_{i}+\mathbf{b}_{i}^{\mathsf{T}}\mathbf{u}\,,\mbox{all }i\in[1\\!:\\!m]$
and ${\mathcal{X}}_{0}\in\left\\{\mathbb{R}^{n}_{+},\
\mathbb{R}^{n_{1}}_{+}\times\left\\{0,1\right\\}^{n_{2}}\right\\}$. Problem
(1) describes a family of instances parametrized by $\mathbf{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 $\mathbf{u}$ which
belong to certain uncertainty sets ${\mathcal{U}}^{s}\subseteq\mathbb{R}^{q}$.
Here we assume that these sets consist of all realizations of $\mathbf{u}$ the
decision maker need to take into account, according to their responsibility.

The uncertainty sets ${\mathcal{U}}^{s}$ depend on the second parameter
$s\in[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.
${\mathcal{U}}^{s}\coloneqq\left\\{\mathbf{u}\colon(1,\mathbf{u})^{\mathsf{T}}\in{\mathcal{K}}^{s}\right\\}$
where ${\mathcal{K}}^{s}$ are appropriate closed, convex, pointed cones. Note
that these assumptions, together with boundedness of ${\mathcal{U}}^{s}$
entail the following implication:

$\displaystyle(0,\mathbf{x}^{\mathsf{T}})^{\mathsf{T}}\in{\mathcal{K}}^{s}\implies\mathbf{x}=\mathbf{o}\,.$
(2)

######  Remark 1.

Our modeling choice on ${\mathcal{U}}^{s}$, ${\mathcal{K}}^{s}$ and
$s\in[1\\!:\\!S]$ was made with the desire in mind to have a readable notation
that can, with little effort, capture very general structure. We are aware
that these are neither the most natural nor the most practical modeling
choices for those objects, if we think of more specific instances of robust
optimization problems under endogenous uncertainty. Consider for example
uncertainty sets
$\hat{{\mathcal{U}}}(\hat{{\mathbf{r}}})\coloneqq\left\\{\mathbf{u}\in\mathbb{R}^{q}_{+}\colon
u_{i}\leq 1+0.5\hat{r}_{i}\right\\}$ with
$\hat{{\mathbf{r}}}\in\hat{{\mathcal{X}}}\coloneqq\left\\{\hat{{\mathbf{r}}}\in\left\\{0,1\right\\}^{\hat{S}}\colon{\mathsf{A}}\hat{{\mathbf{r}}}\leq\mathbf{b}\right\\}$
and assume the latter set is bounded. Then one can set
$S=|\hat{{\mathcal{X}}}|$, construct an isomorphism
$f\colon\hat{{\mathcal{X}}}\mapsto[1\\!:\\!S]$ and set
${\mathcal{K}}^{s}\coloneqq\mathrm{cone}\left(\left\\{1\right\\}\times\hat{{\mathcal{U}}}\left(f^{-1}(s)\right)\right)$
in order to obtain
${\mathcal{U}}^{s}=\hat{{\mathcal{U}}}\left(f^{-1}(s)\right)$ so that we have
a reformulation that complies to our assumption but is arguably less
practical. Firstly, the number of variables has increased to a size perhaps
exponential in $\hat{n}_{B}$ and the size of ${\mathsf{A}}$. Secondly the
implicit constraint $\mathbf{e}^{\mathsf{T}}{\mathbf{r}}=1$ present in our
formulation can be much more challenging for MILP solvers than the
inequalities in the description of $\hat{{\mathcal{X}}}$. For practical
purposes it is therefore advisable to operate in the original space of
variables. We chose our general formulation merely to be able to speak of
general structure in simple terms.

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
${\mathcal{U}}^{s}={\mathcal{U}}^{s}_{1}\times\dots\times{\mathcal{U}}^{s}_{k}$.
The factors of such products are likewise modeled as conic intersections with
cones ${\mathcal{K}}_{i}^{s},\ i\in[1\\!:\\!k]$.

######  Remark 2.

The choices on $\mathbf{x}$ and $s$ a decision maker takes may be entangled in
a way that a decision on $\mathbf{x}$ limits the options on $s$ (see [21] for
examples). Such a situation can always be modeled via constraints of the form

$\displaystyle{\mathsf{H}}\mathbf{x}+{\mathsf{G}}\mathbf{y}\leq{\mathsf{F}}{\mathbf{r}}_{s}+\mathbf{f},$

where $\mathbf{y}$ is an auxiliary (real or binary) variable;
${\mathsf{H}},{\mathsf{G}},{\mathsf{F}},\mathbf{f}$ are appropriate
matrices/vectors and the entries of ${\mathbf{r}}_{s}$ are defined by the
indicators (binary variables)

$\displaystyle r^{s}_{i}=\begin{cases}1&\mbox{ if }s=i\,,\\\ 0&\mbox{
else.}\end{cases}$ (3)

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
$\mathbf{c}(\mathbf{u}),\ \mathbf{a}_{i}(\mathbf{u})$ and $b_{i}(\mathbf{u})$
while keeping the uncertainty sets constant (see Section 4).

##  2 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\limits_{s\in[1:S]}\left(\varphi_{s}+\gamma_{s}\right)$, where

$\displaystyle\begin{split}\varphi_{s}\coloneqq\inf_{\mathbf{x}}\quad\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}&\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}\\\
\mathrm{s.t.:}\ \mathbf{a}_{i}(\mathbf{u}_{i})^{\mathsf{T}}\mathbf{x}&\leq
b_{i}(\mathbf{u}_{i})\,\mbox{ for all
}\mathbf{u}_{i}\in{\mathcal{U}}^{s}_{i}\,,\mbox{ all }i\in[1\\!:\\!m]\\\
\quad\mathbf{x}&\in{\mathcal{X}}_{0}.\end{split}$ (RC-s)

Under uncertainty regime $s$, the term
$\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}$
captures the worst-case performance of a solution
$\mathbf{x}\in{\mathcal{X}}_{0}$, and $\varphi_{s}$ is the optimal value of
the robust counterpart to (1). The cost of activating uncertainty regime $s$
is given by $\gamma_{s}$, which is thus a function of $s$. C-MILP
reformulations of $\inf\limits_{s\in[1:S]}\varphi_{s}+\gamma_{s}$ have been
studied in [18, 21]. We define the set of optimal solutions to this problem to
be

$\displaystyle{\mathcal{R}}^{s}_{opt}\coloneqq\left\\{\mathbf{x}\in\mathbb{R}^{n}_{+}\colon\mathbf{x}\mbox{
is an optimal solution to (\ref{eqn:UAModelPrimalWorst})}\right\\}$

We will discuss in Subsection 2.2 how to work with the constraint
$\mathbf{x}\in{\mathcal{R}}^{s}_{opt}$. Following the ideas conveyed in 2 and
3, we will now introduce two models in the focus of this text.

####  2.1.1 A multi-objective optimization approach via
$\varepsilon$-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 $\varepsilon$-constraints which is well known in the multi-
objective optimization literature (see e.g. [8]) . The respective model is
given by:

$\displaystyle\begin{split}\inf_{\mathbf{x},s}\quad\gamma_{s}+{\mathcal{M}}(\mathbf{x},s)\\\
\mathrm{s.t.:}\ \mathbf{a}_{i}(\mathbf{u}_{i})^{\mathsf{T}}\mathbf{x}&\leq
b_{i}(\mathbf{u}_{i})\,\mbox{ for all
}\mathbf{u}_{i}\in{\mathcal{U}}^{s}_{i}\,,\mbox{ all }i\in[1\\!:\\!m]\\\
\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}&\leq\varphi^{*}+\varepsilon,\
\mathbf{x}\in{\mathcal{X}}_{0}.\end{split}$

Here, $\varphi^{*}$ is the optimal value of the endogenously robust
counterpart, gross of the activation cost of the robustly optimal uncertainty
regime, and $\varepsilon\geq 0$ is a degree two which we allow our solution to
deviate from that optimal value. The function ${\mathcal{M}}(\mathbf{x},s)$
gives a measure of the performance of a solution $(\mathbf{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 ${\mathcal{M}}(\mathbf{x},s)$
and study their reformulations in Section 3. But first we will introduce an
alternative model that is applicable to bilevel optimization setting.

####  2.1.2 A bilevel optimization approach

Following the idea illustrated in 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 $\mathbf{x}$ controlled by the follower. Thus we want to
solve

$\displaystyle\begin{split}\inf_{\mathbf{x},s}&\left\\{\gamma_{s}+\alpha\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}+{\mathcal{M}}(\mathbf{x},s)\colon\mathbf{x}\in{\mathcal{R}}^{s}_{opt},\
s\in[1\\!:\\!S]\right\\}\,.\end{split}$ (UPP)

Note that (UPP) is feasible if and only if there is at least one
$s\in[1\\!:\\!S]$ such that (RC-s) is feasible and attains its optimal value.
Here $\alpha$ 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. 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.

###  2.2 The robustly optimal set ${\mathcal{R}}^{s}_{opt}$

The feasible set of the decision vector $\mathbf{x}$ is given by
${\mathcal{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 ${\mathcal{X}}_{0}=\mathbb{R}^{n}_{+}$ we will use robust duality theory
in order to characterize ${\mathcal{R}}^{s}_{opt}$. In case of
${\mathcal{X}}_{0}=\mathbb{R}^{n_{1}}_{+}\times\left\\{0,1\right\\}^{n_{2}}$,
this theory does unfortunately not apply, so we provide alternative ways for
these cases.

Let us first deal with the case when ${\mathcal{X}}_{0}=\mathbb{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
$\mathbf{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

$\displaystyle\begin{split}\sup_{\mathbf{y},\mathbf{u}_{i}}\left\\{\sum_{i=1}^{m}b_{i}(\mathbf{u}_{i})y_{i}\colon\mathrm{s.t.:}\sum_{i=1}^{m}\mathbf{a}_{i}(\mathbf{u}_{i})y_{i}\leq\mathbf{c}(\mathbf{u}_{0})\,,\
\mathbf{y}\in\mathbb{R}^{m}_{+},\
\mathbf{u}_{i}\in{\mathcal{U}}^{s}_{i}\,,\mbox{ all
}i\in[0\\!:\\!m]\right\\}\,.\end{split}$ (4)

We have the following result [2, Theorem 3.1]:

######  Theorem 1.

The problem (4) and the Lagrangian dual of (RC-s) are equivalent.

Note that (RC-s) is convex in $\mathbf{x}$ as the inner suprema are convex
functions in $\mathbf{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
$(\mathbf{x};\bar{\mathbf{u}},\mathbf{y})\in\mathbb{R}^{n}_{+}\times{\mathcal{U}}^{s}\times\mathbb{R}^{m}_{+}$
of (RC-s) are characterized by

$\displaystyle\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}$
$\displaystyle\leq\sum_{i=1}^{m}b_{i}(\bar{\mathbf{u}}_{i})y_{i}\,,\hskip
176.407pt$ (Zero Duality Gap)
$\displaystyle\mathbf{a}_{i}(\mathbf{u}_{i})^{\mathsf{T}}\mathbf{x}$
$\displaystyle\leq b_{i}(\mathbf{u}_{i})\,\mbox{ for all
}\mathbf{u}_{i}\in{\mathcal{U}}^{s}_{i}\,,\mbox{ all }i\in[1\\!:\\!m]\,,$
(Primal Feasibility)
$\displaystyle\sum_{i=1}^{m}\mathbf{a}_{i}(\bar{\mathbf{u}}_{i})y_{i}$
$\displaystyle\leq\mathbf{c}(\bar{\mathbf{u}}_{0})\,.$ (Dual Feasibility)

These relations therefore characterize ${\mathcal{R}}^{s}_{opt}$.

###### Proof.

The proof is immediate from 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 1 we can see that the assumptions in 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.

###  2.3 Finite reformulations for mixed-integer problems

We now consider the case where
${\mathcal{X}}_{0}=\mathbb{R}^{n_{1}}_{+}\times\left\\{0,1\right\\}^{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:

######  Theorem 2.

Assume
${\mathcal{X}}_{0}=\mathbb{R}^{n_{1}}\times\left\\{0,1\right\\}^{n_{2}}$, then
$(\mathbf{x},s)$ is feasible for (UPP) if and only if the following
constraints hold:

$\displaystyle\begin{split}\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}&\leq\varphi_{j}+(1-r^{s}_{j})M_{j}\,,\mbox{
all }j\in[1\\!:\\!S],\\\
\mathbf{a}_{i}(\mathbf{u}_{i})^{\mathsf{T}}\mathbf{x}&\leq
b_{i}(\mathbf{u}_{i})\,\mbox{ for all
}\mathbf{u}_{i}\in{\mathcal{U}}^{s}_{i}\,,\mbox{ all }i\in[1\\!:\\!m],\\\
\mathbf{x}&\in{\mathcal{X}}_{0},\ s\in[1\\!:\\!S],\end{split}$ (5)

where $M_{j}$ are upper bounds for $\varphi_{\max}-\varphi_{j}\,,\mbox{ all
}j\in[1\\!:\\!S]$ with
$\varphi_{\max}\coloneqq\sup\limits_{s\in[1:S]}\varphi_{s}$, while
$\varphi_{j}$ is the optimal value of (RC-s) under uncertainty regime $s=j$
and ${\mathbf{r}}_{j}$ is defined as in (3).

###### Proof.

Let $(\mathbf{x},s)$ be feasible for (UPP), then $s\in[1\\!:\\!S]$ and
$\mathbf{x}\in{\mathcal{R}}^{s}_{opt}$ so that it fulfills the last two
constraints of (5). Further, by this fact, we have
$\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}=\varphi_{s}\leq\varphi_{\max}\leq\varphi_{k}+M_{k}$
for all $k\in[1\\!:\\!S]\setminus\left\\{s\right\\}$. Thus $(\mathbf{x},s)$ is
feasible for (5). For the converse, assume $(\mathbf{x},s)$ is feasible for
(5) so that all but the $s$-th constraint are redundant and by definition and
by feasibility we have
$\varphi_{s}\leq\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}\leq\varphi_{s}$.
So that indeed $\mathbf{x}\in{\mathcal{R}}^{s}_{opt}$, and $(\mathbf{x},s)$ is
feasible for (UPP). ∎

Finding appropriate $M_{j}$ for all $j\in[1\\!:\\!S]$ can be challenging. At
least $\varphi_{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 2 is added. However, $\varphi_{\max}$ is the more
challenging entity. One way to derive an upper bound would be to solve
$\sup_{s\in[1:S]}\bar{\varphi}_{s}$ where $\bar{\varphi}_{s}$ is obtained by
changing the outer infimum in $\varphi_{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.

######  Theorem 3.

Assume
${\mathcal{X}}_{0}=\mathbb{R}^{n_{1}}_{+}\times\left\\{0,1\right\\}^{n_{2}}$
and ${\mathcal{U}}^{s}_{i}={\mathcal{U}}_{i}$ for $i\in[1\\!:\\!m]$, i.e. only
the uncertainty in the objective of (1) is affected by $s$. For all
$j\in[1\\!:\\!S]$, select any $\mathbf{z}_{j}\in{\mathcal{R}}^{j}_{opt}$. Then
$(\mathbf{x},s)\in{\mathcal{X}}_{0}\times[1\\!:\\!S]$ if feasible for (UPP) if
and only if the following constraints hold:

$\displaystyle\begin{split}\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}&\leq\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{z}_{j}\right\\}\,,\mbox{
all }j\in[1\\!:\\!S]\,,\\\
\mathbf{a}_{i}(\mathbf{u}_{i})^{\mathsf{T}}\mathbf{x}&\leq
b_{i}(\mathbf{u}_{i})\,\mbox{ for all
}\mathbf{u}_{i}\in{\mathcal{U}}_{i}\,,\mbox{ all }i\in[1\\!:\\!m]\,.\\\
\end{split}$ (6)

###### Proof.

Assume $(\mathbf{x},s)$ is feasible for (UPP), then
$\mathbf{x}\in{\mathcal{R}}^{s}_{opt}$ so that it fulfills the last constraint
of (6). Also by this fact we have that
$\varphi_{s}=\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}=\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{z}_{s}\right\\}\leq\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{z}_{j}\right\\}$
for all $j\in[1\\!:\\!S]\setminus\left\\{s\right\\}$, since all
$\mathbf{z}_{j}$ are feasible for (RC-s). Thus $(\mathbf{x},s)$ is feasible
for (6). Conversely, assume $(\mathbf{x},s)$ are feasible for (6). We have
$\sup_{\mathbf{u}_{0}\in{\mathcal{U}}_{0}^{s}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{z}_{s}\right\\}\leq\sup_{\mathbf{u}_{0}\in{\mathcal{U}}_{0}^{s}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}\leq\sup_{\mathbf{u}_{0}\in{\mathcal{U}}_{0}^{s}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{z}_{s}\right\\}$
where the first inequality holds since $\mathbf{x}$ is feasible for
$\varphi_{s}$ and the second holds by feasibility for (6). So that indeed
$\mathbf{x}\in{\mathcal{R}}^{s}_{opt}$, and $(\mathbf{x},s)$ is feasible for
(UPP). ∎

##  3 Modeling uncertainty preference

In this section we will discuss different choices for
${\mathcal{M}}(\mathbf{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.

###  3.1 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\in[1\\!:\\!S]$ and $\mathbf{x}\in{\mathcal{R}}^{s}_{opt}$
the worst-case regret associated with this solution is given by

$\displaystyle\rho(\mathbf{x},s)\coloneqq\sup_{\mathbf{u}\in{\mathcal{U}}^{s}}\left[\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{x}-\inf_{\mathbf{y}\in\mathbb{R}^{n}_{+}}\
\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{y}\colon\mathbf{a}_{i}(\mathbf{u})^{\mathsf{T}}\mathbf{y}\leq
b_{i}(\mathbf{u})\,,\mbox{ all }i\in[1\\!:\\!m]\right\\}\right]$

that is, the worst-case difference between the performance of $\mathbf{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:

$\displaystyle\begin{split}&\inf_{\mathbf{x},s,\rho}\left[\gamma_{s}+\alpha\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}+\beta(\rho)\right]\\\
\mathrm{s.t.:}\
\rho\geq&\sup_{\mathbf{u}\in{\mathcal{U}}^{s}}\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{x}-\inf_{\mathbf{y}\in\mathbb{R}^{n}_{+}}\
\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{y}\colon\mathbf{a}_{i}(\mathbf{u})^{\mathsf{T}}\mathbf{y}\leq
b_{i}(\mathbf{u})\,,\,\mbox{ all }i\in[1\\!:\\!m]\right\\}\right\\}\,,\\\
\mathbf{x}&\in{\mathcal{R}}^{s}_{opt},\ s\in[1\\!:\\!S]\,.\end{split}$ (REG-
UPP)

Here, $\beta(\cdot)$ is a convex, non-decreasing function which introduces a
cost on the regret associated with a chosen solution and $\rho$ is an
auxiliary epigraphical variable. Easy viable choices for $\beta(\cdot)$ 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.

####  3.1.1 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
$\mathbf{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
$\rho(\mathbf{x},s)$ to be the "dual best" of a robust linear optimization
problem we need the following assumption on the underlying uncertain problem.

######  Assumption 1.

The underlying uncertain linear optimization problem has

  * a)

no uncertainty in the objective, i.e. $\mathbf{c}(\mathbf{u})=\mathbf{c}_{0}$,

  * b)

column-wise uncertainty,

  * c)

the domain of $\mathbf{x}$ given by ${\mathcal{X}}_{0}=\mathbb{R}^{n}_{+}$,

and can thus be written as

$\displaystyle\inf_{\mathbf{x}}\left\\{\mathbf{c}_{0}^{\mathsf{T}}\mathbf{x}\colon\mathbf{x}\in\mathbb{R}^{n}_{+},\
\sum_{i=1}^{n}\mathbf{a}_{i}(\mathbf{u}_{i})x_{i}\leq\mathbf{b}(\mathbf{u}_{n+1})\right\\}\mbox{
where }\ \mathbf{u}_{i}\in{\mathcal{U}}^{s}_{i}\,,\mbox{ all
}i\in[1\\!:\\!n+1].$ (7)

where
$\mathbf{b}(\mathbf{u}_{n+1})\coloneqq\mathbf{b}_{0}+{\mathsf{B}}\mathbf{u}_{n+1}$.
For the above formulation we assume that

  * d1)

either there is an $\mathbf{x}\in\mathbb{R}^{n}_{+}$ such that there exist
$\mathbf{u}_{i}\in\mathrm{int}\left({\mathcal{U}}^{s}_{i}\right)\,,\mbox{ all
}i\in[1\\!:\\!n+1]$ so that the inequalities are fulfilled, where the
$\mathrm{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 1 d1):

######  Lemma 4.

Consider the following condition on (7):

  * d’)

There is an $\mathbf{x}\in\mathbb{R}^{n}_{+}$ such that there are
$\mathbf{u}_{i}\in{\mathcal{U}}^{s}_{i}\,,\mbox{ all }i\in[1\\!:\\!n+1]$, so
that the inequalities are fulfilled strictly.

We have that d’) implies 1 d1).

###### Proof.

Take any $\mathbf{u}^{0}_{i}\in\mathrm{int}({\mathcal{U}}^{s}_{i})\,,\mbox{
all }i\in[1\\!:\\!n+1]$, then for
$\bar{\mathbf{u}}_{i}\coloneqq\mathbf{u}^{0}_{i}-\mathbf{u}_{i}$ we have
$\mathbf{u}_{i}+\lambda\bar{\mathbf{u}}_{i}\in\mathrm{int}({\mathcal{U}}^{s}_{i})$
for any $\lambda\in(0,1]$ by [24, Theorem 6.1]. Define
$\bm{\varepsilon}\coloneqq\mathbf{b}(\mathbf{u}_{n+1})-\sum_{i=1}^{n}x_{i}\mathbf{a}_{i}(\mathbf{u}_{i})$.
Since by assumption $\bm{\varepsilon}\in\mathrm{int}(\mathbb{R}^{m}_{+})$, we
can choose $\lambda\in(0,1]$ such that
$\lambda\left(\sum_{i=1}^{n}x_{i}{\mathsf{A}}_{i}\bar{\mathbf{u}}_{i}-{\mathsf{B}}\bar{\mathbf{u}}_{n+1}\right)\leq\bm{\varepsilon}$.
We then have

$\displaystyle\sum_{i=1}^{n}x_{i}\mathbf{a}_{i}(\mathbf{u}_{i}+\lambda\bar{\mathbf{u}})-{\mathsf{B}}\left(\mathbf{u}_{n+1}+\lambda\bar{\mathbf{u}}_{n+1}\right)$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}x_{i}\left(\mathbf{a}^{0}_{i}+{\mathsf{A}}_{i}\mathbf{u}_{i}\right)-{\mathsf{B}}\mathbf{u}_{n+1}+\lambda\left(\sum_{i=1}^{n}x_{i}{\mathsf{A}}_{i}\bar{\mathbf{u}}-{\mathsf{B}}\bar{\mathbf{u}}_{n+1}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n}x_{i}\mathbf{a}_{i}(\mathbf{u}_{i})-{\mathsf{B}}\mathbf{u}_{n+1}+\bm{\varepsilon}=\mathbf{b}_{0}$

and
$\mathbf{u}_{i}+\lambda\bar{\mathbf{u}}_{i}\in\mathrm{int}({\mathcal{U}}^{s}_{i})\,,\mbox{
all }i\in[1\\!:\\!n+1]$. ∎

We can generally assume that
$\left\\{\mathbf{o}\right\\}\in\mathrm{int}({\mathcal{U}}^{s})$ since we can
always shift the set and adapt the constant terms in
$\mathbf{a}(\mathbf{u}),\mathbf{c}(\mathbf{u})$ and $\mathbf{b}(\mathbf{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

$\displaystyle\begin{split}\inf_{\mathbf{x},\mathbf{u}}\left\\{\mathbf{c}_{0}^{\mathsf{T}}\mathbf{x}\sum_{i=1}^{n}x_{i}\mathbf{a}_{i}(\mathbf{u}_{i})\leq\mathbf{b}(\mathbf{u}_{n+1}),\
\mathbf{x}\in\mathbb{R}^{n}_{+},\
\mathbf{u}_{i}\in{\mathcal{U}}^{s}_{i}\,,\mbox{ all
}i\in[1\\!:\\!n+1]\right\\}\,,\end{split}$ (8)

is precisely of the form (4) so that by [2, Theorem 3.1] we can close the
duality gap between (8) and

$\displaystyle\begin{split}\sup_{\mathbf{z}}\left\\{\inf_{\mathbf{u}_{n+1}\in{\mathcal{U}}^{s}_{n+1}}\left\\{\mathbf{b}(\mathbf{u}_{n+1})^{\mathsf{T}}\mathbf{z}\right\\}\colon
c^{0}_{i}\geq\mathbf{a}_{i}(\mathbf{u}_{i})^{\mathsf{T}}\mathbf{z}\,\mbox{ for
all }\mathbf{u}_{i}\in{\mathcal{U}}^{s}_{i}\,,\mbox{ all }i\in[1\\!:\\!n]\,,\
-\mathbf{z}\in\mathbb{R}^{m}_{+}\right\\}\,,\end{split}$ (9)

if regularity conditions are met (e.g. Slater’s condition or polyhedrality).
Mindful of this fact, we see that 1 suffices to prove the following theorem.

######  Theorem 5.

Assume that 1 holds. Then (REG-UPP) is equivalent to the following
optimization problem

$\displaystyle\begin{split}&\inf_{\mathbf{x},\mathbf{z},s,\rho}\left[\gamma_{s}+\alpha\mathbf{c}_{0}^{\mathsf{T}}\mathbf{x}+\beta(\rho)\right]\\\
\mathrm{s.t.:}\
&\rho\geq\mathbf{c}_{0}^{\mathsf{T}}\mathbf{x}-\mathbf{b}^{\mathsf{T}}\mathbf{z}+\tau\,,\
-\mathbf{z}\in\mathbb{R}^{n}_{+}\,,\ \mathbf{x}\in{\mathcal{R}}^{s}_{opt}\,,\
s\in[1\\!:\\!S]\,,\\\
&\left(\tau,\mathbf{z}^{\mathsf{T}}{\mathsf{B}}\right)^{\mathsf{T}}\in\left({\mathcal{K}}^{s}_{n+1}\right)^{*}\,,\
\left(c^{0}_{i}-(\mathbf{a}^{0}_{i})^{\mathsf{T}}\mathbf{z},\
-\mathbf{z}^{\mathsf{T}}{\mathsf{A}}_{i}\right)^{\mathsf{T}}\in\left({\mathcal{K}}^{s}_{i}\right)^{*}\,,\mbox{
all }i\in[1\\!:\\!n]\,.\\\ \end{split}$ (10)

###### Proof.

Recall the definition of the max-regret function:

$\displaystyle\rho(\mathbf{x},s)=$
$\displaystyle\sup_{\mathbf{u}\in{\mathcal{U}}^{s}}\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{x}-\inf_{\mathbf{y}\in\mathbb{R}^{n}_{+}}\
\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{y}\colon\mathbf{a}_{i}(\mathbf{u})^{\mathsf{T}}\mathbf{y}\leq
b_{i}(\mathbf{u})\,,\mbox{ all }i\in[1\\!:\\!m]\right\\}\right\\}\ $

which under 1 reduces to

$\displaystyle\rho(\mathbf{x},s)=\ $
$\displaystyle\mathbf{c}_{0}^{\mathsf{T}}\mathbf{x}-\inf_{\mathbf{y},\mathbf{u}_{i}}\left\\{\mathbf{c}^{\mathsf{T}}_{0}\mathbf{y}\colon\mathbf{y}\in\mathbb{R}^{n}_{+},\
\mathbf{u}_{i}\in{\mathcal{U}}^{s}_{i},\
\sum_{i=1}^{n}y_{i}\left(\mathbf{a}_{i}^{0}+{\mathsf{A}}_{i}\mathbf{u}_{i}\right)\leq\mathbf{b}_{0}+{\mathsf{B}}\mathbf{u}_{n+1}\right\\}.$
(11)

We will first show equivalence between the above infimum and

$\displaystyle\inf_{\mathbf{w}_{0},\mathbf{w}_{i},\mathbf{u}_{n+1}}\left\\{\mathbf{c}_{0}^{\mathsf{T}}\mathbf{w}_{0}\colon\left(w^{0}_{i},\
\mathbf{w}_{i}^{\mathsf{T}}\right)^{\mathsf{T}}\in\left({\mathcal{K}}^{s}_{i}\right)^{*},\
\mathbf{u}_{n+1}\in{\mathcal{U}}^{s}_{n+1},\
\sum_{i=1}^{n}w^{0}_{i}\mathbf{a}_{i}^{0}+{\mathsf{A}}_{i}\mathbf{w}_{i}\leq\mathbf{b}_{0}+{\mathsf{B}}\mathbf{u}_{n+1}\right\\},$
(12)

minding the fact that by assumption,
${\mathcal{U}}^{s}_{i}=\left\\{\mathbf{u}_{i}\colon\left(1,\mathbf{u}_{i}^{\mathsf{T}}\right)^{\mathsf{T}}\in{\mathcal{K}}^{s}_{i}\right\\}$
are compact. If $(\mathbf{y},\mathbf{u}_{1},\dots,\mathbf{u}_{n+1})$ is
feasible for (11), we set $w^{0}_{i}=y_{i}$ and
$\mathbf{w}_{i}=y_{i}\mathbf{u}_{i}$ for $i\in[1\\!:\\!n]$ to get an
equivalent solution for (12). Conversely, assuming
$(\mathbf{w}_{0},\mathbf{w}_{1},\dots,\mathbf{w}_{n},\mathbf{u}_{n+1})$ is
feasible for (12), we set $y_{i}=w^{0}_{i}$ and
$\mathbf{u}_{i}=\tfrac{\mathbf{w}_{i}}{w^{0}_{i}}$ if $w^{0}_{i}\neq 0$ and
$\mathbf{u}_{i}=\mathbf{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
$\mathbf{u}_{i}\in\mathrm{int}\left({\mathcal{U}}^{s}_{i}\right)$ translates
to a Slater point in (12). So, in any case, by 1 d) we have strong duality
with its dual given by

$\sup_{\mathbf{z}}\left\\{\mathbf{b}^{\mathsf{T}}\mathbf{z}-\tau:-\mathbf{z}\in\mathbb{R}^{n}_{+},\left(\tau,\mathbf{z}^{\mathsf{T}}{\mathsf{B}}\right)^{\mathsf{T}}\in\left({\mathcal{K}}^{s}_{n+1}\right)^{*},\left(c^{0}_{i}-(\mathbf{a}^{0}_{i})^{\mathsf{T}}\mathbf{z},\
-\mathbf{z}^{\mathsf{T}}{\mathsf{A}}_{i}\right)^{\mathsf{T}}\in\left({\mathcal{K}}^{s}_{i}\right)^{*},\mbox{
all }i\in[1\\!:\\!n]\right\\}\,.$

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 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
$\mathbf{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

$\displaystyle\rho(\mathbf{x},s)=\ $
$\displaystyle\sup_{\mathbf{y},\mathbf{u}_{i}}\left\\{\sum_{i=1}^{n}c_{i}(\mathbf{u}_{i})(x_{i}-y_{i})\colon\mathbf{y}\in\mathbb{R}^{n}_{+},\
\mathbf{u}_{i}\in{\mathcal{U}}^{s}_{i},\
\sum_{i=1}^{n}y_{i}\left(\mathbf{a}_{i}^{0}+{\mathsf{A}}_{i}\mathbf{u}_{i}\right)\leq\mathbf{b}_{0}+{\mathsf{B}}\mathbf{u}_{n+1}\right\\},$

where $\mathbf{u}_{i}$ interacts with $y_{i}$ and stands alone in the product
$c_{i}(\mathbf{u}_{i})x_{i}$. For our relaxation this would mean that we would
have to model the interaction between $\mathbf{w}_{i}$ and $\mathbf{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.

####  3.1.2 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 $\prod_{i\in{\mathcal{J}}_{1}}x_{i}$ and
$\prod_{i\in{\mathcal{J}}_{2}}(1-x_{i})$ for some appropriately chosen
${\mathcal{J}}_{1},{\mathcal{J}}_{2}\subseteq[1\\!:\\!n]$ and replace the
nonlinear terms with lifted variables i.e.
$x_{i_{1},\dots,i_{n}}=x_{i_{1}}\dots x_{i_{n}}$. 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_{\mathbf{z}\geq\mathbf{o}}\left\\{\mathbf{f}(\mathbf{x},s)^{\mathsf{T}}\mathbf{z}\colon{\mathsf{A}}\mathbf{z}=\mathbf{b}\right\\}=\inf_{\mathbf{w}}\left\\{\mathbf{b}^{\mathsf{T}}\mathbf{w}\colon{\mathsf{A}}^{\mathsf{T}}\mathbf{w}\geq\mathbf{f}(\mathbf{x},s)\right\\}\,.$

The final inequality in (REG-UPP) can then be replaced by

$\displaystyle\rho\geq\mathbf{b}^{\mathsf{T}}\mathbf{w},\
{\mathsf{A}}^{\mathsf{T}}\mathbf{w}\geq\mathbf{f}(\mathbf{x},s)\,,$

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

$\displaystyle\inf_{\mathbf{x}\in\left\\{0,1\right\\}^{n}}\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{x}\colon{\mathsf{E}}\mathbf{x}=\mathbf{d}\right\\}\quad\mbox{where
}\mathbf{u}\in{\mathcal{U}}\,.$

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 ${\mathsf{E}}\in\mathbb{R}^{m\times 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 ${\mathsf{E}}$. We
have

$\displaystyle\rho(\mathbf{x},s)=\sup_{\mathbf{u}\in{\mathcal{U}}}\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{x}-\inf_{\mathbf{y}\in\left\\{0,1\right\\}^{n}}\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{y}\colon{\mathsf{E}}\mathbf{y}=\mathbf{d}\right\\}\right\\}$

Assume that
$\mathbf{c}(\mathbf{u})\coloneqq\mathbf{c}_{0}+{\mathsf{C}}\mathbf{u}$ and
that ${\mathcal{U}}\coloneqq[-1,1]^{q}$. Denoting
$\bar{{\mathsf{C}}}\coloneqq({\mathsf{C}},-{\mathsf{C}})$, we have

$\displaystyle\rho(\mathbf{x},s)=$
$\displaystyle\sup_{\mathbf{u}\in[-1,1]^{q},\mathbf{y}\in\mathbb{R}^{n}_{+}}\left\\{(\mathbf{c}_{0}+{\mathsf{C}}\mathbf{u})^{\mathsf{T}}\mathbf{x}-\
(\mathbf{c}_{0}+{\mathsf{C}}\mathbf{u})^{\mathsf{T}}\mathbf{y}\colon{\mathsf{E}}\mathbf{y}=\mathbf{d}\right\\}$
$\displaystyle=$
$\displaystyle\sup_{\mathbf{u}\in[0,1]^{2q},\mathbf{y}\in\mathbb{R}^{n}_{+}}\left\\{(\mathbf{c}_{0}+\bar{{\mathsf{C}}}\mathbf{u})^{\mathsf{T}}\mathbf{x}-\
(\mathbf{c}_{0}+\bar{{\mathsf{C}}}\mathbf{u})^{\mathsf{T}}\mathbf{y}\colon{\mathsf{E}}\mathbf{y}=\mathbf{d}\right\\}.$

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}{\mathsf{E}}\mathbf{y}=u_{i}\mathbf{d}$, all $i\in[1\\!:\\!q]$. We now
lift the space of variables by replacing the bilinear terms $u_{i}y_{j}$ with
$\psi_{ij}$ and construct the McCormick envelope [20] by introducing the
constraints

$\displaystyle\psi_{ij}\leq u_{j},\ \psi_{ij}\leq y_{i}\,,\ \psi_{ij}\geq
y_{i}+u_{j}-1\,,\mbox{ all }j\in[1\\!:\\!q],\ i\in[1\\!:\\!n]\,.$

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.

###  3.2 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:

$\displaystyle\begin{split}&\inf_{\mathbf{x},s,{\overline{q}}_{i},\underline{q}_{i}}\left[\gamma_{s}+\alpha\sup_{\mathbf{u}_{0}\in{\mathcal{U}}^{s}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}+\sum_{i=0}^{m}\beta_{i}({\overline{q}}_{i},\underline{q}_{i})\right]\\\
\mathrm{s.t.:}\
&{\overline{q}}_{0}\geq\sup_{\mathbf{u}_{0}\in{\mathcal{U}}_{0}^{s}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\},\
\underline{q}_{0}\leq\inf_{\mathbf{u}_{0}\in{\mathcal{U}}_{0}^{s}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}\,,\\\
&{\overline{q}}_{i}\geq\sup_{\mathbf{u}_{i}\in{\mathcal{U}}^{s}_{i}}\left\\{\mathbf{a}_{i}(\mathbf{u}_{i})^{\mathsf{T}}\mathbf{x}-b_{i}(\mathbf{u}_{i})\right\\},\
\underline{q}_{i}\leq\inf_{\mathbf{u}_{i}\in{\mathcal{U}}^{s}_{i}}\left\\{\mathbf{a}_{i}(\mathbf{u}_{i})^{\mathsf{T}}\mathbf{x}-b_{i}(\mathbf{u}_{i})\right\\}\,,\mbox{
all }i\in[1\\!:\\!m]\,,\\\ &\mathbf{x}\in{\mathcal{R}}^{s}_{opt}\,,\
s\in[1\\!:\\!S]\,.\end{split}$ (PDA-UPP)

Here, ${\overline{q}}_{i}$ and $\uline{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 $\mathbf{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 $\mathbf{x}$, as they are point-wise
suprema of linear functions. By the same token, the infima are concave in
$\mathbf{x}$. Thus, the respective constraints describe a convex set. The
functions $\beta_{i}({\overline{q}}_{i},\uline{q}_{i})$ are convex functions
that put a cost on the distance between worst- and best-case performance of a
feasible solution $\mathbf{x}$. Next to convexity we assume

$\displaystyle\beta_{i}({\overline{q}}_{i},\uline{q}_{i})\geq
0\,,\quad\frac{\partial\beta_{i}({\overline{q}}_{i},\uline{q}_{i})}{\partial{\overline{q}}_{i}}>0\,,\quad\frac{\partial\beta({\overline{q}}_{i},\uline{q}_{i})}{\partial\uline{q}_{i}}<0\
\mbox{for all}\ {\overline{q}}_{i}\geq\uline{q}_{i}\,.$ (13)

A simple choice for $\beta_{i}$ would be
$\beta_{i}\coloneqq{\overline{q}}_{i}-\uline{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:

$\displaystyle\begin{split}\inf_{\mathbf{x},s,\rho_{i}}&\left[\gamma_{s}+\alpha\\!\left(\mathbf{c}_{0}^{\mathsf{T}}\mathbf{x}+\rho_{0}\right)+\beta_{0}(\mathbf{c}_{0}^{\mathsf{T}}\mathbf{x}+\rho_{0},\mathbf{c}_{0}^{\mathsf{T}}\mathbf{x}-\delta_{0})+\sum_{i=1}^{m}\beta_{i}\\!\left((\mathbf{a}_{0}^{i})^{\mathsf{T}}\mathbf{x}-b_{0}^{i}+\rho_{i},(\mathbf{a}_{0}^{i})^{\mathsf{T}}\mathbf{x}-b_{0}^{i}-\delta_{i}\right)\right]\\\
\mathrm{s.t.:}&\begin{pmatrix}\rho_{0},-\mathbf{x}^{\mathsf{T}}{\mathsf{C}}\end{pmatrix}^{\mathsf{T}}\in\left({\mathcal{K}}^{s}_{0}\right)^{*},\
\begin{pmatrix}\delta_{0},\mathbf{x}^{\mathsf{T}}{\mathsf{C}}\end{pmatrix}^{\mathsf{T}}\in\left({\mathcal{K}}^{s}_{0}\right)^{*}\,,\
\mathbf{x}\in{\mathcal{R}}^{s}_{opt}\,,\ s\in[1\\!:\\!S]\,,\\\
&\begin{pmatrix}\rho_{i},\mathbf{b}_{i}^{\mathsf{T}}-\mathbf{x}^{\mathsf{T}}{\mathsf{A}}_{i}\end{pmatrix}^{\mathsf{T}}\in\left({\mathcal{K}}^{s}_{i}\right)^{*},\
\begin{pmatrix}\delta_{i},\mathbf{x}^{\mathsf{T}}{\mathsf{A}}_{i}-\mathbf{b}_{i}^{\mathsf{T}}\end{pmatrix}^{\mathsf{T}}\in\left({\mathcal{K}}^{s}_{i}\right)^{*}\,,\mbox{
all }i\in[1\\!:\\!m]\,.\\\ \end{split}$ (14)

###### 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 ${\mathcal{M}}(\mathbf{x},s)$ removed.

###  3.3 Best-case performance

In 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
$\mathbf{v}$ instead of $\mathbf{u}$ to suggest that now uncertainty is not
adverse):

$\displaystyle\begin{split}\inf_{\mathbf{v},\mathbf{x},s,\underline{q}_{i}}&\left[\gamma_{s}+\alpha\sup_{\mathbf{u}_{0}\in{\mathcal{U}}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}+\beta\left(\underline{q}_{0},\dots,\underline{q}_{m}\right)\right]\\\
\mathrm{s.t.:}\
&\underline{q}_{0}\geq\mathbf{c}(\mathbf{v})^{\mathsf{T}}\mathbf{x}\,,\
\mathbf{v}\in{\mathcal{U}}^{s},\ \mathbf{x}\in{\mathcal{R}}^{s}_{opt},\
s\in[1\\!:\\!S]\,\\\
&\underline{q}_{i}\geq\mathbf{a}_{i}(\mathbf{v})^{\mathsf{T}}\mathbf{x}-b_{i}(\mathbf{v})\,,\quad\hskip
1.42271pt\mbox{ all }i\in[1\\!:\\!m]\,.\end{split}$ (BCP-UPP)

The function $\beta(.)$ is assumed to be convex and nondecreasing in each
argument; in our applications in later sections it is chosen to be the sum of
$\uline{q}_{i}\,,\mbox{ all }i\in[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 $\underline{q}_{i}$,
all $i\in[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
mixed-integer optimization problem and as such very challenging. In case
${\mathcal{X}}_{0}=\left\\{0,1\right\\}^{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 $\mathbf{x}$ depend on independent
portions of the uncertainty vector $\mathbf{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.

####  3.3.1 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 ${\mathcal{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 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

$\displaystyle\underline{q}_{0}$
$\displaystyle\geq\sum_{i=1}^{n}c_{i}(\mathbf{v}_{i})x_{i},\quad\begin{pmatrix}\underline{q}_{1},&\\!\\!\\!\\!\dots,&\\!\\!\\!\\!\
\underline{q}_{m}\end{pmatrix}^{\mathsf{T}}\geq\sum_{i=1}^{n}x_{i}\mathbf{a}_{i}(\mathbf{v}_{i})-\mathbf{b}(\mathbf{v}_{n+1})\,.$

For the sake of notational simplicity we introduce

$\displaystyle\bar{\mathbf{a}}_{i}(\mathbf{v}_{i})\coloneqq\begin{pmatrix}c_{i}(\mathbf{v}_{i}),&\\!\\!\\!\\!\mathbf{a}_{i}(\mathbf{v}_{i})^{\mathsf{T}}\end{pmatrix}^{\mathsf{T}}\,,i\in[1\\!:\\!n]\,,\quad\bar{\mathbf{b}}(\mathbf{v}_{n+1})\coloneqq\begin{pmatrix}0,&\\!\\!\\!\\!\mathbf{b}(\mathbf{v}_{n+1})^{\mathsf{T}}\end{pmatrix}^{\mathsf{T}}\quad\mbox{and}\quad\underline{{\mathbf{q}}}\coloneqq\begin{pmatrix}\underline{q}_{0},&\\!\\!\\!\\!\dots,&\\!\\!\\!\\!\underline{q}_{m}\end{pmatrix}^{\mathsf{T}}.$

We can then find vectors $\bar{\mathbf{a}}_{i}^{0}$ and matrices
$\bar{{\mathsf{A}}}_{i}$ of appropriate size such that
$\bar{\mathbf{a}}_{i}(\mathbf{v}_{i})=\bar{\mathbf{a}}_{i}^{0}+\bar{{\mathsf{A}}}_{i}\mathbf{v}_{i}$
for all $i\in[1\\!:\\!n]$. We are now ready to state the following theorem.

######  Theorem 7.

Assume that 1 b) holds, so that (BCP-UPP) can be written as

$\displaystyle\begin{split}\inf_{\mathbf{v}_{i},\mathbf{x},s,\underline{{\mathbf{q}}}}&\left[\gamma_{s}+\alpha\sup_{\mathbf{u}_{0}\in{\mathcal{U}}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}+\beta\left(\underline{q}_{0},\dots,\underline{q}_{m}\right)\right]\\\
\mathrm{s.t.:}\
&\underline{{\mathbf{q}}}\geq\sum_{i=1}^{n}x_{i}\bar{\mathbf{a}}_{i}(\mathbf{v}_{i})-\bar{\mathbf{b}}(\mathbf{v}_{n+1})\,,\
\mathbf{v}_{i}\in{\mathcal{U}}^{s}_{i}\ \mbox{for }i\in[1\\!:\\!n+1],\
\mathbf{x}\in{\mathcal{R}}^{s}_{opt}\,,\ s\in[1\\!:\\!S]\,.\end{split}$

Then this problem is equivalent to

$\displaystyle\begin{split}\inf_{\mathbf{w}_{i},\mathbf{v}_{i},\mathbf{x},s,\underline{{\mathbf{q}}}}&\left[\gamma_{s}+\alpha\sup_{\mathbf{u}_{0}\in{\mathcal{U}}_{0}}\left\\{\mathbf{c}(\mathbf{u}_{0})^{\mathsf{T}}\mathbf{x}\right\\}+\beta\left(\underline{q}_{0},\dots,\underline{q}_{m}\right)\right]\\\
\mathrm{s.t.:}\
&\underline{{\mathbf{q}}}\geq\sum_{i=1}^{n}x_{i}\bar{\mathbf{a}}_{i}^{0}+\bar{{\mathsf{A}}}_{i}\mathbf{w}_{i}-\bar{\mathbf{b}}(\mathbf{v}_{n+1})\,,\\\
&\begin{pmatrix}x_{i},&\\!\\!\\!\\!\mathbf{w}_{i}^{\mathsf{T}}\end{pmatrix}^{\mathsf{T}}\in{\mathcal{K}}^{s}_{i}\
\mbox{for }i\in[1\\!:\\!n],\ \mathbf{v}_{n+1}\in{\mathcal{U}}^{s}_{n+1}\,,\
\mathbf{x}\in{\mathcal{R}}^{s}_{opt}\,,\ s\in[1\\!:\\!S]\,.\end{split}$

###### Proof.

The proof is similar to that of 5. ∎

##  4 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 1 and 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
$\varepsilon$-constraint model at the same time, by explicitly presenting the
respective constraints for $\mathbf{x}\in{\mathcal{R}}^{s}_{opt}$, and in
parentheses we present the $\varepsilon$-constraint. We will maintain this
style also in the succeeding section.

###  4.1 The uncertain shortest path problem and its robust counterpart

Consider a directed, weighted graph $G=({\mathcal{V}},{\mathcal{A}})$ where
${\mathcal{V}}$ is the set of vertices and ${\mathcal{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

$\displaystyle\min_{\mathbf{x}\in\mathbb{R}^{|{\mathcal{A}}|}_{+}}\left\\{\mathbf{c}^{\mathsf{T}}\mathbf{x}\colon{\mathsf{E}}\mathbf{x}=\mathbf{d}\right\\},$

where each (directed) arc corresponds to a variable $x_{k}$ under some
relabeling $\pi(k)=(i,j)$ and

$\displaystyle e_{i,k}=\left\\{\begin{matrix}-1&\mbox{if $\pi(k)=(i,j)$ for
some $j$}\\\ 1&\mbox{if $\pi(k)=(j,i)$ for some $j$}\\\ 0&\mbox{otherwise}\\\
\end{matrix}\right.$

Also
$\mathbf{d}=(-1,0,\dots,0,1)^{\mathsf{T}}\in\mathbb{R}^{|{\mathcal{V}}|}$.
That integrality can be dropped stems from the fact that ${\mathsf{E}}$ is
totally unimodular and $\mathbf{d}$ is integral. The dual of the linearized
SPP is given by
$\max_{\mathbf{y}\in\mathbb{R}^{|{\mathcal{V}}|}}\left\\{\mathbf{d}^{\mathsf{T}}\mathbf{y}\colon{\mathsf{E}}^{\mathsf{T}}\mathbf{y}\leq\mathbf{c}\right\\}$.
In case of endogenous uncertain arc weights we can formulate the endogenous
uncertain SPP as

$\displaystyle\min_{\mathbf{x}\in\left\\{0,1\right\\}^{|{\mathcal{A}}|}}\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{x}\colon{\mathsf{E}}\mathbf{x}=\mathbf{d}\right\\},\
\mbox{where }\mathbf{u}\in{\mathcal{U}}^{s},$ (EU-SPP)

and the robust counterpart (for fixed $s$) is given by

$\displaystyle\min_{\mathbf{x}\in\left\\{0,1\right\\}^{|{\mathcal{A}}|}}\left\\{\sup_{\mathbf{u}\in{\mathcal{U}}^{s}}\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{x}\right\\}\colon{\mathsf{E}}\mathbf{x}=\mathbf{d}\right\\}.$
(R-SPP)

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
${\mathcal{R}}^{s}_{opt}$. In special cases, however, the robust counterpart
remains a linear optimization problem so that we can apply 1, in other cases
we can still work with 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 $\mathbf{x}$, and since we can model these as bilinear terms
between ${\mathbf{r}}$ and $\mathbf{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
$\mathbf{c}_{s}(\mathbf{u})$ while the uncertainty set will remain constant
across $s\in[1\\!:\\!S]$.

###  4.2 SPP under structured box uncertainty

Define
$\mathbf{c}_{s}(\mathbf{u})\coloneqq\mathbf{c}^{0}_{s}+{\mathsf{C}}_{s}\mathbf{u}$
with $\mathbf{c}^{0}_{s}\in\mathbb{R}_{+}^{|{\mathcal{A}}|}$ and
${\mathsf{C}}_{s}\in\mathbb{R}^{|{\mathcal{A}}|\times q},\ s\in[1\\!:\\!S]$
and consider the following uncertainty set:
${\mathcal{U}}_{\mathrm{Box}}\coloneqq\left\\{\mathbf{u}\in\mathbb{R}^{q}\colon\|\mathbf{u}\|_{\infty}\leq
1\right\\}\,$ , with
${\mathcal{K}}=\left\\{(v_{0},\mathbf{v})\in\mathbb{R}^{m+1}\colon\|\mathbf{v}\|_{\infty}\leq
v_{0}\right\\}$ and
${\mathcal{K}}^{*}=\left\\{(z_{0},\mathbf{z})\in\mathbb{R}^{m+1}\colon\|\mathbf{z}\|_{1}\leq
z_{0}\right\\}$. General box uncertainty can managed by employing 3. However,
there are at least two cases where (R-SPP) under box uncertainty can be
reformulated as a linear optimization problem.

  1. Interval uncertainty:

$q=|{\mathcal{A}}|$ and ${\mathsf{C}}=\mathrm{Diag}(\hat{\mathbf{c}})$ is
diagonal; by flipping $u_{i}\to-u_{i}$ if necessary, we can always assume that
all $\hat{c}_{i}\geq 0$. This is a special case of what we suggest to call

  2. Correlated interval uncertainty

where ${\mathsf{C}}_{s}\in\mathbb{R}^{|{\mathcal{A}}|\times q}_{+}$. We
consider

$\displaystyle\min_{\mathbf{x}\in\left\\{0,1\right\\}^{|{\mathcal{A}}|}}\left\\{\sup_{\mathbf{u}\in{\mathcal{U}}_{\mathrm{Box}}}\left\\{\mathbf{c}_{s}(\mathbf{u})^{\mathsf{T}}\mathbf{x}\right\\}\colon{\mathsf{E}}\mathbf{x}=\mathbf{d}\right\\}\,.$

Since $\max\limits_{\|\mathbf{u}\|_{\infty}\leq
1}\mathbf{g}^{\mathsf{T}}\mathbf{u}=\|\mathbf{g}\|_{1}=\mathbf{e}^{\mathsf{T}}\mathbf{g}$,
with $\mathbf{e}\in\mathbb{R}^{q}$ the all-ones vector, holds for all
$\mathbf{g}\in\mathbb{R}^{q}_{+}$ and since
$\mathbf{g}={\mathsf{C}}_{s}^{\mathsf{T}}\mathbf{x}\in\mathbb{R}^{q}_{+}$
under our assumptions, we have, by total unimodularity,

$\displaystyle\min_{\mathbf{x}\in\left\\{0,1\right\\}^{|{\mathcal{A}}|}}\left\\{\sup_{\mathbf{u}\in{\mathcal{U}}_{\mathrm{Box}}}\left\\{\mathbf{c}_{s}(\mathbf{u})^{\mathsf{T}}\mathbf{x}\right\\}\colon{\mathsf{E}}\mathbf{x}=\mathbf{d}\right\\}=\min_{\mathbf{x}\in\mathbb{R}^{|{\mathcal{A}}|}_{+}}\left\\{({\mathbf{c}}^{0}_{s}+{\mathsf{C}}_{s}\mathbf{e})^{\mathsf{T}}\mathbf{x}\colon{\mathsf{E}}\mathbf{x}=\mathbf{d}\right\\}\,,$

which is a linear optimization problem. It is interesting to note that in the
uncorrelated interval case where
${\mathsf{C}}_{s}=\mathrm{Diag}(\hat{\mathbf{c}})$ with diagonal entries
$\hat{c}_{j}\geq 0$ we have

$\max\limits_{u\in{\mathcal{U}}_{\mathrm{Box}}}[c^{0}_{s,i}+\hat{c}_{j}u_{j}]=c^{0}_{s,j}+\hat{c}_{j}=[\mathbf{c}^{0}_{s}+{\mathsf{C}}_{s}\mathbf{e}]_{j}\quad\mbox{for
all }j\in{\mathcal{A}}\,,$

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 4 below.

####  4.2.1 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
$[\underline{c}^{i}_{s},{\overline{c}}^{i}_{s}]$ if uncertainty regime $s$ is
active. Thus the worst and best-case outcomes do not depend on $\mathbf{x}$
and are easily identified as the outcomes where the travel time is on the
upper and lower bound respectively. Let $s\in[1\\!:\\!S]$ and define
$\underline{\mathbf{c}}_{s}$, and ${\overline{\mathbf{c}}}_{s}$, to be the
element-wise best-case, or worst-case realizations, respectively, of
$\mathbf{c}(\mathbf{u})$ under uncertainty regime $s$. Following above logic,
we arrive at a mixed-integer linear model for each of the uncertainty
preferences:

$\displaystyle\min_{\mathbf{x},s}\gamma_{s}+\alpha{\overline{\mathbf{c}}}_{s}^{\mathsf{T}}\mathbf{x}+{\mathcal{M}}(\mathbf{x},s)$
$\displaystyle\mathrm{s.t.:}\ $
$\displaystyle{\overline{\mathbf{c}}}_{s}^{\mathsf{T}}\mathbf{x}\leq\mathbf{d}^{\mathsf{T}}\mathbf{y}\,,\
{\mathsf{E}}\mathbf{x}=\mathbf{d}\,,\
{\mathsf{E}}^{\mathsf{T}}\mathbf{y}\leq{\overline{\mathbf{c}}}_{s},\,\left({\overline{\mathbf{c}}}_{s}^{\mathsf{T}}\mathbf{x}\leq\varphi^{*}+\varepsilon\right),\
\mathbf{x}\in\mathbb{R}^{|{\mathcal{A}}|}_{+},\ s\in[1\\!:\\!S]\,.$

Here we used 1 in order to characterize ${\mathcal{R}}^{s}_{opt}$. To
accommodate the three different types of uncertainty preferences, we specify
${\mathcal{M}}(\mathbf{x},s)$ in the following ways (with the simplest choice
corresponding to the specification
$\beta({\overline{q}},\underline{q})=\beta(\overline{q}-\underline{q})$ in
(PDA-UPP), which can be generalized in a straightforward manner):

$\displaystyle\mbox{Predictability: }{\mathcal{M}}(\mathbf{x},s)=$
$\displaystyle\left({\overline{\mathbf{c}}}_{s}-\underline{\mathbf{c}}_{s}\right)^{\mathsf{T}}\mathbf{x}\,,$
$\displaystyle\mbox{Best-case Performance : }{\mathcal{M}}(\mathbf{x},s)=$
$\displaystyle\ \underline{\mathbf{c}}_{s}^{\mathsf{T}}\mathbf{x}\,,$
$\displaystyle\mbox{Regret: }{\mathcal{M}}(\mathbf{x},s)=$ $\displaystyle\
\inf_{\mathbf{z}}\left\\{{\overline{\mathbf{c}}}_{s}^{\mathsf{T}}\mathbf{x}-\mathbf{d}^{\mathsf{T}}\mathbf{z}\colon{\mathsf{E}}^{\mathsf{T}}\mathbf{z}\leq\mathbf{c}_{\mathbf{x}}\right\\}\,,$

where
$\mathbf{c}_{\mathbf{x}}\coloneqq\underline{\mathbf{c}}_{s}+\sum_{i=1}^{|{\mathcal{A}}|}x_{i}\,\mathbf{e}_{i}\mathbf{e}_{i}^{\mathsf{T}}\left({\overline{\mathbf{c}}}_{s}-\underline{\mathbf{c}}_{s}\right)$.
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.

####  4.2.2 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 4 we will demonstrate the difference between interval and
correlated interval uncertainty.

For the uncertain travel times under uncertainty regime $s$ given by
$\mathbf{c}_{s}(\mathbf{u})\coloneqq\mathbf{c}^{0}_{s}+{\mathsf{C}}_{s}\mathbf{u}$,
let ${\mathsf{C}}_{s}$ be non-negative. Then we have
$\|{\mathsf{C}}_{s}^{\mathsf{T}}\mathbf{x}\|_{1}=\mathbf{e}^{\mathsf{T}}{\mathsf{C}}_{s}^{\mathsf{T}}\mathbf{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 ${\mathcal{R}}^{s}_{opt}$ as follows:

$\displaystyle\min_{\mathbf{x},s}\ $
$\displaystyle\gamma_{s}+\alpha({\mathbf{c}}^{0}_{s}+{{\mathsf{C}}}_{s}\mathbf{e})^{\mathsf{T}}\mathbf{x}\
+{\mathcal{M}}(\mathbf{x},s)$ $\displaystyle\mathrm{s.t.:}\ $
$\displaystyle({\mathbf{c}}^{0}_{s}+{{\mathsf{C}}}_{s}\mathbf{e})^{\mathsf{T}}\mathbf{x}\leq\mathbf{d}^{\mathsf{T}}\mathbf{y}\,,\
{\mathsf{E}}\mathbf{x}=\mathbf{d}\,,\
\mathbf{x}\in\mathbb{R}^{|{\mathcal{A}}|}_{+}\,,\ s\in[1\\!:\\!S]\,,$
$\displaystyle{\mathsf{E}}^{\mathsf{T}}\mathbf{y}\leq{\mathbf{c}}^{0}_{s}+{{\mathsf{C}}}_{s}\mathbf{e}\,,\left(({\mathbf{c}}^{0}_{s}+{{\mathsf{C}}}_{s}\mathbf{e})^{\mathsf{T}}\mathbf{x}\leq\varphi^{*}+\varepsilon\right)\,.$

Again, ${\mathcal{M}}(\mathbf{x},s)$ can be specified in three different ways
according to the respective uncertainty preferences:

Predictability:
$\displaystyle{\mathcal{M}}(\mathbf{x},s)=2\mathbf{e}^{\mathsf{T}}{\mathsf{C}}_{s}^{\mathsf{T}}\mathbf{x}\,,$
Best-case Performance:
$\displaystyle{\mathcal{M}}(\mathbf{x},s)=(\mathbf{c}^{0}_{s})^{\mathsf{T}}\mathbf{x}-\mathbf{e}^{\mathsf{T}}{\mathsf{C}}_{s}^{\mathsf{T}}\mathbf{x}\,,$
Regret:
$\displaystyle{\mathcal{M}}(\mathbf{x},s)=\mathbf{b}^{\mathsf{T}}\mathbf{w}\,,\
{\mathsf{A}}^{\mathsf{T}}\mathbf{w}\geq\mathbf{f}(\mathbf{x},s)\,,$

where $\mathbf{b},{\mathsf{A}},$ and $\mathbf{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
${\mathsf{C}}\in\mathbb{R}^{n\times m}_{+}$ and consider

$\sup/\inf_{\|\mathbf{u}\|_{\infty}\leq
1}\mathbf{x}^{\mathsf{T}}{\mathsf{C}}^{\mathsf{T}}\mathbf{u}=\pm\mathbf{x}^{\mathsf{T}}{\mathsf{C}}^{\mathsf{T}}\mathbf{e}=\sup/\inf_{\|\mathbf{w}\|_{\infty}\leq
1}\mathbf{x}^{\mathsf{T}}\mathrm{Diag}\left(({\mathsf{C}}^{\mathsf{T}}\mathbf{e})_{1},\dots,({\mathsf{C}}^{\mathsf{T}}\mathbf{e})_{n}\right)\mathbf{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 ${\mathsf{C}}=0.5\,\mathbf{e}$
and ${\mathcal{U}}=\left\\{u\colon u\in[-1,1]\right\\}$ and
$\mathbf{c}_{0}=1.5\,\mathbf{e}$. In this case the same outcome would have to
occur on all four edges simultaneously and the maximum regret would always be
0.

$1$$2$$3$$4$ Figure 2:

###  4.3 SPP with general box uncertainty

If we have box uncertainty where ${\mathsf{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 ${\mathcal{R}}^{s}_{opt}$
based on 1 is no longer possible, and hence 3 has to be invoked. With
$\mathbf{c}_{s}(\mathbf{u})$ given as above, (UPP) for the SPP with general
box uncertainty can be cast as:

$\displaystyle\begin{split}\inf_{\mathbf{x},s}&\left[\gamma_{s}+\alpha\left((\mathbf{c}^{0}_{s})^{\mathsf{T}}\mathbf{x}+\|{\mathsf{C}}_{s}^{\mathsf{T}}\mathbf{x}\|_{1}\right)+{\mathcal{M}}(\mathbf{x},s)\right]\\\
\mathrm{s.t.:}\
&(\mathbf{c}^{0}_{s})^{\mathsf{T}}\mathbf{x}+\|{\mathsf{C}}_{s}^{\mathsf{T}}\mathbf{x}\|_{1}\leq(\mathbf{c}^{0}_{s})^{\mathsf{T}}\mathbf{z}_{j}+\|{\mathsf{C}}_{s}^{\mathsf{T}}\mathbf{z}_{j}\|_{1}\,,\mbox{
all }j\in[1\\!:\\!S]\,,\\\
{\mathsf{E}}\mathbf{x}&=\mathbf{d}\,,\left((\mathbf{c}^{0}_{s})^{\mathsf{T}}\mathbf{x}+\|{\mathsf{C}}_{s}^{\mathsf{T}}\mathbf{x}\|_{1}\leq\varphi^{*}+\varepsilon\right),\\\
\mathbf{x}&\in\left\\{0,1\right\\}^{|{\mathcal{A}}|},\
s\in[1\\!:\\!S]\,,\end{split}$ (15)

where $\mathbf{z}_{j}\in{\mathcal{R}}_{opt}^{j}$ for all $j\in[1\\!:\\!S]$.
The respective specifications for ${\mathcal{M}}(\mathbf{x},s)$ are

Predictability:
$\displaystyle{\mathcal{M}}(\mathbf{x},s)=2\|{\mathsf{C}}_{s}^{\mathsf{T}}\mathbf{x}\|_{1}\,,$
Best-case performance:
$\displaystyle{\mathcal{M}}(\mathbf{x},s)=\inf_{\mathbf{u}\in{\mathcal{U}}}\left\\{(\mathbf{c}^{0}_{s})^{\mathsf{T}}\mathbf{x}+\mathbf{u}^{\mathsf{T}}{\mathsf{C}}_{s}^{\mathsf{T}}\mathbf{x}\right\\}\,,$
Regret:
$\displaystyle{\mathcal{M}}(\mathbf{x},s)=\mathbf{b}^{\mathsf{T}}\mathbf{w}\,,\
{\mathsf{A}}^{\mathsf{T}}\mathbf{w}\geq\mathbf{f}(\mathbf{x},s)\,.$

Since $\mathbf{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

$\displaystyle\rho(\mathbf{x},s)=\sup_{\mathbf{u}\in{\mathcal{U}}}\left\\{\mathbf{c}_{s}(\mathbf{u})^{\mathsf{T}}\mathbf{x}-\inf_{\mathbf{y}\in\left\\{0,1\right\\}^{|{\mathcal{A}}|}}\left\\{\mathbf{c}_{s}(\mathbf{u})^{\mathsf{T}}\mathbf{y}\colon{\mathsf{E}}\mathbf{y}=\mathbf{d}\right\\}\right\\}$

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
$\mathbf{x}\in{\mathcal{R}}^{s}_{opt}$ are derived using 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 $(\mathbf{x},s)$, it checks
whether

$\displaystyle(\mathbf{c}^{0}_{s})^{\mathsf{T}}\mathbf{x}+\|{\mathsf{C}}_{s}^{\mathsf{T}}\mathbf{x}\|_{1}\leq\inf_{\mathbf{y}\in\left\\{0,1\right\\}^{|{\mathcal{A}}|}}\left\\{\sup_{\mathbf{u}\in{\mathcal{U}}}\left\\{\mathbf{c}_{s}(\mathbf{u})^{\mathsf{T}}\mathbf{y}\right\\}\colon{\mathsf{E}}\mathbf{y}=\mathbf{d}\right\\}.$

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.

##  5 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.

###  5.1 The $\varepsilon$-constraint model for the SPP

In this set of experiments we exemplify the use of the
$\varepsilon$-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 $|{\mathcal{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 $\varphi^{*}$. Replacing ${\mathcal{M}}(\mathbf{x},s)$ with
the respective terms for predictability, best-case performance and regret one
at a time, we resolved each instance allowing for an $\varepsilon$ violation
of the optimality constraint where
$\varepsilon\in\left\\{1\%,2\%,\dots,10\%\right\\}$. The blue line in the
graphs of Figure 3 depicts the change of the optimal solutions predictability,
best-case performance and max regret with $\varepsilon$, while the orange line
depicts the change of the solutions worst case performance. The values were
normalized by their range across different values of $\varepsilon$ and
averaged across all 10 instances.

Figure 3: Trade-off between the secondary characteristics and robustly optimal
value.

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 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.

preferences | $T$ | [$T_{min}$, $T_{max}$] %
---|---|---
predi | 53.69 | [12.43, 200.12]
bestc | 42.83 | [10.05, 174.17]
regret | 592.29 | [1388.64, 328.43]
Table 1: Run time for the $\varepsilon$-constraints model

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.

###  5.2 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 trade-off 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 $|{\mathcal{V}}|=300,\ S=10$ for the interval uncertainty model
and $|{\mathcal{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 $(\mathbf{x},s)$ we obtained, we also calculated
$\rho(\mathbf{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 $|{\mathcal{V}}|$ and
$|{\mathcal{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 ($\\#TO$) 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 ($\Delta_{1}$%) and ($\Delta_{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.

Figure 4: Scatter plots for SPP instances with general box uncertainty preferences | $T$ | [$T_{min}$, $T_{max}$] | $\\#TO$ |  $\Delta_{1}$% |  $\Delta_{2}$ %
---|---|---|---|---|---
predi vs. bestc | 131.63 | [26.16, 418.12] | 20 | 61.81 | 16.81
predi vs. regret | 18.48 | [4.51, 72.24] | 9 | 16.15 | 30.38
bestc vs. regret | 115.77 | [9.75, 328.43] | 9 | 3.21 | 20.35
worstc vs. bestc | 91.82 | [3.57, 318.92] | 20 | 14.38 | 13.03
worstc vs. regret | 13.68 | [5.63, 43.56] | 8 | 1.64 | 18.04
worstc vs predi | 5.04 | [1.66, 16.14] | 5 | 2.37 | 9.39
Table 2: Results for instances with general box uncertainty Figure 5: Scatter plots for SPP instances with interval uncertainty preferences | $T$ | [$T_{min}$, $T_{max}$] | $\\#TO$ |  $\Delta_{1}$% |  $\Delta_{2}$ %
---|---|---|---|---|---
predi vs. bestc | 14.89 | [7.76, 28.7] | 19 | 44.87 | 42.95
predi vs. regret | 24.8 | [7.48, 85.56] | 15 | 21.9 | 23.91
bestc vs. regret | 22.35 | [9.24, 75.66] | 9 | 7.25 | 19.73
worstc vs. bestc | 14.0 | [7.56, 47.97] | 9 | 4.12 | 11.29
worstc vs. regret | 20.88 | [8.44, 36.87] | 3 | 2.46 | 6.86
worstc vs predi | 15.44 | [6.8, 55.16] | 12 | 7.12 | 15.78
Table 3: Results for SPP instances with interval uncertainty

##  6 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 also discussed, for relevant special cases,
various reformulations that can be tackled using C-MILP solvers. We applied
this framework to the shortest path problem and (in the appendix) to the
knapsack problem under endogenous uncertainty, providing multiple practical
reformulations applicable under different uncertainty models. We demonstrated
that the respective optimization problems are tractable, using standard
software, and give meaningful results. However, we understand that there are
many open questions regarding this new model, some of which we discuss briefly
in the appendix.

Acknowledgements. The authors want to thank two anonymous referees and an
anonymous Associate Editor for their advice and suggestions to improve upon
earlier versions.

## References

  * [1] W. P. Adams and H. D. Sherali.  A tight linearization and an algorithm for zero-one quadratic programming problems.  Management Science, 32(10):1274–1290, 1986.
  * [2] A. Beck and A. Ben-Tal.  Duality in robust optimization: primal worst equals dual best.  Operations Research Letters, 37(1):1–6, 2009.
  * [3] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski.  Robust optimization.  Princeton University Press, Princeton and Oxford, 2009.
  * [4] A. Ben-Tal, A. Goryashko, E. Guslitzer, and A. Nemirovski.  Adjustable robust solutions of uncertain linear programs.  Mathematical Programming, 99(2):351–376, 2004.
  * [5] D. Bertsimas and D. B. Brown.  Constructing uncertainty sets for robust linear optimization.  Operations Research, 57(6):1483–1495, 2009.
  * [6] D. Bertsimas and M. Sim.  The price of robustness.  Operations Research, 52(1):35–53, 2004.
  * [7] D. Bertsimas and M. Sim.  Robust discrete optimization under ellipsoidal uncertainty sets.  Manuscript, MIT, 9, 2004.
  * [8] M. T. Emmerich and A. H. Deutz.  A tutorial on multiobjective optimization: fundamentals and evolutionary methods.  Natural Computing, 17(3):585–609, 2018.
  * [9] V. Goel and I. E. Grossmann.  A class of stochastic programs with decision dependent uncertainty.  Mathematical Programming, 108(2):355–394, 2006.
  * [10] B. L. Gorissen, I. Yanikoglu, and D. den Hertog.  A practical guide to robust optimization.  Omega, 53:124–137, 2015.
  * [11] L. V. Green, S. Savin, and N. Savva.  “Nursevendor Problem”: Personnel staffing in the presence of endogenous absenteeism.  Management Science, 59(10):2237–2256, 2013.
  * [12] Gurobi Optimization, LLC.  Gurobi optimizer reference manual.  http://www.gurobi.com, 2020.
  * [13] P. Hansen, B. Jaumard, and G. Savard.  New branch-and-bound rules for linear bilevel programming.  SIAM Journal on Scientific and Statistical Computing, 13(5):1194–1217, 1992.
  * [14] T. W. Jonsbraten, R. J. B. Wets, and D. L. Woodruff.  A class of stochastic programs with decision dependent random elements.  Annals of Operations Research, 82:83–106, 1998.
  * [15] P. Kall and S. W. Wallace.  Stochastic Programming.  Springer, Berlin, Germany, 1994.
  * [16] O. E. Karaşan, M. Ç. Pinar, and H. Yaman.  The robust shortest path problem with interval data.  Available at http://www.optimization-online.org/DB_HTML/2001/08/361.html, 2001.
  * [17] P. Kouvelis and G. Yu.  Robust Discrete Optimization and Its Applications.  Kluwer Academic Publishers, Dordrecht, The Netherlands, 1997.
  * [18] N. H. Lappas and C. E. Gounaris.  Robust optimization for decision-making under endogenous uncertainty.  Computers & Chemical Engineering, 111:252–266, 2018.
  * [19] F. Luo and S. Mehrotra.  Distributionally robust optimization with decision dependent ambiguity sets.  Optimization Letters, 14(8):2565–2594, 2020.
  * [20] G. P. McCormick.  Computability of global solutions to factorable nonconvex programs: Part I — convex underestimating problems.  Mathematical Programming, 10(1):147–175, 1976.
  * [21] O. Nohadani and K. Sharma.  Optimization under decision-dependent uncertainty.  SIAM Journal on Optimization, 28(2):1773–1795, 2018.
  * [22] N. Noyan, G. Rudolf, and M. Lejeune.  Distributionally robust optimization with decision-dependent ambiguity set.  Available at http://www.optimization-online.org/DB_HTML/2018/09/6821.html, 2018.
  * [23] Python Software Foundation.  Python: A dynamic, open source programming language.  https://www.python.org/, 2015.
  * [24] R. T. Rockafellar.  Convex analysis.  Princeton University Press, 2015.
  * [25] M. Ryu and R. Jiang.  Nurse staffing under absenteeism: A distributionally robust optimization approach.  arXiv preprint arXiv:1909.09875, 2019.
  * [26] A. Shapiro, D. Dentcheva, and A. Ruszczyński.  Lectures on stochastic programming: modeling and theory.  SIAM, 2014.
  * [27] H. D. Sherali and W. P. Adams.  A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems.  SIAM Journal on Discrete Mathematics, 3(3):411–430, 1990.
  * [28] H. D. Sherali and W. P. Adams.  A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, volume 31 of Nonconvex Optimization and Its Applications.  Springer Science & Business Media, 2013.
  * [29] A. Soyster and F. Murphy.  A unifying framework for duality and modeling in robust linear programs.  Omega, 41(6):984–997, 2013.
  * [30] A. L. Soyster and F. H. Murphy.  On the integration of row and column uncertainty in robust linear programming.  Journal of Global Optimization, 66(2):195–223, 2016.
  * [31] G. Yu and J. Yang.  On the robust shortest path problem.  Computers & Operations Research, 25(6):457–468, 1998.

Appendix

##  Appendix A Generalization from SPP to other network flow problems

Network flow problems problems take the form of
$\inf_{\mathbf{x}}\left\\{\mathbf{c}^{\mathsf{T}}\mathbf{x}\colon{\mathsf{E}}\mathbf{x}\leq\mathbf{b},\
\mathbf{x}\in\left\\{0,1\right\\}^{|{\mathcal{A}}|}\right\\}$ where the matrix
${\mathsf{E}}\in\mathbb{R}^{q\times|{\mathcal{A}}|}$ is parametrized by the
underlying graph, $\mathbf{b}\in\mathbb{R}^{q}$ is a vector of maximal or
minimal net flows at each node and $\mathbf{c}$ is a vector of costs
associated with flows on each arc. Note, that in the aforementioned general
form we have assumed that possible "$\geq$"-constraints have been transformed
by multiplying both sides by $-1$. Network flow problems are, thus,
combinatorial problems which in many special cases allow for an exact LP
relaxation. Specifically, if ${\mathsf{E}}$ is totally unimodular and
$\mathbf{b}$ is a vector of integers, than the LP relaxation is actually
tight. We will now discuss the assumptions under which the above techniques
can be applied to the more general case.

If we assume interval uncertainty of the objective function coefficients, and
furthermore that the LP relaxation of the nominal problem is tight, then the
entire discussion in Section 4.2.1 applies almost verbatim. Specifically, this
is true for the max-regret reformulation as we will show shortly in 8. Also,
if we assume that $\mathbf{b}$ is uncertain, no adoptions are needed for the
modelling of predictability and best-case performance in the objective, since
the latter is independent of $\mathbf{b}$. However, in order to keep 1
applicable we need to assume that $\mathbf{b}$ is also subject to interval
uncertainty: $b_{i}\in[\uline{b}_{i},\bar{b}_{i}]$, $i\in[1\\!:\\!q]$, with
integer $\uline{b}_{i},\bar{b}_{i}$. The robust counterpart is then
$\inf_{\mathbf{x}}\left\\{\uline{\mathbf{c}}^{\mathsf{T}}\mathbf{x}\colon{\mathsf{E}}\mathbf{x}\leq\bar{\mathbf{b}},\
\mathbf{x}\in[0,1]^{|{\mathcal{A}}|}\right\\}$, where $\bar{\mathbf{b}}$ is
the (integer) vector of worst case realization of the uncertain right hand
side. By totally unimodularity we can cast the latter problem as an LP so that
we may use 1 in order characterize ${\mathcal{R}}_{opt}^{s}$. The same
assumption is needed in order to maintain validity of the reformulation of the
regret function in Section 4.2.1 (up to minor adaptations) which we will
demonstrate in 8 at the end of this section.

For correlated box uncertainty with fixed right hand side. the discussion in
Section 4.2.2 applies analogously, however the relaxation used to model the
max-regret function needs to be adapted using the more general techniques
discussed at the beginning of Section 3.1.2. For all other cases, e.g. general
box uncertainty and correlated box uncertainty with uncertain right hand side,
one can apply the techniques from Section 4.3, again with the need to adapt
the max-regret relaxation.

We close the section providing a slight generalization of the reformulation of
the max-regret function from [16], which covers more general network flow
problems and cases with right-hand side uncertainty.

######  Theorem 8.

Assume that for the uncertain linear-binary problem

$\displaystyle\inf_{\mathbf{x}}\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{x}\colon{\mathsf{E}}\mathbf{x}\leq\mathbf{b}(\mathbf{v}),\
\mathbf{x}\in\left\\{0,1\right\\}^{|{\mathcal{A}}|}\right\\}\mbox{ where
}\|\mathbf{u}\|_{\infty}\leq 1,\ \|\mathbf{v}\|_{\infty}\leq 1$

we have interval uncertainty for both the objective and the right hand sides,
i.e.
$(\mathbf{c}(\mathbf{u}))_{i}=c_{i}(u_{i})\in[\underline{c}_{i},\bar{c}_{i}]$
and
$(\mathbf{b}(\mathbf{v}))_{i}=b_{i}(v_{i})\in[\underline{b}_{i},\bar{b}_{i}]$
where $\underline{b}_{i},\bar{b}_{i}$ are integer, $i\in[1\\!:\\!q]$, and that
${\mathsf{E}}$ is totally unimodular. Also, let $\mathbf{c}_{\mathbf{x}}$ be
defined as in Section 4.2.1. Then for any
$\mathbf{x}\in\left\\{0,1\right\\}^{|{\mathcal{A}}|}$ the max-regret function
is given by

$\displaystyle\rho(\mathbf{x})=\min_{\mathbf{z}\in\mathbb{R}^{q+|{\mathcal{A}}|}}\left\\{\bar{\mathbf{c}}^{\mathsf{T}}\mathbf{x}-\left(\uline{\mathbf{b}}^{\mathsf{T}},\mathbf{e}^{\mathsf{T}}\right)\mathbf{z}\colon\left({\mathsf{E}},{\mathsf{I}}\right)^{\mathsf{T}}\mathbf{z}\leq\mathbf{c}_{\mathbf{x}}\right\\}.$

###### Proof of 8.

$\displaystyle\rho(\mathbf{x})$
$\displaystyle=\max_{\mathbf{u},\mathbf{y},\mathbf{v}}\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{x}-\mathbf{c}(\mathbf{u})^{\mathsf{T}}\mathbf{y}\colon{\mathsf{E}}\mathbf{y}\leq\mathbf{b}(\mathbf{v}),\
\mathbf{y}\in\left\\{0,1\right\\}^{|{\mathcal{A}}|},\
\|\mathbf{u}\|_{\infty}\leq 1,\ \|\mathbf{v}\|_{\infty}\leq 1\right\\}$
$\displaystyle=\bar{\mathbf{c}}^{\mathsf{T}}\mathbf{x}-\min_{\mathbf{y},\mathbf{v}}\left\\{\mathbf{c}_{\mathbf{x}}^{\mathsf{T}}\mathbf{y}\colon{\mathsf{E}}\mathbf{y}\leq\mathbf{b}(\mathbf{v}),\
\mathbf{y}\in\left\\{0,1\right\\}^{|{\mathcal{A}}|},\
\|\mathbf{v}\|_{\infty}\leq 1\right\\}$
$\displaystyle=\bar{\mathbf{c}}^{\mathsf{T}}\mathbf{x}-\min_{\mathbf{y},\mathbf{v}}\left\\{\mathbf{c}_{\mathbf{x}}^{\mathsf{T}}\mathbf{y}\colon{\mathsf{E}}\mathbf{y}\leq\underline{\mathbf{b}},\
\mathbf{y}\in\left\\{0,1\right\\}^{|{\mathcal{A}}|}\right\\}$
$\displaystyle=\bar{\mathbf{c}}^{\mathsf{T}}\mathbf{x}-\min_{\mathbf{y},\mathbf{v}}\left\\{\mathbf{c}_{\mathbf{x}}^{\mathsf{T}}\mathbf{y}\colon{\mathsf{E}}\mathbf{y}\leq\underline{\mathbf{b}},\
\mathbf{y}\in[0,1]^{|{\mathcal{A}}|}\right\\}$
$\displaystyle=\bar{\mathbf{c}}^{\mathsf{T}}\mathbf{x}-\max_{\mathbf{z}\mathbb{R}^{q+|{\mathcal{A}}|}}\left\\{\left(\uline{\mathbf{b}}^{\mathsf{T}},\mathbf{e}^{\mathsf{T}}\right)\mathbf{z}\colon\left({\mathsf{E}},{\mathsf{I}}\right)^{\mathsf{T}}\mathbf{z}\leq\mathbf{c}_{\mathbf{x}}\right\\}$

The second equality stems from the fact that for any
$\mathbf{x},\mathbf{y}\in\left\\{0,1\right\\}^{|{\mathcal{A}}|}$ we have

$\displaystyle\max_{\|\mathbf{u}\|_{\infty}\leq
1}\left\\{\mathbf{c}(\mathbf{u})^{\mathsf{T}}(\mathbf{x}-\mathbf{y})\right\\}$
$\displaystyle=\max_{\|\mathbf{u}\|_{\infty}\leq
1}\left\\{\sum_{i=1}^{|{\mathcal{A}}|}c_{i}(u_{i})(x_{i}-y_{i})\right\\}$
$\displaystyle=\sum_{i\in{\mathcal{I}}_{1}}\max_{-1\leq u_{i}\leq
1}\left\\{c_{i}(u_{i})(x_{i}-y_{i})\right\\}+\sum_{i\in{\mathcal{I}}_{0}}\max_{-1\leq
u_{i}\leq 1}\left\\{c_{i}(u_{i})(x_{i}-y_{i})\right\\}$
$\displaystyle=\sum_{i\in{\mathcal{I}}_{1}}\bar{c}_{i}(x_{i}-y_{i})+\sum_{i\in{\mathcal{I}}_{0}}\underline{c}_{i}(x_{i}-y_{i})$
$\displaystyle=\sum_{i\in{\mathcal{I}}_{1}}\bar{c}_{i}(x_{i}-y_{i})-\sum_{i\in{\mathcal{I}}_{0}}\underline{c}_{i}y_{i}=\sum_{i=1}^{|{\mathcal{A}}|}\bar{c}_{i}x_{i}+\sum_{i\in{\mathcal{I}}_{1}}\bar{c}_{i}y_{i}-\sum_{i\in{\mathcal{I}}_{0}}\underline{c}_{i}y_{i}$
$\displaystyle=\bar{\mathbf{c}}^{\mathsf{T}}\mathbf{x}+\mathbf{c}_{\mathbf{x}}^{\mathsf{T}}\mathbf{y},$

where ${\mathcal{I}}_{j}=\left\\{i\colon x_{i}=j\right\\},\ 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 ${\mathsf{E}}$ is totally
unimodular and $\underline{\mathbf{b}}$ is integer and, finally, the fifth
equality holds by linear programming duality. ∎

##  Appendix B Knapsack problems with endogenous $\Gamma$-uncertainty

In this section we will apply our framework to the knapsack problem with
$\Gamma$-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
$\mathbf{c}\in\mathbb{R}^{n}$ be the vector of utilities of the $n$ items, and
let $\mathbf{a}\in\mathbb{R}^{n}$ their weight, then the knapsack problem is
given by
$\max_{\mathbf{x}\in\left\\{0,1\right\\}^{n}}\left\\{\mathbf{c}^{\mathsf{T}}\mathbf{x}\colon\mathbf{a}^{\mathsf{T}}\mathbf{x}\leq
b\right\\}$. 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 $\mathbf{a}_{0}\in\mathbb{R}^{n}$ is restricted by the parameter
$\Gamma\in\mathbb{N}$. Denoting the maximum amount of deviation of item $i$ by
$\bar{a}_{i},\ i\in[1\\!:\\!S]$ our assumptions so far may be formalized as
$(\mathbf{a}(\mathbf{u}))_{i}\coloneqq a^{0}_{i}+\bar{a}_{i}u_{i}$ where
$\mathbf{u}\in{\mathcal{U}}_{\Gamma}\coloneqq\left\\{\mathbf{u}\colon\sum_{i=1}^{n}u_{i}=\Gamma,\
\mathbf{u}\in[0,1]^{n}\right\\}$. 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
$\bar{\mathbf{a}}_{s}\in\mathbb{R}^{n},\ i\in[1\\!:\\!S]$. Under these
assumptions, the knapsack problem under endogenous $\Gamma$-uncertainty is
given by

$\displaystyle\max_{\mathbf{x}\in\left\\{0,1\right\\}^{n}}\left\\{\mathbf{c}^{\mathsf{T}}\mathbf{x}\colon\sum_{i=1}^{n}(a^{0}_{i}+\bar{a}^{s}_{i}u_{i})x_{i}\leq
b\right\\}\quad\mbox{where }\mathbf{u}\in{\mathcal{U}}_{\Gamma},\
s\in[1\\!:\\!S],$

while the endogenously robust counterpart is given by

$\displaystyle\max_{\mathbf{x}\in\left\\{0,1\right\\}^{n},\
s\in[1\\!:\\!S]}\left\\{\mathbf{c}^{\mathsf{T}}\mathbf{x}\colon\mathbf{a}^{\mathsf{T}}\mathbf{x}+\max_{\mathbf{u}}\left\\{\sum_{i=1}^{n}u_{i}\bar{a}^{s}_{i}x_{i}\colon\sum_{i=1}^{n}u_{i}=\Gamma,\
\mathbf{u}\in[0,1]^{n}\right\\}\leq b\right\\}.$

Following the standard reformulation strategy from [6] we arrive at the
deterministic counterpart given by

$\displaystyle\max_{\mathbf{x},\lambda,\bm{\delta},s}\
\mathbf{c}^{\mathsf{T}}\mathbf{x}\hskip 56.9055pt$
$\displaystyle\mathrm{s.t.:}\
\mathbf{a}^{\mathsf{T}}\mathbf{x}+\lambda\Gamma+\bm{\delta}^{\mathsf{T}}\mathbf{e}$
$\displaystyle\leq b,\ \mathbf{x}\in\left\\{0,1\right\\}^{n},\
s\in[1\\!:\\!S],\ \bm{\delta}\in\mathbb{R}^{n}_{+},\ \lambda\in\mathbb{R}\,,$
$\displaystyle\delta_{i}+\lambda$
$\displaystyle\geq\bar{a}^{s}_{i}x_{i},\hskip 28.45274pti\in[1\\!:\\!n]\,.$

Again we pushed the dependence on $s$ into the coefficients $\bar{a}_{i}^{s}$
and the bilinear terms arising from
$\bar{a}^{s}_{i}x_{i}=\sum_{j=1}^{S}\bar{a}^{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 2 for the characterization of ${\mathcal{R}}_{opt}^{s}$ since we
have a combinatorial problem with endogenously uncertain constraints. This
raises the question of how to construct $M_{j},\ j\in[1\\!:\\!S]$, for the
respective constraint from (5). In case of the endogenously uncertain knapsack
problem this constraint is given by
$\mathbf{c}^{\mathsf{T}}\mathbf{x}\geq\varphi_{j}+(1-r^{s}_{j})M_{j},\mbox{
all }j\in[1\\!:\\!S]$, where we had to flip the inequality since we are now
dealing with a maximization problem and we need $M_{j},\ j\in[1\\!:\\!S]$ to
be a upper bound on $\varphi_{\min}-\varphi_{j},\ j\in[1\\!:\\!S]$ with
$\varphi_{\min}\coloneqq\min_{j\in[1\\!:\\!S]}\varphi_{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
$\varphi_{\min}-\varphi_{j},\ j\in[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}=\varphi_{j}$ since zero is a trivial lower bound for the
objective of the knapsack problem. It is therefore not necessary to pre-
calculate $\varphi_{\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
${\mathcal{M}}(\mathbf{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:

######  Theorem 9.

Assume that there is a value for the uncertain parameter such that the
knapsack problem under endogenous $\Gamma$-uncertainty is feasible. Then, the
max-regret function can be upper bounded in the following way

$\displaystyle\rho(\mathbf{x},s)\leq-\mathbf{c}^{\mathsf{T}}\mathbf{x}+\min_{\mu,\bm{\alpha},\bm{\beta},\bm{\gamma},\lambda}\left\\{\mu
b+\lambda\Gamma+\mathbf{e}^{\mathsf{T}}(\bm{\gamma}+\mathbf{t}+\mathbf{s})\colon\begin{array}[]{rl}\mathbf{a}\mu-\bm{\beta}+\bm{\gamma}+\mathbf{t}\geq&\mathbf{c},\\\
\bar{\mathbf{a}}^{s}\mu+\bm{\alpha}+\bm{\beta}-\bm{\gamma}\geq&\mathbf{o},\\\
\mathbf{e}\lambda-\bm{\alpha}+\bm{\gamma}+\mathbf{s}\geq&\mathbf{o},\\\ \
\bm{\alpha},\bm{\beta},\bm{\gamma},\mathbf{t},\mathbf{s}\in&\mathbb{R}^{n}_{+},\
\mu\geq 0\end{array}\right\\}$ (20)

###### Proof.

We have

$\displaystyle\begin{split}\rho(\mathbf{x},s)=&\max_{\mathbf{y},\mathbf{z}}\left\\{\mathbf{c}^{\mathsf{T}}\mathbf{y}-\mathbf{c}^{\mathsf{T}}\mathbf{x}\colon\mathbf{a}^{\mathsf{T}}\mathbf{y}+\sum_{i=1}^{n}z_{i}\bar{a}^{s}_{i}y_{i}\leq
b,\ \sum_{i=1}^{n}z_{i}=\Gamma,\
\mathbf{z}\in[0,1]^{n},\mathbf{y}\in\left\\{0,1\right\\}^{n}\right\\}\\\
=&-\mathbf{c}^{\mathsf{T}}\mathbf{x}+\max_{\mathbf{y},\mathbf{z},\mathbf{u}}\left\\{\mathbf{c}^{\mathsf{T}}\mathbf{y}\colon\begin{array}[]{l}\mathbf{a}^{\mathsf{T}}\mathbf{y}+\sum_{i=1}^{n}\bar{a}^{s}_{i}u_{i}\leq
b,\\\ \sum_{i=1}^{n}z_{i}=\Gamma,\
\mathbf{u}\geq\mathbf{z}+\mathbf{y}-\mathbf{e},\ \mathbf{u}\leq\mathbf{z},\
\mathbf{u}\leq\mathbf{y},\\\
\mathbf{z}\in[0,1]^{n},\mathbf{y}\in\left\\{0,1\right\\}^{n},\mathbf{u}\geq\mathbf{o}\end{array}\right\\}\\\
\leq&-\mathbf{c}^{\mathsf{T}}\mathbf{x}+\max_{\mathbf{y},\mathbf{z},\mathbf{u}}\left\\{\mathbf{c}^{\mathsf{T}}\mathbf{y}\colon\begin{array}[]{l}\mathbf{a}^{\mathsf{T}}\mathbf{y}+\sum_{i=1}^{n}\bar{a}^{s}_{i}u_{i}\leq
b,\\\ \sum_{i=1}^{n}z_{i}=\Gamma,\
\mathbf{u}\geq\mathbf{z}+\mathbf{y}-\mathbf{e},\ \mathbf{u}\leq\mathbf{z},\
\mathbf{u}\leq\mathbf{y},\\\
\mathbf{z}\in[0,1]^{n},\mathbf{y}\in[0,1]^{n},\mathbf{u}\geq\mathbf{o}\end{array}\right\\}\\\
=&-\mathbf{c}^{\mathsf{T}}\mathbf{x}+\min_{\mu,\bm{\alpha},\bm{\beta},\bm{\gamma},\lambda}\left\\{\mu
b+\lambda\Gamma+\mathbf{e}^{\mathsf{T}}(\bm{\gamma}+\mathbf{t}+\mathbf{s})\colon\begin{array}[]{rl}\mathbf{a}\mu-\bm{\beta}+\bm{\gamma}+\mathbf{t}\geq&\mathbf{c},\\\
\bar{\mathbf{a}}^{s}\mu+\bm{\alpha}+\bm{\beta}-\bm{\gamma}\geq&\mathbf{o},\\\
\mathbf{e}\lambda-\bm{\alpha}+\bm{\gamma}+\mathbf{s}\geq&\mathbf{o},\\\ \
\bm{\alpha},\bm{\beta},\bm{\gamma},\mathbf{t},\mathbf{s}\in&\mathbb{R}^{n}_{+},\
\mu\geq 0\end{array}\right\\},\end{split}$ (21)

where the final step follows from linear duality and the fact that we consider
a feasible knapsack problem. ∎

This relaxation may be primitive but in our experiments showed to be off by no
more than 2% at most for the instances we considered. Of course, such a
difference could potentially be troubling in case different uncertainty
regimes give similar regret, but are affected differently by the relaxation
error. For the sake of simplicity, however, we were willing to make this
sacrifice in our experiments.

A notable problem that arises from the above reformulation stems from the term
$\bar{a}^{s}_{i}\mu=\sum_{i=1}^{S}\bar{a}_{i}^{s}r^{s}_{i}\mu$ which is
bilinear in ${\mathbf{r}}_{s}$ and $\mu$. Of course, since ${\mathbf{r}}_{s}$
is a binary vector we can achieve an exact McCormick linearization by
considering,

$\displaystyle\bar{a}^{s}_{i}\mu=\sum_{j=1}^{S}\bar{a}_{i}^{s}r^{s}_{j}\mu=\sum_{i=1}^{S}\bar{a}_{i}^{s}w_{i}\,,\quad
w_{i}=r^{s}_{i}\mu\,,\ \mbox{ all }i\in[1\\!:\\!S]$

where the latter equality is replaced by its McCormick envelope given by

$\displaystyle w_{i}\leq r^{s}_{i}{\overline{M}}_{i}\,,\ w_{i}\geq 0\,,\
w_{i}\leq\mu\,,\ w_{i}\geq\mu-(1-r^{s}_{i}){\overline{M}}_{max}\,,\ \mbox{ all
}i\in[1\\!:\\!S],$

where ${\overline{M}}_{i},\ i\in[1\\!:\\!S]$ are upper bounds on $\mu$ under
uncertainty regime $i\in[1\\!:\\!S]$, while
${\overline{M}}_{max}=\max\left\\{{\overline{M}_{i}}\colon
i\in[1\\!:\\!S]\right\\}$. This construction is necessary since the final
constraint must be redundant for all but the activated uncertainty regimes,
while the first constraints need to be redundant only for the activated
uncertainty regime. The difficulty is the construction of valid upper bounds
which we provide in the following theorem:

######  Theorem 10.

Let $s\in[1\\!:\\!S]$ be fixed and consider the minimization problem in (20)
with $\Gamma<n$. Then for any optimal choice of $\mu^{*}$ we have
$\mu^{*}\leq{\overline{M}}_{i}=\max\left\\{\frac{c_{j}}{a_{j}}\colon
j\in[1\\!:\\!n]\right\\}$, and this bound cannot be improved upon.

###### Proof.

We will argue that the statement is true for any positive $b<a_{1}$ and
conclude the proof by showing that this gives an upper bound for $\mu^{*}$ for
all other positive $b$. So choose numbers $b<a_{1}$ and $\Delta b>0$ such that
still $b+\Delta b<a_{1}$. We can reorder indices $j$ such that
$\frac{c_{1}}{a_{1}}\geq\frac{c_{j}}{a_{j}}$ for all $j\in[1\\!:\\!n]$. Then
the last maximization problem in (20) has as a feasible solution
$\mathbf{y}=\frac{b}{a_{1}}\,\mathbf{e}_{1}$,
$\mathbf{z}=\sum_{j=n-\Gamma}^{n}\mathbf{e}_{j}$, $\mathbf{u}=\mathbf{o}$,
with objective function value $\frac{bc_{1}}{a_{1}}$. The problem
$\max_{\mathbf{y}\geq
0}\left\\{\mathbf{c}^{\mathsf{T}}\mathbf{y}\colon\mathbf{a}^{\mathsf{T}}\mathbf{y}\leq
b\right\\}=\frac{bc_{1}}{a_{1}}$ is a relaxation, hence the aforementioned
feasible solution is actually optimal. Replacing $b$ by $b+\Delta b$ does not
change above construction whenever the right-hand side $b+\Delta 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
$\mathbf{a}^{\mathsf{T}}\mathbf{y}\leq b+\Delta b$ is again binding at
$\mathbf{y}$). Thus, for the optimal choice $\mu^{*}$, the difference of dual
optimal values (by strong duality, equalling the difference of the primal-
optimal values) is

$\mu^{*}\Delta
b=\max_{\mathbf{y},\mathbf{u},\mathbf{z}}\left\\{\mathbf{c}^{\mathsf{T}}\mathbf{y}\colon\mathbf{a}^{\mathsf{T}}\mathbf{y}+\mathbf{a}_{s}^{\mathsf{T}}\mathbf{u}\leq
b+\Delta
b,\dots\right\\}-\max_{\mathbf{y},\mathbf{u},\mathbf{z}}\left\\{\mathbf{c}^{\mathsf{T}}\mathbf{y}\colon\mathbf{a}^{\mathsf{T}}\mathbf{y}+\mathbf{a}_{s}^{\mathsf{T}}\mathbf{u}\leq
b,\dots\right\\}=\frac{c_{1}\Delta b}{a_{1}}$

so that $\mu^{*}=\frac{c_{1}}{a_{1}}=\max_{j}\left\\{\frac{c_{j}}{a_{j}}\colon
j\in[1\\!:\\!n]\right\\}$ whenever $b\in(0,a_{1})$. We will now show that this
gives an upper bound for all other values $b\geq 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_{(\mu;\bar{\bm{\mu}})\geq\mathbf{o}}\left\\{b_{i}\mu+\bar{\mathbf{b}}^{\mathsf{T}}\bar{\bm{\mu}}\colon\mathbf{a}\mu+{\mathsf{B}}\bar{\bm{\mu}}\geq\mathbf{c}\right\\}$
for $i=1,2$ with $b_{1}<b_{2}$, and their respective optimal solutions
$(\mu_{1}^{*},\bar{\bm{\mu}}_{1}^{*})$ and
$(\mu_{2}^{*},\bar{\bm{\mu}}_{2}^{*})$. Assume that $\mu_{2}^{*}>\mu_{1}^{*}$.
Since both solutions are feasible for either problem we have
$b_{2}\mu_{1}^{*}+\bar{\mathbf{b}}^{\mathsf{T}}\bar{\bm{\mu}}_{1}^{*}\geq
b_{2}\mu_{2}^{*}+\bar{\mathbf{b}}^{\mathsf{T}}\bar{\bm{\mu}}_{2}^{*}$ which
implies

$\bar{\mathbf{b}}^{\mathsf{T}}(\bar{\bm{\mu}}_{1}^{*}-\bar{\bm{\mu}}_{2}^{*})\geq
b_{2}(\mu_{2}^{*}-\mu_{1}^{*})>b_{1}(\mu_{2}^{*}-\mu_{1}^{*})$

by $\mu_{2}^{*}>\mu_{1}^{*}$ and $b_{1}<b_{2}$. This yields the final
contradiction
$b_{1}\mu_{1}^{*}+\bar{\mathbf{b}}^{\mathsf{T}}\bar{\bm{\mu}}_{1}^{*}>b_{1}\mu_{2}^{*}+\bar{\mathbf{b}}^{\mathsf{T}}\bar{\bm{\mu}}_{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 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.

$\displaystyle\begin{split}&\max_{\mathbf{x},s,{\overline{q}},\underline{q}}\left\\{\gamma_{s}+\alpha\mathbf{c}^{\mathsf{T}}\mathbf{x}-\beta({\overline{q}},\underline{q})\right\\}\\\
\mathrm{s.t.:}\
&{\overline{q}}\geq\mathbf{a}^{\mathsf{T}}\mathbf{x}+\max_{\mathbf{u}}\left\\{\sum_{i=1}^{n}u_{i}\bar{a}^{s}_{i}x_{i}\colon\sum_{i=1}^{n}u_{i}=\Gamma,\
\mathbf{u}\in[0,1]^{n}\right\\},\\\
&\underline{q}\leq\mathbf{a}^{\mathsf{T}}\mathbf{x}+\min_{\mathbf{u}}\left\\{\sum_{i=1}^{n}u_{i}\bar{a}^{s}_{i}x_{i}\colon\sum_{i=1}^{n}u_{i}=\Gamma,\
\mathbf{u}\in[0,1]^{n}\right\\},\\\ &\mathbf{x}\in{\mathcal{R}}^{s}_{opt}\,,\
s\in[1\\!:\\!S]\,,\left(\mathbf{c}^{\mathsf{T}}\mathbf{x}\leq\varphi^{*}+\varepsilon\right).\end{split}$

Again making use of the equality

$\displaystyle\max\left\\{\mathbf{g}^{\mathsf{T}}\mathbf{z}:\
\mathbf{e}^{\mathsf{T}}\mathbf{z}=\Gamma,\ \mathbf{z}\leq\mathbf{e},\