$\Gamma$–counterparts for robust nonlinear combinatorial and discrete
optimization Adelhütte and Liers $\Gamma$–counterparts for robust MINLPs
Dennis Adelhütte, Frauke Liers Friedrich–Alexander–Universität
Erlangen–Nürnberg, Department Data Science, Cauerstraße 11, 91058 Erlangen
<EMAIL_ADDRESS><EMAIL_ADDRESS>1

$\Gamma$–uncertainty sets have been introduced for adjusting the degree of
conservatism of robust counterparts of (discrete) linear programs. The
contribution of this paper is a generalization of this approach to
(mixed–integer) nonlinear optimization programs. We focus on the cases in
which the uncertainty is linear or concave but also derive formulations for
the general case. By applying reformulation techniques that have been
established for nonlinear inequalities under uncertainty, we derive equivalent
formulations of the robust counterpart that are not subject to uncertainty.
The computational tractability depends on the structure of the functions under
uncertainty and the geometry of its uncertainty set. We present cases where
the robust counterpart of a nonlinear combinatorial program is solvable with a
polynomial number of oracle calls for the underlying nominal program.
Furthermore, we present robust counterparts for practical examples, namely for
(discrete) linear, quadratic and piecewise linear settings.

nonlinear programming, integer programming, nonlinear integer programming

##  1 Introduction

In recent years, optimization under uncertainty has gained importance and
popularity. When an optimization program is subject to uncertainty, one can
aim to solve it before all data are known – sometimes, this is even mandatory.
Two fields of research how to treat said uncertainties are stochastic and
robust optimization. In stochastic optimization, one usually requires a
sufficient amount of data to estimate or determine the underlying probability
distribution. For further information on this, we refer the reader to the
monograph Stochastic. For robust optimization, one does not require
probability distributions. Instead, for modeling the real–life situation, an
uncertainty set is pre–determined and one optimizes over the variables while
taking the uncertainty set into account simultaneously. Several approaches in
robust optimization have been conducted in the past decades, especially in the
field of (mixed–integer) linear programming. However, for combinatorial
optimization, those are usually not applicable since the underlying program’s
structure is changed, rendering solution algorithms for the nominal problem
not applicable. To circumvent this, Bertsimas and Sim introduced
$\Gamma$–uncertainty sets in IntroGamma and PriceRobust for combinatorial
optimization under interval uncertainty in a linear objective. Since recent
research has focused on nonlinear robust optimization programming, we extend
their approach for combinatorial and discrete programming with nonlinearities.

#### Contribution:

We propose and study a generic framework for mixed–integer nonlinear programs
(MINLPs) under uncertainties that generalizes the $\Gamma$–uncertainties for
mixed–integer linear programs (MIPs) in IntroGamma and PriceRobust. We focus
on objective uncertainty: On the one hand, we provide reformulations, in
particular for the case of nonlinear, concave and linear uncertainty. On the
other hand, we show that the programs

$\displaystyle\min_{x\in\mathcal{X}}u^{T}Bg(x)$ (1)

underlying an ’assignment structure’ and

$\displaystyle\min_{x\in\mathcal{X}}u^{T}l(x)$ (2)

where $l$ is a $0/1$–function1\. 1\. endnote: 1\. We call a function $l\colon
M\to N$ a $0/1$–function when $l(x)\in\\{0,1\\}$ for all $x\in M$. and, in
both cases, $u$ is a vector of uncertain parameters in
$[\overline{u},\overline{u}+\Delta u]$ can be solved by a polynomial number of
oracle calls (With an oracle, we henceforth mean a black box that can solve
the original program without uncertainties). To be more precise, we conduct
the following:

  1. 1.

Programs with concave uncertainty can be reformulated into programs including
support functions and concave conjugations. If the uncertainty is linear, then
support functions are sufficient.

  2. 2.

A black box for solving the program without uncertainty is sufficient for
solving programs either (1) or (2) under $\Gamma$–uncertainty with intervals.

  3. 3.

We propose a new model to handle deadline uncertainty with
$\Gamma$–uncertainty sets and show its computational tractability.

  4. 4.

Our model unifies several applications of $\Gamma$–uncertainty sets in the
literature.

In our appendix, we demonstrate the practical applicability of our presented
reformulations for the quadratic assignment problem (QAP, QAPintro) and a
special case of the vehicle routing problem with general time windows (VRPGTW,
VRPSTW), both under $\Gamma$–uncertainty, in terms of a prototypical numerical
study. Uncertainty in the constraints can be handled analogously and is also
briefly discussed in the electronic companion. In total, our goal is to
present a unifying framework for nonlinear optimization under uncertainty that
is of interest for future research, in particular the combination of
combinatorial optimization and nonlinear programming under uncertainty.

#### Outline:

The paper is structured as follows. In Section 2, we briefly revisit the the
oracle–polynomial reformulation of the $\Gamma$–counterpart from IntroGamma
before we introduce the $\Gamma$–counterpart for MINLPs. We motivate our
generalization with several applications. In Section 3, we obtain
reformulations of our robust counterparts and demonstrate our main results by
showing and show that in special cases, oracle–polynomiality holds. In Section
4, we present various examples and applications of our results with a focus on
quadratic problems under uncertainty. Finally, in Section 5, we provide a
conclusion and propose some interesting avenues for research. In our electric
electronic companion, we demonstrate the case of uncertain constraints and a
prototypical numerical study for the QAP and the VRPGTW under
$\Gamma$–uncertainty.

#### Literature review:

A first discussion of a program subject to uncertainty has been conducted by
Soyster Soyster for column–wise uncertainty of a constraint matrix where the
uncertainty set is a convex set. To deal with the resulting over–conservatism,
several approaches have been introduced in the literature. In ben-tal1 and
ben-tal3, the authors have presented and discussed linear programs under
uncertainty from a theoretical and a practical point of view, focusing on
convex/interval uncertainties, respectively. The case of reformulating
convex/concave rather than linear functions under uncertainty has been
addressed in ben-tal2. A framework for treating robust programming with
reformulation approaches is RobustBook. Another approach for treating
uncertainties is the adversarial approach presented in ApplDec2 that, instead
of reformulating, tries to iteratively add scenarios of the uncertainty to the
nominal program, finds optimal solutions and checks whether the found
solutions are already robust. The approaches are compared in BertsimasCutting.
For broad overviews of robust optimization in a theoretical and applied sense,
we refer to the surveys survey2011, survey2014 and SurveyAdj. In the context
of combinatorial/discrete programs under uncertainty, we reference
Kouvelis_1997 as the first framework and the surveys RobCombOpt and
Kasperski2016 that tackle interval, discrete and convex uncertainties in the
objective. $\Gamma$–uncertainties were introduced in PriceRobust and applied
to combinatorial programs in IntroGamma. Throughout the last two decades, they
have been generalized and extended. In BusingBand and in Fischetti2009, new
uncertainty concepts, namely multi–band uncertainty and light robustness,
based on $\Gamma$–uncertainties, have been introduced. In Poss12, Poss14 and
POSS2018, uncertainty sets that generalized $\Gamma$–uncertainty sets were
introduced. Furthermore, Buesing2019 discussed $\Gamma$–uncertainty sets in
the context of global robust optimization and Goerigk2021 introduced locally
budgeted uncertainty sets. Finally, $\Gamma$–uncertainty sets have also been
applied in a dynamic robust sense, e.g. in ApplicationBudget. Optimization
under uncertainties including nonlinearities are fairly new in the literature.
For an overview over theory, solution approaches and applications, we refer to
NonlinearRO. The reformulation techniques that our framework is based on have
been derived in Fenchel.

Finally, for our applications, we refer to the following sources. The QAP
under uncertainty was discussed in QAP2015, QAP2012 and QAM. The VRPTGW under
uncertainty is motivated by the patient transport problem described in Dummies
and based on the VRPGTW described in VRPSTW. To the best of our knowledge, the
aforementined $\Gamma$–uncertainty set for piecewise linear objective
functions is new in the literature, although piecewise linear functions under
uncertainty have been discussed e.g. in ApplPWL2013 and Gorissen_2013.

##  2 Our modeling framework

###  2.1 Revisiting $\Gamma$–uncertainties for binary programs

Since our focus lies on reformulations of robust counterparts, we revisit a
reformulation result of IntroGamma. We consider a combinatorial program with
cost vector $\overline{c}\in\mathbb{R}^{n}$ and feasible set
$\mathcal{X}\subseteq\\{0,1\\}^{n}$:

$\displaystyle\begin{split}\min_{x\in\mathcal{X}}&\ \overline{c}^{T}x.\\\
\end{split}$ (3)

We assume that the cost coefficients are subject to interval uncertainty,
i.e., $c_{i}\in[\overline{c}_{i},\overline{c}_{i}+\Delta c_{i}]$ for a given
$\Delta c_{i}\geq 0$ for all $i\in[n]:=\\{1,\dots,n\\}$. We aim to find
solutions that are robust against at most $\Gamma\in[n]$ coefficients
deviating from their nominal scenario $\overline{c}_{i}$:

$\displaystyle\min_{x\in\mathcal{X}}\
\left\\{\overline{c}^{T}x+\max_{\mathcal{S}\subseteq[n]:\left|\mathcal{S}\right|\leq\Gamma}\left\\{\sum_{i\in\mathcal{S}}\Delta
c_{i}x_{i}\right\\}\right\\}.$ (4)

In IntroGamma, Bertsimas and Sim have shown that the optimal solutions of
program (4) can be found by applying an optimization oracle of program (3):

###### Proposition

(IntroGamma, Theorem 3) Assume that $\mathcal{X}\subseteq\\{0,1\\}^{n}$ and
set $\Delta c_{0}:=0$. Then program (4) is equivalent to

$\displaystyle\min_{k\in[n]_{0}}\left\\{\Gamma\Delta
c_{k}+\min_{x\in\mathcal{X}}\left\\{\overline{c}^{T}x+\sum_{j\in[n]}\max\\{0,\Delta
c_{j}-\Delta c_{k}\\}x_{j}\right\\}\right\\}$ (5)

where $[n]_{0}:=\\{0,1,\dots,n\\}$.

Proposition 2.1 implies that program (4) can be solved to optimality in
oracle–polynomial time, assuming that an oracle for program (3) is at hand. We
note that it is crucial that $\mathcal{X}\subseteq\\{0,1\\}^{n}$. If
$\mathcal{X}=\\{x\in\mathbb{Z}^{p}\times\mathbb{R}^{n-p}:\ Ax\leq b,\
x\in[r,s]\\}$ for $r,s\in\mathbb{R}^{n}$ and $p\in[n]$, then one can
reformulate the robust counterpart as a computationally tractable MIP but has
to introduce additional variables while losing the structure of the original
program. Thus, the oracle for solving program (4) is in general not
applicable. For details, we refer the reader to the proofs in IntroGamma.

###  2.2 Introduction of our model and applications

In this subsection, we extend program (4) to MINLPs that are subject to
uncertainty in the objective. We consider the program

$\displaystyle\begin{split}\inf_{x\in\mathcal{X}}&\sum_{i\in[m]}\
\overline{f}_{i}(x),\end{split}$ (6)

where $\overline{f}_{i}\colon\mathbb{R}^{n}\to\mathbb{R}$ is an arbitrary but
fixed function for every $i\in[m]$ and
$\mathcal{X}\subseteq\mathbb{Z}^{p}\times\mathbb{R}^{n-p}$ where
$p\in[n]_{0}$. We assume that every function $\overline{f}_{i}$ is
’contaminated’ by an uncertainty set
$\mathcal{U}_{i}\subseteq\mathbb{R}^{L_{i}}$, i.e., we define
$f_{i}\colon\mathbb{R}^{n}\times\mathcal{U}_{i}\to\mathbb{R}$ with
$f_{i}(x,\overline{u}^{i}):=\overline{f}_{i}(x)$ for a nominal scenario
$\overline{u}^{i}\in\mathcal{U}_{i}$ and $L_{i}$ is the dimension of the
uncertain parameter $u^{i}\in\mathcal{U}_{i}$. We focus on the uncorrelated
case, i.e., we assume that uncertainties of different functions $f_{i}$ are
uncorrelated, i.e., the uncertainty set of $\sum_{i\in[m]}f_{i}(x,u^{i})$ is
$\mathcal{U}:=\bigtimes_{i\in[m]}\mathcal{U}_{i}$. This ensures that the
different uncertainty sets $\mathcal{U}_{i}$ have no influence on each other.
Hence the robust counterpart of program (6) without ’restricting’
$\mathcal{U}$ further is

$\displaystyle\begin{split}\inf_{x\in\mathcal{X}}&\sum_{i\in[m]}\
\sup_{u^{i}\in\mathcal{U}_{i}}f_{i}(x,u^{i}).\end{split}$ (7)

We say that, if $\mathcal{U}^{i}$ is convex and
$f_{i}(x,\cdot):\mathcal{U}^{i}\to\mathbb{R}$ is concave for every
$x\in\mathcal{X}$, then the uncertainty is concave. Furthermore, if there
exists a function $l_{i}\colon\mathcal{X}\to\mathbb{R}^{L_{i}}$ with
$f_{i}(x,u^{i})=(u^{i})^{T}l_{i}(x)$ for every
$x\in\mathcal{X},u^{i}\in\mathcal{U}^{i}$, we call the uncertainty linear.
To reduce over–conservatism, we aim to be robust against at most $\Gamma$
functions deviating from their nominal scenario and obtain the following:

$\displaystyle\inf_{x\in\mathcal{X}}$
$\displaystyle\left\\{\sup_{\mathcal{S}\subseteq[m]:|\mathcal{S}|\leq\Gamma}\left\\{\sum_{i\in\mathcal{S}}\sup_{u^{i}\in\mathcal{U}_{i}}f_{i}(x,u^{i})+\sum_{i\in[m]\setminus\mathcal{S}}f_{i}(x,\overline{u}^{i})\right\\}\right\\}.$
(8)

Program (8) is henceforth referred to as the $\Gamma$-counterpart of program
(6). Naturally, it is more general than (4). To demonstrate that this
generalization is natural, we consider linear uncertainties: Assume that
$f_{i}$ is subject to linear uncertainty for every $i\in[m]$ and that
$\mathcal{U}^{i}$ is convex and compact. Then there exists
$w^{i}\in\mathcal{U}^{i}$, such that
$\sup_{u^{i}\in\mathcal{U}^{i}}f_{i}(x,u^{i})=f_{i}(x,w^{i})\in\mathbb{R}$.
Then we obtain

$\displaystyle\eqref{Prob:GeneralGammaCounterpart}$
$\displaystyle=\inf_{x\in\mathcal{X}}\left\\{\sup_{\mathcal{S}\subseteq[m]:|\mathcal{S}|\leq\Gamma}\left\\{\sum_{i\in\mathcal{S}}f_{i}(x,w^{i})+\sum_{i\in[m]\setminus\mathcal{S}}f_{i}(x,\overline{u}^{i})\right\\}\right\\}$
$\displaystyle=\inf_{x\in\mathcal{X}}\left\\{\sup_{\mathcal{S}\subseteq[m]:|\mathcal{S}|\leq\Gamma}\left\\{\sum_{i\in\mathcal{S}}f_{i}(x,w^{i})-f_{i}(x,\overline{u}^{i})+\sum_{i\in[m]}f_{i}(x,\overline{u}^{i})\right\\}\right\\}$
$\displaystyle=\inf_{x\in\mathcal{X}}\left\\{\sum_{i\in[m]}f_{i}(x,\overline{u}^{i})+\sup_{\mathcal{S}\subseteq[m]:|\mathcal{S}|\leq\Gamma}\left\\{\sum_{i\in\mathcal{S}}f_{i}(x,w^{i}-\overline{u}^{i})\right\\}\right\\}$
$\displaystyle=\inf_{x\in\mathcal{X}}\left\\{\sum_{i\in[m]}f_{i}(x,\overline{u}^{i})+\sup_{\mathcal{S}\subseteq[m]:|\mathcal{S}|\leq\Gamma}\left\\{\sum_{i\in\mathcal{S}}\sup_{z^{i}\in\mathcal{U}_{i}-\overline{u}^{i}}f_{i}(x,z^{i})\right\\}\right\\}.$

In particular, if $\mathcal{U}_{i}=[\overline{u}_{i},\overline{u}_{i}+\Delta
u_{i}]\subseteq\mathbb{R}_{\geq 0}$ and $f_{i}(x,u_{i})=u_{i}x_{i}\geq 0$ for
all $u_{i}\in\mathcal{U}_{i}$, then

$\displaystyle\sup_{z_{i}\in\mathcal{U}_{i}-\overline{u}_{i}}f_{i}(x,z_{i})=\Delta
u_{i}x_{i}$

and one obtains program (4).
Before we continue with our discussion for handling the $\Gamma$–counterpart
in Section 3, we present some application examples.

#### Single–machine scheduling under uncertainty.

This application was firstly discussed under uncertainty in RobustScheduling
and Tadayon2015. A set of $m$ jobs $\mathcal{J}$ must be scheduled on a single
machine. The machine requires a processing time
$\overline{p}_{j}\in\mathbb{R}_{\geq 0}$ to finish job $j\in\mathcal{J}$
without preemption. The completion time of job $j$ that depends on the
schedule $x$ and on the processing time
$\overline{p}:=(\overline{p}_{j})_{j\in\mathcal{J}}$ is denoted by
$C_{j}(x,\overline{p})$. With $\mathcal{X}$, we denote the set of feasible
schedules (the binary variable $x_{i,j}$ indicates whether job $j$ is
scheduled at position $i$):

$\displaystyle\mathcal{X}:=\left\\{x\in\\{0,1\\}^{[m]\times|\mathcal{J}|}:\sum_{i\in[m]}x_{i,j}=1\
\forall j\in\mathcal{J},\ \sum_{j\in\mathcal{J}}x_{i,j}=1\ \forall
i\in[m]\right\\}.$

Assuming that every job $j$ contributes weight $w_{j}\in\mathbb{R}_{\geq 0}$
to the objective, we aim to minimize the total completion time:

$\displaystyle\min_{x\in\mathcal{X}}\sum_{j\in\mathcal{J}}C_{j}(x,\overline{p}).$
(9)

Program (9) is equivalent to

$\displaystyle\min_{x\in\mathcal{X}}\sum_{j\in\mathcal{J}}\overline{p}_{j}\sum_{i\in[m]}(m+1-i)x_{i,j}.$
(10)

If the processing time $p_{j}$ is subject to uncertainty
$\mathcal{U}_{j}=[\overline{p}_{j},\overline{p}_{j}+\Delta p_{j}]$ for each
job $j\in\mathcal{J}$, then the $\Gamma$–counterpart (8) of program (10) is

$\displaystyle\min_{x\in\mathcal{X}}\left\\{\sum_{j\in\mathcal{J}}\overline{p}_{j}\sum_{i\in[m]}(m+1-i)x_{i,j}+\max_{\mathcal{S}\subseteq\mathcal{J}:|\mathcal{S}|\leq\Gamma}\left\\{\sum_{j\in\mathcal{S}}\Delta
p_{j}\sum_{i\in[m]}(m+1-i)x_{i,j}\right\\}\right\\}$ (11)

since the uncertainty is linear.
While program (11) looks very similar to (4), there is an important
difference: The variables $x_{i,j}$ are not multiplied with exactly one
coefficient but each uncertain parameter $p_{j}$ is multiplied with a linear
combination of the variables $x_{i,j}$ for fixed $j\in\mathcal{J}$. Thus, the
objective of the nominal program (10) is linear in $p$ and in $x$ but has the
form $\min_{x\in\mathcal{X}}u^{T}Bx$ for a real matrix $B$ instead of
$\min_{x\in\mathcal{X}}u^{T}x$. Thus, Proposition 2.1 and the original results
of IntroGamma cannot be applied.

#### Quadratic assignment problem under uncertainty.

The QAP models the process of assigning $n\in\mathbb{N}$ facilities to $n$
locations such that the cost of transporting goods is minimized. With binary
variables $x_{i,r}$, $i,r\in[n],$ that indicate whether facility $i$ is
assigned to location $r$, the feasible set can be modeled as

$\displaystyle\mathcal{X}=\left\\{x\in\\{0,1\\}^{[n]^{2}}:\sum_{i\in[n]}x_{i,r}=1\
\forall r\in[n],\sum_{r\in[n]}x_{i,r}=1\ \forall i\in[n]\right\\}.$

For each pair of facilities $(i,j)\in[n]^{2}$, $c_{i,j}\geq 0$ denotes the
flow between $i$ and $j$ and for all pair of locations $(r,s)\in[n]^{2}$,
$d_{r,s}\geq 0$ denotes the distance between $r$ and $s$. Thus, the QAP can be
modeled with

$\displaystyle\min_{x\in\mathcal{X}}\sum_{(i,j,r,s)\in[n]^{4}}c_{i,j}d_{r,s}x_{i,r}x_{j,s}.$

In QAP2015, the authors have assumed that the flow is subject to interval
uncertainty. Their goal was to obtain solutions that are robust against at
most $\Gamma$ deviations from the nominal scenario: We seek protection against
uncertainties in $c_{i,j}$ that are modeled by a perturbation of at most
$\Delta c_{i,j}\geq 0$ for all $(i,j)\in[n]^{2}$, i.e.,
$c_{i,j}\in\mathcal{U}_{i,j}=[\overline{c}_{i,j},\overline{c}_{i,j}+\Delta
c_{i,j}]$. The $\Gamma$-counterpart (8) is, since the uncertainty is linear,
given by:

$\displaystyle\begin{split}&\min_{x\in\mathcal{X}}\left\\{\sum_{(i,j,r,s)\in[n]^{4}}\overline{c}_{i,j}d_{r,s}x_{i,r}x_{j,s}+\max_{\mathcal{S}\subseteq[n]^{2}:|\mathcal{S}|\leq\Gamma}\left\\{\sum_{(i,j)\in\mathcal{S}}\sum_{r,s\in[n]}\Delta\overline{c}_{i,j}d_{r,s}x_{i,r}x_{j,s}\right\\}\right\\}.\end{split}$
(12)

#### Logistics with deadline uncertainties.

Problems occuring in the application of logistics involving deliveries within
given due times can often be modeled as combinatorial programs with
(non–)linear objective functions, e.g. taxi routing, delivery of goods or
patient transport. For all three of these cases, being on time is important
for customer satisfaction. At the same time, it is usually not problematic
when vehicle arrives too early for a pick–up.
For tasks $i\in[m]$, we denote the due time with $b_{i}\in\mathbb{R}$. If a
job is finished after $b_{i}$, then penalty costs occur. A program for
(unweighted) penalty costs is

$\displaystyle\begin{split}\inf_{x\in\mathcal{X}}&\
\sum_{i\in[m]}\max\\{0,x_{i}-b_{i}\\}.\end{split}$ (13)

Program (13) may arise in transportation logistics, for example as a special
case of vehicle routing problems with general time windows, see VRPSTW. In
practice, the due time can be uncertain: We assume that
$b_{i}\in\mathcal{U}_{i}:=[\overline{b}_{i}-\Delta b_{i},\overline{b}_{i}]$
for some nominal scenario $\overline{b}_{i}$ and a perturbation $\Delta
b_{i}$. To reduce conservatism, the objective is to ensure robustness against
$\Gamma$ deviations of the due times, resulting in the following program:

$\displaystyle\begin{split}\inf_{x\in\mathcal{X}}&\
\left\\{\sup_{\mathcal{S}\subseteq[m]:|\mathcal{S}|\leq\Gamma}\left\\{\sum_{i\in\mathcal{S}}\max\\{0,x_{i}-\overline{b}_{i}+\Delta
b_{i}\\}+\sum_{i\in[m]\setminus\mathcal{S}}\max\\{0,x_{i}-\overline{b}_{i}\\}\right\\}\right\\}.\end{split}$
(14)

Problem (14) is obtained from $\Gamma$–counterpart (8) by setting
$f_{i}(x,b):=\max\\{0,x_{i}-b_{i}\\}$.

##  3 Reformulations for programs with uncertain objectives

In this section, we present equivalent reformulations for the
$\Gamma$–counterpart introduced in Section 2.2. Several of the proofs are
inspired by those in IntroGamma. It turns out that it is possible to obtain
first reformulations of $\Gamma$– counterpart (8) without any assumptions on
the functions $f_{i}$ or the uncertainty sets $\mathcal{U}^{i}$.

######  Lemma 3.1.

Let $\Gamma\in[m]$. Then $\Gamma$–counterpart (8) is equivalent to

$\displaystyle\begin{split}\inf_{x,p,\theta}&\
\Gamma\theta+\sum_{i\in[m]}f_{i}(x,\overline{u}^{i})+p_{i},\\\
\mathrm{s.t.\;}&x\in\mathcal{X},\\\
&p_{i}+\theta\geq\sup_{u^{i}\in\mathcal{U}_{i}}f_{i}(x,u^{i})-f_{i}(x,\overline{u}^{i})\
\forall i\in[m],\\\ &p\in\mathbb{R}^{m}_{\geq 0},\theta\in\mathbb{R}_{\geq
0}.\end{split}$ (15)

######  Proof 3.2.

Proof. The structure of the proof is similar to the proof of Theorem 3 in
IntroGamma. With the binary variables

$\displaystyle s_{i}:=\begin{cases}1,\text{ if $i\in\mathcal{S}$,}\\\ 0,\text{
otherwise,}\\\ \end{cases}$

$i\in[m]$, the inner maximization program of $\Gamma$–counterpart (8) is
equivalent to

$\displaystyle\begin{split}\sup_{s}&\
\sum_{i\in[m]}f_{i}(x,\overline{u}^{i})+s_{i}(\sup_{u^{i}\in\mathcal{U}_{i}}f_{i}(x,u^{i})-f_{i}(x,\overline{u}^{i})),\\\
\text{s.t.}&\ \sum_{i\in[m]}s_{i}\leq\Gamma,\\\ &\
s\in\\{0,1\\}^{m}.\end{split}$ (16)

Clearly, program (16) is equivalent to its LP relaxation. Inserting its dual
into $\Gamma$–counterpart (8) proves the claim.

In Lemma 3.1, to obtain a tractable formulation, it is necessary to
reformulate the inequality

$\displaystyle
p_{i}+\theta\geq\sup_{u^{i}\in\mathcal{U}_{i}}f(x,u^{i})-f(x,\overline{u}^{i})$
(17)

for all $i\in[m]$. In Fenchel, the authors proposed various approaches,
especially for linear/concave uncertainties which will be discussed in the
subsequent subsections. We demonstrate one approach for the non–concave case
that uses the notion of term–wise parallel vectors for a non–convex quadratic
program in Section 4. For other approaches, we refer to Fenchel and
NonlinearRO.

Furthermore, one can reformulate program (15) to obtain a program with
feasible set $\mathcal{X}$ and without variables $p$ and $\theta$:

######  Lemma 3.3.

If $\Gamma\in[m]$, then $\Gamma$–counterpart (8) is equivalent to

$\displaystyle\begin{split}\inf_{k\in[m]_{0}}&\left\\{\inf_{x\in\mathcal{X}}\left\\{\Gamma\theta^{k}(x)+\sum_{i\in[m]}f_{i}(x,\overline{u}^{i})+\sup\\{0,\theta^{i}(x)-\theta^{k}(x)\\}\right\\}\right\\},\\\
\end{split}$ (18)

where
$\theta^{k}(x):=\sup_{u^{k}\in\mathcal{U}_{k}}f_{k}(x,u^{k})-f_{k}(x,\overline{u}^{k})$
and $\theta^{0}(x):=0$.

######  Proof 3.4.

Proof. Since $\Gamma\in[m]$, $\Gamma$–counterpart (8) is equivalent to (15).
Since for all $i\in[m]$, $p_{i}$ only occurs in exactly one inequality, we
obtain

$\displaystyle
p^{*}_{i}=\sup\\{0,\sup_{u^{i}\in\mathcal{U}_{i}}f_{i}(x^{*},u^{i})-f_{i}(x^{*},\overline{u}^{i}))-\theta^{*}\\}\
\forall i\in[m]$ (19)

for an optimal solution $(x^{*},p^{*},\theta^{*})$ of (15). Inserting equation
(19) into the objective function of (15) results in

$\displaystyle\Gamma\theta+\sum_{i\in[m]}f_{i}(x,\overline{u}^{i})+\sup\\{0,\sup_{u^{i}\in\mathcal{U}_{i}}f_{i}(x,u^{i})-f_{i}(x,\overline{u}^{i}))-\theta\\}.$
(20)

Since $\eqref{Eq:piecewiselinearlem}$ is convex and piecewise linear in
$\theta$, either $\theta^{*}=0$ or $\theta^{*}=\theta^{k}(x)$ for one
$k\in[m]$.

###  3.1 Concave Uncertainties

In this subsection, we will focus on programs that fulfill the following
assumptions: For $\Gamma$–counterpart (8) and for all $i\in[m]$ we assume:

  * (i)

There is a nominal scenario $\overline{u}^{i}\in\mathbb{R}^{L_{i}}$, a matrix
$A^{i}\in\mathbb{R}^{L_{i}\times m_{i}}$ and a convex set
$\mathcal{Z}_{i}\subseteq\mathbb{R}^{m_{i}}$, such that
$\mathcal{U}_{i}=\\{\overline{u}^{i}+A^{i}\zeta^{i}\mid\
\zeta^{i}\in\mathcal{Z}_{i}\\}$, i.e., $\mathcal{U}_{i}$ is an affine
transformation of a convex set (and thus, convex).

  * (ii)

The uncertainty of $f_{i}$ is concave (we recall that this definition implies
that $f_{i}(x,\cdot):\mathcal{U}^{i}\to\mathbb{R}$ is concave for every
$x\in\mathcal{X}$).

  * (iii)

The nominal scenario $\overline{u}^{i}$ is contained in the relative interior
of $\mathcal{U}_{i}$.

Convexity of the uncertainty set (i) is a typical assumption in robust
optimization, see RobustBook. Assumptions (ii) and (iii) are required to apply
the techniques from Fenchel. To this end, we need some tools of convex
analysis:

######  Definition 3.5.

Let $\mathcal{X}\subseteq\mathbb{R}^{n}$ and
$\mathcal{A}\subseteq\mathbb{R}^{m}$ be a convex set. Let
$f\colon\mathcal{X}\times\mathcal{A}\to\mathbb{R},\ (x,a)\mapsto f(x,a)$ be a
function that is concave in $a$ for every $x\in\mathcal{X}$. For an arbitrary,
but fixed $x\in\mathcal{X}$, the function

$\displaystyle f_{*}(x,\cdot)\colon$ $\displaystyle\mathbb{R}^{n}$
$\displaystyle\to$ $\displaystyle\ \mathbb{R}\cup\\{-\infty\\},$
$\displaystyle a$ $\displaystyle\mapsto$
$\displaystyle\inf_{y\in\mathcal{A}}\\{a^{T}y-f(x,y)\\}$

is called the (partial) concave conjugate with respect to $a$. For a non–empty
set $\mathcal{S}\subseteq\mathbb{R}^{n}$, the function

$\displaystyle\delta^{*}(\cdot\mid\mathcal{S})\colon$
$\displaystyle\mathbb{R}^{n}$ $\displaystyle\to$ $\displaystyle\
\mathbb{R}\cup\\{\infty\\},$ $\displaystyle x$ $\displaystyle\mapsto$
$\displaystyle\sup_{y\in\mathcal{S}}y^{T}x$

is called the support function of $\mathcal{S}$.

The main result of Fenchel is the following reformulation:

######  Proposition 1.

(Fenchel, Theorem 2) Under Assumption 3.1, inequality

$\displaystyle\sup_{u^{i}\in\mathcal{U}_{i}}f_{i}(x,u^{i})\leq 0$

is satisfied if and only if there is a vector $v^{i}\in\mathbb{R}^{L_{i}}$,
such that

$\displaystyle\left(\overline{u}^{i}\right)^{T}v^{i}+\delta^{*}((A^{i})^{T}v^{i}\mid\mathcal{Z}_{i})-f_{i,*}(x,v^{i})\leq
0.$ (21)

We note that convexity of $f_{i}$ in $x$ implies that the left-hand side of
inequality (21) is also convex, since $\delta^{*}$ is convex in $v^{i}$ and
$f_{i,*}$ is concave in $(x,v^{i})$, see Fenchel.
By applying Proposition 1 to program (15), we obtain an equivalent
reformulation of $\Gamma$–counterpart (8):

######  Corollary 3.6.

Let $\Gamma\in[m]$. Under Assumption 3.1, $\Gamma$–counterpart (8) is
equivalent to

$\displaystyle\begin{split}\inf_{x,p,\theta,v^{1},\dots,v^{m}}&\
\Gamma\theta+\sum_{i\in[m]}f_{i}(x,\overline{u}^{i})+p_{i}\\\
\mathrm{s.t.}\;&x\in\mathcal{X}\\\
&p_{i}+\theta\geq(\overline{u}^{i})^{T}v^{i}+\delta^{*}((A^{i})^{T}v^{i}\mid\mathcal{Z}_{i})-f_{i,*}(x,v^{i})-f_{i}(x,\overline{u}^{i})\
\forall i\in[m]\\\ &p,\theta\geq 0.\end{split}$ (22)

######  Proof 3.7.

Proof. Since $\Gamma$ is integral, Lemma 3.1 holds. Proposition 1 implies that
for each $i\in[m]$,

$\displaystyle
p_{i}+\theta\geq({\overline{u}^{i}})^{T}v^{i}+\delta^{*}((A^{i})^{T}v^{i}\mid\mathcal{Z}_{i})-f_{i,*}(x,v^{i})-f_{i}(x,\overline{u}^{i})$

is satisfied for $v\in\mathbb{R}^{L_{i}}$ if and only if
$p_{i}+\theta\geq\sup_{u^{i}\in\mathcal{U}_{i}}f_{i}(x,u^{i})-f_{i}(x,\overline{u}^{i}).$

In general, program (22) is not compuationally tractable. The support function
and the concave conjugate with respect to $v^{i}$ are optimization programs
themselves that depend on a new decision variable $v^{i}$. In Fenchel, the
authors derived finite reformulations for various uncertainty sets
$\mathcal{U}_{i}$, including geometries like ellipsoids, polyhedra, cones,
boxes, Minkowski sums or their intersections and uncertainty sets that are
described by various functions, e.g. convex functions or separable functions
and. Their findings can also be applied here. For details, we refer to Tables
1, 2 and 3 in Fenchel.

###  3.2 Linear Uncertainties

During the last decades, research has been focused on linear uncertainties and
they are well–studied. Thus, in this subsection, we will show how one can deal
with linear uncertainties in the context of MINLPs under uncertainty, noting
that many combinatorial programs are dealing with linear uncertainty (as we
will also demonstrate in Section 4): For $\Gamma$–counterpart (8) and for all
$i\in[m]$, Assumption 3.1 holds with the following modification:

  * $\text{(ii)}^{*}$

The uncertainty is linear, i.e., there exists a function
$l_{i}\colon\mathcal{X}\to\mathbb{R}^{L_{i}}$ such that

$\displaystyle f_{i}(x,u^{i})=(u^{i})^{T}l_{i}(x)\ \forall
u^{i}\in\mathcal{U}_{i},\ x\in\mathcal{X}.$

We start by formulating Corollary 3.6 under Assumption 3.2:

######  Corollary 3.8.

Let $\Gamma\in[m]$. Under Assumption 3.2, $\Gamma$–counterpart (8) is
equivalent to

$\displaystyle\begin{split}\inf_{x,p,\theta}&\
\Gamma\theta+\sum_{i\in[m]}(\overline{u}^{i})^{T}l_{i}(x)+p_{i},\\\
\mathrm{s.t.}\;&x\in\mathcal{X},\\\
&p_{i}+\theta\geq\delta^{*}((A^{i})^{T}l_{i}(x)\mid\mathcal{Z}_{i})\ \forall
i\in[m],\\\ &p,\theta\geq 0.\end{split}$ (23)

######  Proof 3.9.

Proof. Since $\Gamma$ is integral, Corollary 3.6 holds. Since the uncertainty
is linear, we have

$\displaystyle f_{i,*}(x,v^{i})\neq-\infty\Leftrightarrow v^{i}=l_{i}(x),$

see Fenchel. Since inequality (21) is naturally not fulfilled for
$f_{i,*}(x,v^{i})=-\infty$, $v^{i}=l_{i}(x)$ holds. Inserting this into
program (22) proves the claim, since
$f_{i}(x,\overline{u}^{i})=(\overline{u}^{i})^{T}l_{i}(x)$.

######  Remark 3.10.

We note that naturally, similar to $\Gamma$–counterpart (8) being a
generalization of program (4), Corollary 3.8 is a generalization of Theorem 1
in IntroGamma.

For combinatorial optimization under interval uncertainty, it is usually
essential to obtain a tractable reformulation for which the feasible set is
not altered, as oracles for program (6) can then be used to solve the resp.
$\Gamma$–counterpart. In the case of linear uncertainty, this can be achieved
by adding the additional assumption of $l_{i}$, $i\in[m]$, being non–negative
on $\mathcal{X}$ and altering $\mathcal{X}$:

######  Theorem 3.11.

Let $\Gamma\in[m]$ and consider the $\Gamma$–counterpart (8) under interval
uncertainty $\mathcal{U}_{k}=[\overline{u}_{k},\overline{u}_{k}+\Delta u_{k}]$
for some $\overline{u}_{k},\Delta u_{k}\in\mathbb{R}_{\geq 0}^{L_{k}}$ for all
$k\in[m]$. If the uncertainty is linear with $f(x,u_{k})=u_{k}^{T}l_{k}(x)$
and $l_{k}(x)\geq 0$ holds for all $x\in\mathcal{X}$ and all $k\in[m]$, then
program (8) is equivalent to

$\displaystyle\begin{split}\inf_{k\in[m]_{0}}&\left\\{\inf_{\mathcal{Q}\subseteq[m]}\left\\{\inf_{x\in\mathcal{X_{\mathcal{Q}}}}\left\\{\Gamma\Delta
u_{k}^{T}l_{k}(x)+\sum_{i\in[m]}\overline{u}_{i}^{T}l_{i}(x)+\sum_{q\in\mathcal{Q}}\Delta
u_{q}^{T}l_{q}(x)-\Delta
u_{k}^{T}l_{k}(x)\right\\}\right\\}\right\\},\end{split}$ (24)

with $\Delta u_{0}:=l_{0}(x):=0$ and

$\displaystyle\mathcal{X}_{\mathcal{Q}}:=\\{x\in\mathcal{X}:\Delta
u_{q}^{T}l_{q}(x)-\Delta u_{k}^{T}l_{k}(x)\geq 0\ \forall q\in\mathcal{Q},\
\Delta u_{q}^{T}l_{q}(x)-\Delta u_{k}^{T}l_{k}(x)\leq 0\ \forall
q\in[m]\setminus\mathcal{Q}\\}.$

######  Proof 3.12.

Proof. Let $e^{j}$ be the vector of only ones in $\mathbb{R}^{j}$. Since
$l_{k}$ is non–negative, $\Gamma$–counterpart (8) does not change when one
replaces $\mathcal{U}_{k}$ with
$\mathcal{U}^{\varepsilon}_{k}:=[\overline{u}_{k}-\varepsilon
e^{L_{k}},\overline{u}_{k}+\Delta u_{k}]$ for any $\varepsilon>0$ and
Assumption 3.2 holds. Thus, $\Gamma$–counterpart (8) is equivalent to (22).
Analogously to the proof of Lemma 3.3, one can show that

$\displaystyle
p^{*}_{i}=\max\\{0,\delta^{*}((A^{i})^{T}l_{i}(x)\mid\mathcal{Z}_{i})-\theta^{*}\\}$
(25)

and that $\theta^{*}$ equals $0$ or there exists $k\in[m]$ such that

$\displaystyle\theta^{*}=\delta^{*}((A^{k})^{T}l_{k}(x)\mid\mathcal{Z}_{k})=\Delta
u_{k}^{T}l_{k}(x)$ (26)

for optimal $p^{*}$ and $\theta^{*}$. Note that the last equation in (26)
holds since $l_{k}$ is non–negative. Thus, $\Gamma$–counterpart (8) is
equivalent to

$\displaystyle\inf_{k\in[m]_{0}}$
$\displaystyle\left\\{\inf_{\begin{subarray}{c}x\in\mathcal{X}\end{subarray}}\left\\{\Gamma
u_{k}^{T}l_{k}(x)+\sum_{i\in[m]}(\overline{u}^{i})^{T}l_{i}(x)+\max\\{0,\Delta
u_{i}^{T}l_{i}(x)-\Delta u_{k}^{T}l_{k}(x)\\}\right\\}\right\\}.$

This proves the claim since $\mathcal{Q}$ encodes which maximization terms are
non–negative.

Theorem 3.11 states that the $\Gamma$–counterpart under said theorem’s
assumptions can be ’almost’ solved by an optimization oracle for solving (6),
assuming that one can extend the oracle from $\mathcal{X}$ to
$\mathcal{X}_{\mathcal{Q}}$. However, the number of calls is in $O(m2^{m})$,
i.e., exponential in the number of uncertain functions (even if $m$ is part of
the input). To the best of our knowledge, there is no ’black box’ that can go
from $\mathcal{X}$ to $\mathcal{X}_{\mathcal{Q}}$ in the nonlinear
combinatorial context which would certainly be an interesting research avenue.
Thus, to be able to solve the $\Gamma$–counterpart with an optimization oracle
as of now, one requires further assumptions. However, in Section 4, we show
that this is possible for programs ’underlying an assignment structure’. As a
tool, we require the following result for models of the form
$\min_{x\in\mathcal{X}}u^{T}Bg(x)$ underlying said structure.

######  Theorem 3.13.

Let $B\in\mathbb{R}_{\geq 0}^{m\times(mn)}$ be a block diagonal matrix where
each block consists of a single row and let
$g\colon\mathbb{R}^{r}\to\mathbb{R}_{\geq 0}^{mn}$ be an arbitrary nonnegative
function. Consider program

$\displaystyle\inf_{x\in\mathcal{X}}u^{T}Bg(x),$ (27)

under interval uncertainty, i.e.,
$u_{i}\in\mathcal{U}^{i}:=[\overline{u}_{i},\overline{u}_{i}+\Delta
u_{i}]\subseteq\mathbb{R}_{\geq 0}$ for all $i\in[m]$. Furthermore, we assume
that

$\displaystyle\mathcal{X}\subseteq\\{x\in\mathbb{R}^{r}\colon\ \forall
i\in[m]\exists!j\in[n]:\ g_{i,j}(x)\text{ is not constant $0$}\\}.$ (28)

Let $\Gamma\in[m]$. Then the $\Gamma$–counterparts of program (27) and program

$\displaystyle\inf_{x\in\mathcal{X}}y^{T}g(x),$ (29)

under interval uncertainty
$y_{(i,j)}\in\mathcal{Y}^{(i,j)}:=[\overline{u}_{i}B_{i,(i,j)},(\overline{u}_{i}+\Delta
u_{i})B_{i,(i,j)}]$ for all $(i,j)\in[m]\times[n]$ are equivalent.

######  Proof 3.14.

Proof. We begin by introducing some notation: We set $B_{.,(0,0)}:=\Delta
y_{0,0}:=\overline{y}_{0,0}:=0$ (note that this is a slight abuse of notation
and we mean the zero vector or the number $0$, depending on the dimension),
$\Delta y:=(\Delta y_{a,b})_{(a,b)\in[m]\times[n]}:=(\Delta
u_{a}B_{a,(a,b)})_{(a,b)\in[m]\times[n]}$,
$\overline{y}:=(\overline{y}_{(a,b)})_{(a,b)\in[m]\times[n]}=(\overline{u}_{a}B_{a,(a,b)})_{(a,b)\in[m]\times[n]}$
and with $B_{k,.}$, we denote the $k$–th row of $B$. By applying Theorem 3.11,
we obtain that the $\Gamma$–counterpart of program (27) is equivalent to

$\displaystyle\inf_{k\in[m]_{0}}$
$\displaystyle\left\\{\inf_{\mathcal{Q}\subseteq[m]}\left\\{\inf_{x\in\mathcal{X_{\mathcal{Q}}}}\left\\{\Gamma\Delta
u_{k}B_{k,.}g(x)+\sum_{i\in[m]}\overline{u}_{i}B_{i,.}g(x)+\sum_{q\in\mathcal{Q}}\Delta
u_{q}B_{q,.}g(x)-\Delta u_{k}B_{k,.}g(x)\right\\}\right\\}\right\\}.$ (30)

Since $B$ is a block–diagonal matrix where each block contains exactly one
row, one obtains $B_{i,(r,s)}=0$ for $i\neq r$. Furthermore, since for all
$i\in[m]$, $g_{i,j}(x)\neq 0$ for exactly one $j\in[n]$ (which will we be
denoted by $j(i)$) we obtain

$\displaystyle
B_{q,.}g(x)=\sum_{i\in[m],j\in[n]}B_{q,(i,j)}g_{i,j}(x)=\sum_{i\in[m]}B_{q,(i,j(i))}g_{i,j(i)}(x)=B_{q,(q,j(q))}g_{q,j(q)}(x).$

The $\Gamma$–counterpart of program (29) is equivalent to (again by applying
Theorem 3.11 – note that $l(x)=g(x)$ here and we replace $\mathcal{Q}$ by
$\mathcal{Y}$ for the sake of notation):

$\displaystyle\inf_{(a,b)\in[m]\times[n]\cup\\{(0,0)\\}}$
$\displaystyle\left\\{\inf_{\mathcal{Y}\subseteq[m]\times[n]}\left\\{\inf_{x\in\mathcal{X_{\mathcal{Y}}}}\left\\{\Gamma\Delta
y_{(a,b)}g_{(a,b)}(x)+F_{\mathcal{Y},a,b}(x)\right\\}\right\\}\right\\}$ (31)

with

$\displaystyle\begin{split}F_{\mathcal{Y},a,b}(x)&:=\sum_{(i,j)\in[m]\times[n]}\overline{y}_{(i,j)}g_{(i,j)}x+\sum_{(q,p)\in\mathcal{Y}}\Delta
y_{(q,p)}g_{(q,p)}(x)-\Delta y_{(a,b)}g_{(a,b)}(x).\end{split}$ (32)

In the following, we show that one can reduce the number of subproblems of
program (30) from $(m\cdot n+1)\cdot 2^{mn}$ to $(m+1)\cdot 2^{m}$ and that
the resulting program is exactly (31). On the one hand, if $b\neq b(a)$, then
$g_{(a,b)}(x)=0$ for all $x\in\mathcal{X}$ by assumption and equation (32)
results in

$\displaystyle
F_{\mathcal{Y},a,b}(x)=\sum_{(i,j)\in[m]\times[n]}\overline{y}_{(i,j)}g_{(i,j)}(x)+\sum_{(q,p)\in\mathcal{Y}}\Delta
y_{(q,p)}g_{(q,p)}(x)=F_{\mathcal{Y},0,0}(x).$ (33)

Thus, instead of $b\in[n]$, we can fix $b=b(a)$ in program (31) and only have
$m+1$ ’outer problems’. On the other hand, for each
$\mathcal{Y}\subseteq[m]\times[n]$, $x\in\mathcal{X}_{\mathcal{Y}}$ only holds
if

$\displaystyle\Delta y_{q,p}g_{q,p}(x)\geq\Delta y_{a,b(a)}g_{a,b(a)}(x)>0\
\forall(q,p)\in\mathcal{Y}.$

However, $g_{q,p}(x)$ is not equal to $0$ for some $x$ only if $p=p(q)$. Thus,
$\mathcal{X}_{\mathcal{Y}}=\emptyset$ if $(q,p)\in\mathcal{Y}$ for some $p\neq
p(q)$. Thus, program (31) is equivalent to

$\displaystyle\inf_{a\in[m]_{0}}$
$\displaystyle\left\\{\inf_{\overline{\mathcal{Y}}\subseteq[m]}\left\\{\inf_{x\in\mathcal{X}_{\overline{\mathcal{Y}}}}\left\\{\Gamma\Delta
y_{(a,b(a))}g_{(a,b(a))}(x)+F_{\overline{\mathcal{Y}},a}(x)\right\\}\right\\}\right\\}$
(34)

where

$\displaystyle\mathcal{X}_{\overline{\mathcal{Y}}}:=\\{x\in\mathcal{X}\colon$
$\displaystyle\Delta y_{q,p(q)}g_{q,p(q)}(x)\geq\Delta
y_{a,b(a)}g_{a,b(a)}(x)\ \forall q\in\overline{\mathcal{Y}},$
$\displaystyle\Delta y_{q,p(q)}g_{q,p(q)}(x)\leq\Delta
y_{a,b(a)}g_{a,b(a)}(x)\ \forall q\in[m]\setminus\overline{\mathcal{Y}}\\},$

$b(0):=0$ and

$\displaystyle F_{\overline{\mathcal{Y}},a}(x)$
$\displaystyle:=\sum_{(i,j)\in[m]\times[n]}\overline{y}_{(i,j)}g_{(i,j)}(x)+\sum_{(q,p)\in\overline{\mathcal{Y}}}\Delta
y_{(q,p(q))}g_{(q,p(q))}(x)-\Delta y_{(a,b(a))}g_{(a,b(a))}(x).$

By inserting the definition of $\overline{y}$ and $\Delta y$ into program (34)
and by replacing all indices, one obtains program (30).

Thus, if $g(x)$ is a $0/1$–function, then one can apply Theorem 3.13 to obtain
an equivalent $\Gamma$–counterpart where the uncertainty is linear and no
matrix $B$ is involved. The following corollary demonstrates this for
$g(x)=x$:

######  Corollary 3.15.

Consider program

$\displaystyle\min_{x\in\mathcal{X}}u^{T}Bx$ (35)

as in the setting of Theorem 3.13 and assume that
$\mathcal{X}\subseteq\\{x\in\\{0,1\\}^{[m]\times[n]}:\sum_{j\in[n]}x_{i,j}=1\
\forall i\in[m]\\}$. Let $\Gamma\in[m]$. Then the $\Gamma$–counterpart of (35)
is equivalent to

$\displaystyle\min_{(k,l)\in[m]\times[n]\cup\\{(0,0)\\}}\left\\{\Gamma\Delta
u_{k}B_{k,(k,l)}+\min_{x\in\mathcal{X}}\left\\{\overline{u}^{T}Bx+\sum_{(i,j)\in[m]\times[n]}F_{i,j,k,l}(x)\right\\}\right\\}$

where $B_{0,.}:=\Delta u_{0}:=0$ (the first one being a row vector of zeros
and the latter being the number $0$) and

$\displaystyle F_{i,j,k,l}(x):=\max\\{0,\Delta u_{i}B_{i,(i,j)}-\Delta
u_{k}B_{k,(k,l)}\\}x_{i,j}.$

######  Proof 3.16.

Proof. This follows from Theorem 3.13 and Proposition 2.1 by setting $g(x)=x$.

#### The special case of $0/1$–functions.

Before we apply our theory in Section 4, we discuss one more case, namely the
$\Gamma$–counterpart (8) under linear one–dimensional interval uncertainty
with $0/1$–functions: For the $\Gamma$–counterpart (8) and for all $i\in[m]$
we assume:

  * (i)

The uncertainty set $\mathcal{U}_{i}$ is a 1–dimensional interval, i.e.,
$\mathcal{U}_{i}=[\overline{u}_{i},\overline{u}_{i}+\Delta
u_{i}]\subseteq\mathbb{R}_{>0}$ and $\Delta u_{i}>0$.

  * (ii)

There is a $0/1$–function $l_{i}\colon\mathcal{X}\to\\{0,1\\}$ such that
$f_{i}(x,u_{i})=u_{i}l_{i}(x)$ for all $u_{i}\in\mathcal{U}_{i}$.

Although Assumption 3.2 seems restrictive, it covers many combinatorial
programs under uncertainty, e.g. the quadratic knapsack problem or the
quadratic matching problem. By applying Proposition 2.1, we obtain the
following:

######  Theorem 3.17.

Let $\Gamma\in[m]$ and assume that Assumption 3.2 holds. Then
$\Gamma$–counterpart (8) is equivalent to

$\displaystyle\inf_{k\in[m]_{0}}\left\\{\Gamma\Delta
u_{k}+\inf_{x\in\mathcal{X}}\left\\{\overline{u}^{T}l(x)+\sum_{j\in[m]}\max\\{0,\Delta
u_{j}-\Delta u_{k}\\}l_{j}(x)\right\\}\right\\}.$ (36)

######  Proof 3.18.

Proof. Under Assumption 3.2, program (6) is equivalent to
$\inf_{(x,y)\in\mathcal{X}_{y}}u^{T}y$ with
$\mathcal{X}_{y}:=\mathcal{X}\times
l(\mathcal{X})\subseteq\mathbb{R}^{n}\times\\{0,1\\}^{m}$. Then Proposition
2.1 implies that the modified program’s $\Gamma$–counterpart is equivalent to

$\displaystyle\inf_{k\in[m]_{0}}\left\\{\Gamma\Delta
u_{k}+\inf_{x\in\mathcal{X}_{y}}\left\\{\overline{u}^{T}y+\sum_{j\in[m]}\max\\{0,\Delta
u_{j}-\Delta u_{k}\\}y_{j}\right\\}\right\\}$

where $\Delta u_{0}:=0$. Since $y_{j}=l_{j}(x)$, the claim follows.

Theorem 3.17 demonstrates that one can solve the $\Gamma$–counterpart with an
optimization oracle of program (6). This result only implies that
additionally, one can reduce the number of oracle calls one has to solve and
can determine $\alpha$-approximations (for $\alpha\geq 1$), if program (6) is
$\alpha$–approximable (the following definition is not formal and is usually
applied for combinatorial programs: Assume that $f^{*}\in$ $(-\infty,\infty)$
is the optimal value of program (6). Then program (6) is called
$\alpha$–approximable when there exists a real number $\alpha\geq 1$ and an
algorithm ALG with input $(f,\mathcal{X})$, output $\tilde{x}$, the inequality
$\alpha f^{*}\geq f(\tilde{x})$ holds for every instance $(f,\mathcal{X})$ and
the running time of algorithm ALG is polynomial in the encoding length of
$(f,\mathcal{X})$). The proofs are both heavily inspired by the resp. proofs
in IntroGamma and Lee2014:

######  Theorem 3.19.

Let $\Gamma\in[m]$. If Assumption 3.2 holds and program (6) is
$\alpha$-approximable, then (8) is $\alpha$–approximable.

######  Proof 3.20.

Proof. For $k\in[m]_{0}$, we denote the objective of the $k$–th inner problem
of program (36) with $G^{k}(x)$, i.e.,

$\displaystyle G^{k}(x):=\sum_{j\in[m]}(\overline{u}_{j}+\max\\{0,\Delta
u_{j}-\Delta u_{k}\\})l_{j}(x).$

Naturally, one can $\alpha$–approximate program
$\inf_{x\in\mathcal{X}}G^{k}(x)$ for each $k\in[m]_{0}$ by assumption. Let
$x^{k}$ be the output of the given approximation algorithm with objective
value $z^{k}$ and $Z^{*}$ be the optimal value of program (36), which is
equivalent to $\Gamma$–counterpart (8) since Assumption 3.2 holds. Then we
obtain

$\displaystyle Z^{*}$
$\displaystyle\leq\left(\sum_{i\in[m]}l_{i}(x^{k})\overline{u}_{i}\right)+\sup_{\mathcal{S}\subseteq[m]:|\mathcal{S}|\leq\Gamma}\sum_{i\in\mathcal{S}}\Delta
u_{i}l_{i}(x^{k})$
$\displaystyle=\left(\sum_{i\in[m]}l_{i}(x^{k})\overline{u}_{i}\right)+\inf_{\theta\geq
0}\sum_{j\in[m]}\max\\{0,\Delta u_{i}l_{i}(x^{k})-\theta\\}+\Gamma\theta$
$\displaystyle\overset{l_{i}(x^{k})\in\\{0,1\\}}{=}\left(\sum_{i\in[m]}l_{i}(x^{k})\overline{u}_{i}\right)+\inf_{\theta\geq
0}\sum_{j\in[m]}\max\\{0,\Delta u_{i}-\theta\\}l_{i}(x^{k})+\Gamma\theta$
$\displaystyle\leq\Gamma\Delta
u_{k}+\sum_{i\in[m]}(\overline{u}_{i}+\max\\{0,\Delta u_{i}-\Delta
u_{k}\\})l_{i}(x^{k})$ $\displaystyle=\Gamma\Delta u_{k}+G^{k}(x^{k})$
$\displaystyle\leq\alpha(z_{k}^{*}-\Gamma\Delta u_{k})+\Gamma\Delta u_{k}$
$\displaystyle\overset{\alpha\geq 1}{\leq}\alpha z_{k}^{*}$
$\displaystyle=\alpha Z^{*}$

which proves the claim since it is sufficient to apply the given
$\alpha$–approximation to $\inf_{x\in\mathcal{X}}G^{k}(x)$ for every
$k\in[m]_{0}$ and to solve $\min_{k\in[m]_{0}}z_{k}$.

######  Theorem 3.21.

Let $\Gamma\in[m]$ and assume that $\Delta u_{1}\geq\Delta
u_{2}\geq\dots\geq\Delta u_{m}\geq 0$. If Assumption 3.2 holds, then the
$\Gamma$–counterpart (8) is equivalent to

$\displaystyle\inf_{k\in\mathcal{L}}\left\\{\Gamma\Delta
u_{k}+\inf_{x\in\mathcal{X}}\left\\{f(x,\overline{u})+\sum_{i\in[k]}\left(\Delta
u_{i}-\Delta u_{k}\right)l_{i}(x)\right\\}\right\\}$

for $\mathcal{L}:=\\{\Gamma+1,\dots,\Gamma+\gamma,m+1\\}$ with $\gamma$ being
the largest odd integer smaller than $(m+1)-\Gamma$ and $\Delta_{m+1}:=0$.
Furthermore, if the optimal value of the $k$–th inner program is smaller than
$\Gamma\Delta u_{l}$ for $l\in\mathcal{L}$, one can replace $\mathcal{L}$ with
$\mathcal{L}^{*}:=\\{k\in\mathcal{L}:\ k>l\\}$.

######  Proof 3.22.

Proof. Since Assumption 3.2 holds, this statement is a consequence of Theorem
1 in Lee2014 by introducing binary variables $y_{i}$, $i\in[m]$, with
$y_{i}=l_{i}(x)$ (as in the proof of Theorem 3.17).

In particular, Theorem 3.21 implies that, instead of solving $m+1$ nominal
programs, one only needs to solve $\lceil\frac{m-\Gamma}{2}\rceil+1$
subproblems instead of $m+1$, as in the case of Theorem 3.17. Lee2014
demonstrates that this significantly reduces the number of subproblems one
needs to solve for the linear case.
Before we conclude this section, for the sake of completeness, we note the
following:

######  Remark 3.23.

With respect to concave uncertainties under Assumption 3.1, one can show that
$\Gamma$–counterpart (8) is equivalent to

$\displaystyle\min_{k\in[m]_{0}}$
$\displaystyle\left\\{\min_{\begin{subarray}{c}x\in\mathcal{X},v^{1}\in\mathbb{R}^{L_{1}},\\\
\dots,v^{m}\in\mathbb{R}^{L_{m}}\end{subarray}}\left\\{\Gamma\theta^{k}(x,v^{k})+\sum_{i\in[m]}f_{i}(x,\overline{u}^{i})+\max\\{0,\theta^{i}(x,v^{i})-\theta^{k}(x,v^{k})\\}\right\\}\right\\}$
(37)

where

$\displaystyle\theta^{k}(x,v^{k}):=(\overline{u}^{k})^{T}v^{k}+\delta^{*}((A^{k})^{T}v^{k}\mid\mathcal{Z}_{k})-f_{k}(x,\overline{u}^{k})-f_{k,*}(x,v^{k})\
\forall k\in[m].$

In this context, however, it seems unlikely that one would use this
formulation over the one given in Corollary 3.6 since the objective is very
different from the one of program (6), the feasible set was altered, rendering
oracles not applicable.

##  4 Practical examples

In this section, we demonstrate some examples of the reformulations of Section
2. We note that some are maximization programs for which our theory naturally
applies as well.

#### Linear programs under uncertainty.

Here, we cover the case of $\min_{x\in\mathcal{X}}u^{T}Bx$. If $B$ is the unit
matrix and $u$ is subject to interval uncertainty, we obtain the original
setting of Bertsimas and Sim. We have already shown with Corollary 3.15 that
there is a case where one can ’shift’ $B$ into the uncertainty set and that
one can solve the $\Gamma$–counterpart with a polynomial number of oracle
calls. This is a generalization of a result in RobustScheduling which has been
applied to the single–machine scheduling problem under uncertainty:

######  Example 4.1.

We recall that in Section 2, we considered an instance of the program

$\displaystyle\begin{split}\min_{x}&\
\sum_{i,j\in\mathcal{I},\mathcal{J}}u_{i}q_{j}x_{i,j},\\\ \mathrm{s.t.}&\
x\in\mathcal{X}\subseteq\left\\{x\in\\{0,1\\}^{|\mathcal{I}|\cdot|\mathcal{J}|}:\sum_{j\in\mathcal{J}}x_{i,j}=1\
\forall i\in\mathcal{I}\right\\}\end{split}$ (38)

where $u_{i}$ is subject to uncertainty
$[\overline{u}_{i},\overline{u}_{i}+\Delta u_{i}]$ in the context of
single–machine scheduling. By applying Corollary 3.15, one can show that the
$\Gamma$–counterpart of program (38) is equivalent to taking the minimum of

$\displaystyle\min_{(k,l)\in\mathcal{I}\times\mathcal{J}}\left\\{\Gamma
q_{k}\Delta
u_{l}+\min_{x\in\mathcal{X}}\left\\{\sum_{i,j\in\mathcal{I},\mathcal{J}}(\overline{u}_{i}+\max\\{0,\Delta
u_{i}-\frac{\Delta u_{k}q_{l}}{q_{j}}\\})q_{j}x_{i,j}\right\\}\right\\}$

and

$\displaystyle\min_{x\in\mathcal{X}}\sum_{i,j\in\mathcal{I},\mathcal{J}}(\overline{u}_{i}+\Delta
u_{i})q_{j}x_{i,j}.$

In RobustScheduling, this has been shown by algebraic means.

#### Quadratic programs under uncertainty.

As an application of Corollary 3.11, we reformulate the QAP under uncertainty
given in Section 2.

######  Example 4.2.

We consider the QAP under interval uncertainty

$\displaystyle\begin{split}\min_{x}&\
\sum_{(i,j,r,s)\in[n]^{4}}c_{i,j}d_{r,s}x_{i,r}x_{j,s}\\\ \mathrm{s.t.}&\
x\in\mathcal{X}=\\{x\in\\{0,1\\}^{[n]^{2}}:\sum_{i\in[n]}x_{i,r}=1\ \forall
r\in[n],\ \sum_{r\in[n]}x_{i,r}=1\ \forall i\in[n]\\}\end{split}$ (39)

with uncertain coefficients
$c_{i,j}\in\mathcal{U}_{i,j}:=[\overline{c}_{i,j},\overline{c}_{i,j}+\Delta
c_{i,j}]\subseteq\mathbb{R}_{\geq 0}$ for all $i,j\in[n]$ and $d_{r,s}\geq 0$
for all $r,s\in[n]$. Let $\Gamma\in[n^{2}]$. The objective of (39) equals
$u^{T}Bg(x)$ where $B\in\mathbb{R}^{n^{2}\times n^{4}}$ is a block diagonal
matrix with $n^{2}$ copies of $d^{T}$, $u=c$ and
$g_{(i,j),(r,s)}(x):=x_{i,r}x_{j,s}$ for $(i,j,r,s)\in[n]^{4}$. Then Theorem
3.13 implies that the $\Gamma$–counterpart of program (39) is equivalent to
the $\Gamma$–counterpart of

$\displaystyle\min_{x\in\mathcal{X}}y^{T}g(x)$

with $y\in\mathbb{R}^{n^{4}}$ being subject to interval uncertainty, in
particular
$y_{i,j,r,s}\in[\overline{c}_{i,j}d_{r,s},(\overline{c}_{i,j}+\Delta
c_{i,j})d_{r,s}]$ for $i,j,r,s\in[n]$. Now, we can apply Theorem 3.17 and we
obtain the reformulation

$\displaystyle\min_{\begin{subarray}{c}(k_{1},k_{2},k_{3},k_{4})\in[n]^{4}\\\
\cup\\{(0,0,0,0)\\}\end{subarray}}$ $\displaystyle\left\\{\Gamma(\Delta
c_{k_{1},k_{2}})d_{k_{3},k_{4}}+\min_{x\in\mathcal{X}}\left\\{F_{k_{1},k_{2},k_{3},k_{4}}(x)\right\\}\right\\}$
(40)

where

$\displaystyle
F_{k_{1},k_{2},k_{3},k_{4}}(x)=\sum_{(i,j,r,s)\in[n]^{4}}(\overline{c}_{i,j}d_{r,s}+\max\\{0,\Delta{c}_{i,j}d_{r,s}-\Delta
c_{k_{1},k_{2}}d_{k_{3},k_{4}}\\})x_{i,r}x_{j,s}$

for $(k_{1},k_{2},k_{3},k_{4})\in[n]^{4}$,
$F_{0,0,0,0}(x):=\sum_{(i,j,r,s)\in[n]^{4}}(\overline{c}_{i,j}d_{r,s}+\Delta{c}_{i,j}d_{r,s})x_{i,r}x_{j,s}$,
and $\Delta c_{0,0}:=d_{0,0}:=0$. If we assume that the flow and the distance
coefficients are symmetrical, i.e., $\Delta c_{i,j}=\Delta c_{j,i}$ and
$d_{r,s}=d_{s,r}$ for all $i,j,r,s\in[n]$, then we only have to solve inner
problems of the set

$\displaystyle\mathcal{M}:=\\{(k_{1},k_{2},k_{3},k_{4})\in[n]^{4}:\
k_{1}<k_{2},k_{3}<k_{4}\\}\cup\\{(0,0,0,0)\\}.$

Thus, one needs to solve $1+(\frac{n(n-1)}{2})^{2}=\frac{n^{4}-n^{3}}{2}+1$
QAPs to solve program (40). By application of Theorem 3.21, we can reduce the
number of subproblems to
$\lceil\frac{n^{4}-n^{3}}{4}+\frac{1}{2}-\frac{\Gamma}{2}\rceil+1$. In our
electronic companion, we demonstrate how the application of Theorem 3.21
significantly speeds up the the optimization process.

######  Example 4.3.

We consider the following quadratic combinatorial program under interval
uncertainty:

$\displaystyle\begin{split}\min_{x\in\mathcal{X}\subseteq\\{0,1\\}^{n}}&\sum_{i\in[n]}\sum_{j\in[i]}p_{i,j}x_{i}x_{j}\end{split}$
(41)

with uncertain coefficients $p_{i,j}\in[\bar{p}_{i,j},\bar{p}_{i,j}+\Delta
p_{i,j}]$. Let $m:=n^{2}-\frac{n(n+1)}{2}=\frac{n^{2}-n}{2}$ be the number of
uncertain coefficients and let $\mathcal{M}:=\\{(k,l)\in[n]^{2}:\ l\leq k\\}$.
For $\Gamma\in[m]$, its $\Gamma$–counterpart is given by

$\displaystyle\min_{x\in\mathcal{X}}$
$\displaystyle\left\\{\sum_{(i,j)\in\mathcal{M}}\bar{p}_{i,j}x_{i}x_{j}+\max_{\mathcal{S}\subseteq\mathcal{M}:|\mathcal{S}|\leq\Gamma}\left\\{\sum_{(i,j)\in\mathcal{S}}\Delta
p_{i,j}x_{i}x_{j}\right\\}\right\\}$ (42)

By applying Theorem 3.17, we obtain that program (42) is equivalent to

$\displaystyle\min_{(k,l)\in\mathcal{M}\cup\\{(0,0)\\}}\left\\{\Gamma\Delta
p_{k,l}+\min_{x\in\mathcal{X}}\left\\{\sum_{i\in[n]}\sum_{j\in[i]}(\bar{p}_{ij}+\max\\{0,\Delta
p_{i,j}-\Delta p_{k,l}\\})x_{i}x_{j}\right\\}\right\\}$

where $\Delta p_{0,0}:=0$ and we can solve the robust counterpart with $m+1$
calls of an optimization oracle of program (41).

To conclude the discussion of quadratic programs under uncertainty, we
demonstrate the approach of applying the notion of term–wise parallel vectors
and hidden concavity TermWise for interval uncertainty.

######  Example 4.4.

Let $\mathcal{X}$ be a convex set. We consider the following program:

$\displaystyle\inf_{x\in\mathcal{X}}\sum_{i\in[m]}(x_{i}-u_{i})^{2}.$ (43)

For every $i\in[m]$, $u_{i}$ is subject to uncertainty
$\mathcal{U}_{i}:=[\overline{u}_{i},\overline{u}_{i}+\Delta u_{i}]$. For
$\Gamma\in[m]$, the $\Gamma$–counterpart of program (43) after applying Lemma
3.1 is given by

$\displaystyle\begin{split}\inf_{x,p,\theta}&\
\Gamma\theta+\sum_{i\in[m]}(x_{i}-\overline{u}_{i})^{2}+p_{i},\\\
\mathrm{s.t.}&\ x\in\mathcal{X},\\\
&\max_{u_{i}\in\mathcal{U}_{i}}(x_{i}-u_{i})^{2}-(x_{i}-\overline{u}_{i})^{2}\leq
p_{i}+\theta\ \forall i\in[m].\end{split}$ (44)

The inequalities of program (44) are equivalent to

$\displaystyle-2x_{i}u_{i}+u_{i}^{2}\leq
p_{i}+\theta-2x_{i}\overline{u}_{i}+\overline{u}_{i}^{2}\ \forall
u_{i}\in\mathcal{U}_{i}$ (45)

for each $i\in[m]$. The left–hand side of (45) is not concave in $u_{i}$ and
thus, we cannot apply the reformulations of Subsection 3.1. We set
$h(y):=y^{2}$ for all $y\in\mathbb{R}$ and consider the following formulation
of the uncertainty set:

$\displaystyle[\overline{u}_{i},\overline{u}_{i}+\Delta
u_{i}]=\\{u_{i}\in\mathbb{R}\colon(-2\overline{u}_{i}-\Delta
u_{i})u_{i}+u_{i}^{2}\leq-\overline{u}_{i}^{2}-\overline{u}_{i}\cdot\Delta
u_{i}\\}.$

Finally, define

$\displaystyle\alpha:=-2\overline{u}_{i}-\Delta u_{i},\ \beta:=1,\
\gamma=-\overline{u}_{i}^{2}-\overline{u}_{i}\Delta u_{i}.\ $

Since $\alpha$ and $\beta$ are scalars, they are clearly term–wise parallel
TermWise. Thus, we obtain that (45) is satisfied for $(x,p,\theta)$ if and
only if there exist $v_{1},\dots,v_{m}\in\mathbb{R}$, such that

$\displaystyle(1+v)h_{i}^{*}\left(\frac{2x+2\overline{u}_{i}v_{i}+\Delta
u_{i}v_{i}}{1+v_{i}}\right)-\overline{u}_{i}^{2}v_{i}-\overline{u}_{i}v_{i}\Delta
u_{i}v_{i}+2x_{i}\overline{u}_{i}\leq p_{i}+\theta+\overline{u}_{i}^{2},$
$\displaystyle 1+v_{i}\geq 0,$ $\displaystyle v_{i}\geq 0,$

see Fenchel, Subsection 4.3, for details. Clearly, the second inequality is
redundant. Furthermore, since $h_{i}^{*}(z)=\frac{z^{2}}{4}$, the first
inequality is convex in $(x,v_{i})$ if it is assumed that $x\geq 0$. If
$\mathcal{X}\subseteq\mathbb{R}^{n}_{\geq\overline{u}}$, then the
$\Gamma$–counterpart of program (43) is a convex optimization problem,
although the uncertainty is not concave.

#### Deadline uncertainties in a piecewise linear setting.

We conclude our discussion of applications with the deadline uncertainty
setting we introduced in Section 2.

######  Example 4.5.

Consider the $\Gamma$–counterpart of program (13) as introduced in Section 2:

$\displaystyle\inf_{x\in\mathcal{X}}\left\\{\sup_{\mathcal{S}\subseteq[m]:|\mathcal{S}|\leq\Gamma}\left\\{\sum_{i\in\mathcal{S}}\max\\{0,x_{i}-\overline{b}_{i}+\Delta
b_{i}\\}+\sum_{i\in[m]\setminus\mathcal{S}}\max\\{0,x_{i}-\overline{b}_{i}\\}\right\\}\right\\}.$

An equivalent reformulation, given in Remark 3.3 as program (18), is

$\displaystyle\begin{split}\inf_{k\in[m]_{0}}\left\\{\inf_{x\in\mathcal{X}}\left\\{\Gamma\theta^{k}(x)+\sum_{i\in[m]}\max\\{0,x_{i}-\overline{b}_{i},\max\\{0,x_{i}-\overline{b}_{i}+\Delta
b_{i}\\}-\theta^{k}(x)\\}\right\\}\right\\}\end{split}$ (46)

with $\theta^{k}(x):=\max\\{0,x_{k}-\overline{b}_{k}+\Delta
b_{k}\\}-\max\\{0,x_{k}-\overline{b}_{k}\\}$ and $\theta^{0}(x):=0$. Thus, for
$k=0$, it is necessary to solve
$\min_{x\in\mathcal{X}}\sum_{i\in[m]}\max\\{0,x_{i}-\overline{b}_{i}+\Delta
b_{i}\\}$. For $k>0$, we distinguish between three cases:

  1. i)

$x_{k}\geq\overline{b}_{k}$, i.e., $\theta^{k}(x)=\Delta b_{k}$ and

$\displaystyle\max\\{0,x_{i}-\overline{b}_{i},\max\\{0,x_{i}-\overline{b}_{i}+\Delta
b_{i}\\}-\theta^{k}(x)\\}=\max\\{0,x_{i}-\overline{b}_{i},x_{i}-\overline{b}_{i}+\Delta
b_{i}-\Delta b_{k}\\}.$ (47)

  2. ii)

$x_{k}\in[\overline{b}_{k}-\Delta b_{k},\overline{b}_{k}]$, i.e.,
$\theta^{k}(x)=x_{k}-\overline{b}_{k}+\Delta b_{k}$ and

$\displaystyle\begin{split}&\max\\{0,x_{i}-\overline{b}_{i},\max\\{0,x_{i}-\overline{b}_{i}+\Delta
b_{i}\\}-\theta^{k}(x)\\}=\\\
&\max\\{0,x_{i}-\overline{b}_{i},x_{i}-\overline{b}_{i}+\Delta
b_{i}-x_{k}+\overline{b}_{k}-\Delta b_{k}\\}.\end{split}$ (48)

  3. iii)

$x_{k}\leq\overline{b}_{k}-\Delta b_{k}$, i.e.,
$\max\\{0,x_{k}-\overline{b}_{k}\\}=\max\\{0,x_{k}-\overline{b}_{k}+\Delta
b_{k}\\}=0$. Thus, $\theta^{k}(x)=0$ and we refer to the case of $k=0$.

For each $k\in[m]$, by applying equations (47) and (48), we solve

$\displaystyle\begin{split}\inf_{x\in\mathcal{X}}&\
\sum_{i\in[m]}\max\\{0,x_{i}-\overline{b}_{i},x_{i}-\overline{b}_{i}+\Delta
b_{i}-\Delta b_{k}\\}+\Gamma\Delta b_{k}\\\ \mathrm{s.t.}&\
x_{k}\in[\overline{b}_{k}-\Delta b_{k},\overline{b}_{k}]\end{split}$ (49)

and

$\displaystyle\begin{split}\inf_{x\in\mathcal{X}}&\
\sum_{i\in[m]}\max\\{0,x_{i}-\overline{b}_{i},x_{i}-\overline{b}_{i}+\Delta
b_{i}-x_{k}+\overline{b}_{k}-\Delta
b_{k}\\}+\Gamma(x_{k}-\overline{b}_{k}+\Delta b_{k})\\\ \mathrm{s.t.}&\
x_{k}\geq b_{k}.\end{split}$ (50)

Therefore, in total, we need to solve $2m+1$ optimization programs with a
piecewise linear objective with the addition of one additional hard bound for
exactly one variable for $k\in[m]$. In the electric companion, we apply this
reformulation to a special case of the vehicle routing problem with general
time windows.

##  5 Conclusion

In this paper, we studied $\Gamma$–counterparts of discrete nonlinear
optimization problems under uncertainty in the objective. We established
reformulations of $\Gamma$–counterparts by applying reformulations techniques
developed in Fenchel. Similar to $\Gamma$–uncertainties in IntroGamma and
PriceRobust, our reformulations work for general MINLPs and for combinatorial
optimization problems with linear uncertainty when attempting to optimize over
the original feasible set $\mathcal{X}$. While those reformulations are not
necessarily computationally tractable, we have provided examples where this is
indeed the case, namely for linear uncertainties involving $0/1$–functions,
programs involving some kind of assignment structure. Furthermore, we
discussed the general case with an application in logistics. Possible further
research for this topic include extensive numerical studies for the derived
reformulations that could be based on our prototypical study in the electronic
companion. Furthermore, one could also investigate whether the generalizations
of Poss12, Poss14 and POSS2018 to the nonlinear $\Gamma$–counterpart are
possible and tractable as well. Finally, one could attempt to investigate
cases where one could extend the optimization oracle from $\mathcal{X}$ to
$\mathcal{X}_{\mathcal{Q}}$ as in the setting of Theorem 3.11 or to perform,
under further assumptions, more reformulations that reduce the number of the
problems from exponential to polynomial im $m$, similar to Theorem 3.13.

The authors are grateful to Jana Dienstbier for many fruitful discussions, in
particular on the quadratic assignment problem under uncertainty. Research
reported in this paper was partially supported by project HealthFaCT under
BMBF grant 05M16WEC. It was also funded by the Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation) – Project–ID 416229255 – SFB 1411.
Furthermore, this paper has received funding from the European Union’s Horizon
2020 research and innovation program under the Marie Skłodowska-Curie grant
agreement No 764759.

Electronic Companion

##  6 Appendix: Numerical study

The programs were implemented in Python 3.7. To solve the optimization
programs, we used Gurobi 9.0.1. Gurobi running on machines with Xeon E3-1240
v5 CPUs (4 cores, 3.5 GHz each).

###  6.1 Vehicle routing problem with soft time windows under uncertainty

We elaborate on Example 4.5 based on Dummies and VRPSTW. We consider a
complete digraph $D=(N,A)$ with nodes $N:=[n]$, a start depot $0$ and a copy
of the start depot $n+1$, and the digraph $\bar{D}=(V,\bar{A})$ with nodes
$V:=[n+1]_{0}$ and arcs

$\displaystyle\bar{A}=A\cup\\{(0,j):\ j\in N\\}\cup\\{(i,n+1):\ i\in
N\cup\\{0\\}\\}.$

The following data are given: For every arc $a\in\bar{A}$, the travel time is
$t_{a}$ and for every node $i\in N$, a service time $s_{i}$ and a soft due
time $b_{i}$ is given. Given a homogeneous fleet of $K$ vehicles, all nodes
$i\in N$ have to be ’visited’ by exactly one vehicle exactly once and with as
little delay as possible. The vehicles start and end at the depot. In the
following, the binary variables $x_{i,j}^{k}\in\\{0,1\\}$ for
$(i,j)\in\bar{A}$ and $k\in[K]$ denote whether vehicle $k$ ’uses’ arc $(i,j)$
and the real variables $T_{i}\in\mathbb{R}_{\geq 0}$ for $i\in V$ denote the
arrival time of a vehicle at node $i$. With this notation, we obtain the
following optimization program (with $\delta^{\mathrm{out}}(v)$ and
$\delta^{\mathrm{in}}(v)$, we denote the outgoing and the incoming arcs of
$v\in V$ in the graph $\bar{D}$):

$\displaystyle\min_{x,T}$ $\displaystyle\ \sum_{i\in
N}\max\\{0,T_{i}-b_{i}\\},$ (51a) s.t. $\displaystyle\
\sum_{k\in[K]}\sum_{(i,j)\in\delta^{\mathrm{out}}(i)}x_{i,j}^{k}=1\
\forall{i}\in{N},$ (51b)
$\displaystyle\sum_{(0,j)\in\delta^{\mathrm{out}}(0)}x_{0,j}^{k}=1\
\forall{k}\in[K],$ (51c)
$\displaystyle\sum_{(i,j)\in\delta^{\mathrm{in}}(j)}x_{i,j}^{k}-\sum_{(j,i)\in\delta^{\mathrm{out}}(j)}x_{j,i}^{k}=0\
\forall k\in[K],j\in N,$ (51d)
$\displaystyle\sum_{(i,n+1)\in\delta^{\mathrm{in}}(0)}x_{i,0}^{k}=1\ \forall
k\in[K],$ (51e) $\displaystyle x_{i,j}^{k}(T_{i}+s_{i}+t_{i,j}-T_{j})\leq 0\
\forall k\in[K],\ (i,j)\in A,$ (51f) $\displaystyle x_{i,j}^{k}\in\\{0,1\\}\
\forall k\in[K],\ (i,j)\in A,$ (51g) $\displaystyle T_{i}\geq 0\ \forall i\in
V.$ (51h)

Constraint (51b) ensures that each $i\in N$ is served exactly once by exactly
one vehicle. Constraints (51c) and (51e) ensure that each vehicle leaves and
enters the depot or stays at the depot. In combination with constraints (51b),
(51c) and (51e), constraint (51d) ensures that each node is served exactly
once and by exactly one vehicle. Constraint (51f) ensures that, if vehicle $k$
serves node $j$ after node $i$, the arrival time $T_{j}$ is at least as large
as the arrival time $T_{i}$ added to the time it requires for serving $i$ and
going from $i$ to $j$. Finally, (51g) and (51h) ensure that $x$ is binary and
$T$ is non–negative. Note that this formulation is only one of many
possibilities to formulate vehicle routing problems – for an overview, we
refer the reader to SurveyVRP. We attempt to be robust against scenarios of
the set $\bigtimes_{i\in N}[\overline{b}_{i}-\Delta b_{i},\overline{b}_{i}]$.
Solving the $\Gamma$–counterpart for all $\Gamma\in[m]$ would show how many
shifts of the due times are possible without any (or only little) delay.
For our experiments we use the Solomon instances r101, r102, c101, c102, rc101
and rc102. If these names begin with r, the nodes are generated randomly, if
they begin with c, they are clustered, and otherwise some nodes are generated
randomly and some are clustered – for a detailed description of the
construction, see Solomon. As due time $b_{i}$ we chose the start time
specified in the original instance for the customer, i.e., node $i$. The
uncertainty set was constructed randomly, i.e., $\Delta b_{i}$ is a uniformly
distributed random variable in $[0,\overline{b}_{i}]$. Since we were
ultimately aiming to find optimal solutions for the $\Gamma$–counterpart, we
tested $N=[8]$ and $N=[10]$, $K\in[3]$ and all $\Gamma\in N$, and calculated
the optimal solutions for the respective nominal program. We selected the
first $|N|$ customers of the list of customers given in the resp. instance.

$0$$2$$4$$6$$8$$0$$100$$200$$300$$\displaystyle\Gamma$Optimal valuerc101K = 1K
= 2K = 3$0$$2$$4$$6$$8$$200$$300$$400$$500$$\displaystyle\Gamma$rc102K = 1K =
2K =
3$0$$2$$4$$6$$8$$0$$200$$400$$600$$800$$1{,}000$$1{,}200$$\displaystyle\Gamma$Optimal
valuec101K = 1K = 2K =
3$0$$2$$4$$6$$8$$200$$300$$400$$500$$600$$700$$\displaystyle\Gamma$r102K = 1K
= 2K = 3

Figure 1: Optimal values for the respective $\Gamma$–counterparts for
instances rc101 (upper left), rc102 (upper right), c101 (lower left) and r102
(lower right), with $N=[8]$ and $K\in[3]$. If a yellow point for a value of
$\Gamma$ is ’missing’, its value coincides with the green point of the same
$\Gamma$.

In Figure 1 we have the robust optimal values for $N=[8]$, $K\in[3]$ and the
instances rc101, rc102, c101 and r102 (we have neglected the other two cases
and the results for $N=[10]$ because the graphs are similar). As expected, the
optimum value, i.e., the waiting time, increases with an increasing number of
vehicles $K$. In addition, at $K=1$ the optimal value for increasing $\Gamma$
strongly rises, while at $K=2,3$ the change in the optimal value is not so
marked. This is also to be expected: If there is exactly one vehicle, the
changes in the due times are supposed to be met by this one vehicle, which is
clearly not really possible, especially in clustered settings. However, the
total delays are more robust for $K=2,3$ – while the robust values differ
between $K=1,2,3$, the difference between $K=1$ and $K=2$ is much higher than
in $K=2$ and $K=3$. So if more vehicles are available, this can lead to more
robust solutions. The difference in the price of robustness is evident, e.g.
in c101: For $K=1$ the nominal optimal value is less than $200$ and for
$K=2,3$ it is $0$. For $\Gamma=1$ and $K=1$ we obtain a delay of at least
$400$, while for $K=2,3$ we remain around the optimal nominal value for $K=1$.
For $\Gamma=2$ the delay increases only slightly and does not change
afterwards. However, for $K=1$, the optimum value increases up to $\Gamma=6$
and is above $1200$, while for $K=2,3$ the optimum value is below $200$. We
note that for other cases, the difference between the nominal optimal values
and the optimal values for $\Gamma\geq 1$ is not as large as can be seen in
r102. In this particular case, the increase in nominal optimal values for
$\Gamma$ stopped at $\Gamma=2$ for all $K=1,2,3$.
Table 1 and Table 2 show the running time to solve the $\Gamma$–counterpart
for $\Gamma\in[2]$, the nominal program for all instances with $N=[8],[10]$
and $K\in[3]$. As the number of constraints increases with more customers and
more vehicles, i.e., rising $|N|$ and $K$, the running time increases in most
cases. Note that when reformulating the $\Gamma$–counterpart, only the
objective of the subproblems (50) will be affected, while the optimal
solutions of the other subproblems can be reused. Thus, of the $2|N|+1$
programs, only $|N|$ programs need to be solved to obtain an optimal solution
of the $\Gamma$ counterpart when different values of $\Gamma$ are considered.
This explains the fact that the running time for $\Gamma=2$ is usually at most
half as large as that for $\Gamma=1$. We note that the value of $\Gamma$ does
not have any other significant influence on the running time and that the
running times are relatively high, especially for $|N|=10$.

Table 1: Running time of various instances in seconds for $\Gamma=1,2$, the nominal case, $N=[8]$ and $K=1,2,3$.  Instances: | Nominal case | $\Gamma=1$ | $\Gamma=2$
---|---|---|---
$N=[8]$ | $K=1$ | $K=2$ | $K=3$ | $K=1$ | $K=2$ | $K=3$ | $K=1$ | $K=2$ | $K=3$
r101 | 17 | 1 | 2 | 79 | 43 | 26 | 40 | 15 | 14
r102 | 11 | 22 | 15 | 105 | 356 | 246 | 49 | 136 | 123
c101 | 1 | 1 | 1 | 28 | 7 | 8 | 19 | 4 | 5
c102 | 10 | 21 | 24 | 124 | 394 | 434 | 62 | 183 | 298
rc101 | 5 | 1 | 2 | 107 | 156 | 224 | 30 | 19 | 22
rc102 | 7 | 69 | 291 | 101 | 823 | 2965 | 49 | 284 | 1282
Table 2: Running time of various instances in seconds for $\Gamma=1,2$, the nominal case, $N=[10]$ and $K=1,2,3$. If no optimal solution has been obtained after 24 hours, the resp. fields are marked with –.  Instances: | Nominal case | $\Gamma=1$ | $\Gamma=2$
---|---|---|---
$N=[10]$ | $K=1$ | $K=2$ | $K=3$ | $K=1$ | $K=2$ | $K=3$ | $K=1$ | $K=2$ | $K=3$
r101 | 551 | 6 | 3 | 9080 | 5178 | 2316 | 5612 | 1525 | 376
r102 | 1175 | 1066 | 119 | 15358 | 54885 | 15637 | 9433 | 18285 | 5875
c101 | 15 | 2 | 5 | 8026 | 2444 | 168 | 4161 | 65 | 28
c102 | 1566 | 431 | 111 | 22081 | 32098 | 21335 | 15285 | 12692 | 12703
rc101 | 681 | 14 | 7 | 8279 | 11024 | 9364 | 2949 | 1253 | 350
rc102 | 902 | 2505 | 8425 | 13327 | 70041 | – | 6804 | 37788 | –

This concludes our numerical study of the VRPGTW under uncertainty. As already
mentioned, we used an optimization oracle to solve the programs given in
Example 4.5 as a MINLP instead of using any VRPTGW solvers to demonstrate that
our reformulation can be solved to optimality. In the future, it might be
interesting to conduct experiments including instances with more customers but
rather than solving them to global optimality, they could be solved only to a
certain gap, i.e., to find solutions which are ’sufficiently robust’ or to
apply a VRPTGW oracle.

###  6.2 Quadratic assignment problem under uncertainty

Here, we solve and compare different reformulations of the
$\Gamma$–counterpart of the QAP. We have chosen instances from QAP2015 and
from the QAPLIB QAPlib. The goal of this section is to prototypically evaluate
whether the new reformulations can be solved within a similar order of
magnitude when compared to that of the nominal versions. As we do not have an
efficient problem–specific QAP oracle at hand, we chose small instances where
the $\Gamma$–counterpart could be solved with Gurobi within 24 hours. As
expected, instances with less uncertain coefficients are computationally
easier to handle. Therefore, by choosing scr12, we included an instance with
$c_{i,j}=0$ for some $(i,j)\in[12]^{2}$. We also chose fei9, an instance that
was examined in QAP2015. For fei9, the number of facilities is $n=9$, while
for scr12, it is $n=12$ (both taken from QAP2015). Finally, we also chose
nug12 from QAPlib. For each instance, we generated three different uncertainty
sets. For fei9, the uncertainty set $\mathcal{U}_{1}$ is taken from QAP2015.
Other uncertainty sets, denoted by $\mathcal{U}_{2}$ and $\mathcal{U}_{3}$,
are generated randomly: for all $(i,j)\in[n]^{2}$, $\Delta
c_{ij}\in[0,\bar{c}_{ij}]$ is randomly chosen. For scr12 and nug6,
$\mathcal{U}_{1}$ is generated by setting $\Delta c_{ij}=0.1\bar{c}_{ij}$ for
all $(i,j)\in[n]^{2}$. Furthermore, $\mathcal{U}_{2}$ and $\mathcal{U}_{3}$
are generated randomly analogously to fei9.

In Figure 2 the change in the objective value for different $\Gamma$ can be
observed for two of our instances are shown. As expected, the optimal
objective value is increasing in $\Gamma$. As can be seen for scr12, only a
mild increase in cost of robust protection can be seen for increasing values
of $\Gamma$.

0102030400100200300400500600$\Gamma$objective valuefei9 with
$\mathcal{U}_{1}$fei9 with $\mathcal{U}_{2}$fei9 with $\mathcal{U}_{3}$ (a)
Optimal objective value $\times 10^{-4}$ for different values of $\Gamma$ for
fei9.

01020304050600100200300400500600$\Gamma$scr12 with $\mathcal{U}_{1}$scr12 with
$\mathcal{U}_{2}$scr12 with $\mathcal{U}_{3}$ (b) Optimal objective value
$\times 10^{-2}$ for different values of $\Gamma$ for scr12.

Figure 2: Optimal solution for different instances.

Now we compare the running time of different equivalent formulation of the
$\Gamma$–counterpart. In particular, we test following formulations:

  * •

QAP: Formulation (40).

  * •

$\texttt{QAP}_{\texttt{red}}$: Formulation (40) after reducing the number of
subproblems with Theorem 3.21.

  * •

MIP: A linearized QAP under uncertainty after applying Theorem 1 of
IntroGamma.

  * •

BP: A linearized QAP under uncertainty after applying Proposition 2.1.

  * •

$\texttt{BP}_{\texttt{red}}:$ A linearized QAP under uncertainty after
applying Proposition 2.1 and Theorem 1 of Lee2014.

In particular, we apply a standard linearization: the product of two binary
variables $x$ and $y$ can be replaced by a binary variable $z$ and the set of
inequalities

$\displaystyle z\leq x,\ z\leq y,\ z\geq x+y-1.$

The nominal programs can be solved within a few seconds. A comparison of
running times for fei9, scr12 and nug12 and $\Gamma=1$ can be found in Tables
3, 4 and 5. If no optimal solution could be computed after 24 hours, we
stopped the process. Running times are measured in seconds.

Table 3: Comparison of running times for different instances for $\Gamma=1$ and the deterministically constructed uncertainty set $\mathcal{U}_{1}$. – if not solvable within 24 hours.  CPU (s) | nug12 | fei9 | scr12
---|---|---|---
QAP | – | 3420 | 36579
$\texttt{QAP}_{\texttt{red}}$ | 1054 | 174 | 221
MIP | 31417 | 25 | 1718
BP | – | 86243 | –
$\texttt{BP}_{\texttt{red}}$ | 34318 | 4096 | 49126
Table 4: Comparison of running times for different instances for $\Gamma=1$ and the deterministically constructed uncertainty set $\mathcal{U}_{2}$. – if not solvable within 24 hours.  CPU (s) | nug12 | fei9 | scr12
---|---|---|---
QAP | – | 3542 | 74641
$\texttt{QAP}_{\texttt{red}}$ | 591 | 178 | 298
MIP | 24655 | 25 | 819
BP | – | – | –
$\texttt{BP}_{\texttt{red}}$ | – | 4538 | 73847
Table 5: Comparison of running times for different instances for $\Gamma=1$ and the randomly constructed uncertainty set $\mathcal{U}_{3}$. - if not solvable within 24 hours.  CPU (s) | nug12 | fei9 | scr12
---|---|---|---
QAP | – | 3503 | 45851
$\texttt{QAP}_{\texttt{red}}$ | 9507 | 178 | 275
MIP | 19550 | 30 | 1860
BP | – | – | –
$\texttt{BP}_{\texttt{red}}$ | – | 4384 | 56979

It is evident that the instances with $n=12$ can be solved more efficiently
than the linearizations after reducing the number of subproblems by excluding
all redundant scenarios (applying Theorem 3.21, neglecting identical
subproblems and taking symmetry of coefficients into account), for all
regarded uncertainty sets. Only for the smaller instance, MIP is faster. This
demonstrates the benefit of the reformulations proposed here. Without using
them, the corresponding robust counterparts are algorithmically very
challenging. All instances have in common that without reducing the number of
programs, i.e., avoiding a repetition of scenarios or applying Theorem 3.21,
these instances cannot be solved within the time limit, even for smaller
instances.

Finally, we would like to point out two things: Firstly, if one would like to
solve $\Gamma$–counterpart for different values of $\Gamma$, it is preferable
to apply $\texttt{QAP}_{\texttt{red}}$ since one only has to calculate the
optimal solutions of the subproblems for $\Gamma=1,2$, since the value of
$\Gamma$ does not influence the subproblems. Secondly, this computational
study demonstrates that our formulations are applicable in practice.
Naturally, instead of using Gurobi, one can also use algorithms that solve
QAPs more efficiently. However, for our purposes, our method proved to be
highly beneficial, when compared to the standard linearization approach.

##  7 Appendix: Uncertainty in the Constraints

Here, we consider the case of a constraint being subject to uncertainty, i.e.,
program

$\displaystyle\begin{split}\inf_{x\in\mathcal{X}}&\ f(x),\\\
\mathrm{s.t.}&\sum_{i\in[m]}\overline{g}_{i}(x)\leq 0.\end{split}$ (52)

Analogously to Section 3, we assume that the functions $\overline{g}_{i}$ are
subject to uncertainty, i.e., we set

$\displaystyle g_{i}\colon\mathcal{X}\times\mathcal{U}_{i}\to\mathbb{R},$

with $g_{i}(x,\overline{u}^{i}):=\overline{g}_{i}(x)$ for a nominal scenario
$\overline{u}^{i}\in\mathcal{U}_{i}$. Thus, program (52) under uncertainty can
be stated as

$\displaystyle\begin{split}\inf_{x\in\mathcal{X}}&\ f(x),\\\
\mathrm{s.t.}&\sum_{i\in[m]}\sup_{u^{i}\in\mathcal{U}^{i}}g_{i}(x,u^{i})\leq
0.\end{split}$ (53)

The $\Gamma$–counterpart of program (53) is given by

$\displaystyle\begin{split}\inf_{x\in\mathcal{X}}&\ f(x),\\\
\text{s.t.}&\sup_{\mathcal{S}\subseteq[m]:|\mathcal{S}|\leq\Gamma}\left\\{\sum_{i\in\mathcal{S}}\sup_{u^{i}\in\mathcal{U}_{i}}g_{i}(x,u^{i})+\sum_{i\in[m]\setminus\mathcal{S}}g_{i}(x,\overline{u}^{i})\right\\}\leq
0.\end{split}$ (54)

Equivalent to Lemma 3.1, we can obtain a reformulation without the outer
supremum operator:

######  Lemma 7.1.

If $\Gamma\in[m]$, then program (54) is equivalent to

$\displaystyle\begin{split}\inf_{x,p,\theta}&\ f(x),\\\ \mathrm{s.t.}&\
\sum_{i\in[m]}g_{i}(x,\bar{u}^{i})+p_{i}+\theta\Gamma\leq 0,\\\
&p_{i}+\theta\geq\sup_{u^{i}\in\mathcal{U}_{i}}g_{i}(x,u^{i})-g_{i}(x,\bar{u}^{i})\
\forall i\in[m],\\\ &p,\theta\geq 0,\\\ &x\in\mathcal{X}.\end{split}$ (55)

######  Proof 7.2.

The proof is almost identical to the proof of Lemma 3.1 since the constraint
subject to uncertainty of $\Gamma$–counterpart (54) is the objective of the
$\Gamma$–counterpart of the $\Gamma$–counterpart (8) with uncertainty in the
objective. In this case, we obtain

$\displaystyle 0\geq$ $\displaystyle\inf_{\theta,p}\
\sum_{i\in[m]}g_{i}(x,\bar{u}^{i})+p_{i}+\theta\Gamma,$ $\displaystyle\
\text{s.t.}\
p_{i}+\theta\geq\sup_{u^{i}\in\mathcal{U}_{i}}g_{i}(x,u^{i})-g_{i}(x,\bar{u}^{i}),\
\forall i\in[m],$ $\displaystyle\ \ \ \ \ \ p,\theta\geq 0.$

Thus, the $\inf$ operator can be omitted and the claim is proven.

Comparing the reformulations of the $\Gamma$–counterparts of Lemmas 3.1 and
7.1, the only difference is the inequality

$\displaystyle\sum_{i\in[m]}g_{i}(x,\overline{u}^{i})+p_{i}+\Gamma\theta\leq
0.$ (56)

However, the left hand side of inequality (56) is the objective of program
(15). More importantly, the bottleneck of both $\Gamma$–counterparts is the
inequality

$p_{i}+\theta\geq\sup_{u^{i}\in\mathcal{U}_{i}}g_{i}(x,u^{i})-g_{i}(x,\bar{u}^{i}),$

for which we already discussed several reformulations in Section 3. Hence, the
reformulation techniques are still applicable here and for MINLPs, we obtain,
under the analogue of Assumption 3.1, the same reformulations:

######  Theorem 7.3.

Assume that Assumption 3.1 holds for all $g_{i}(x,u^{i})$ and
$\mathcal{U}_{i}$ and $\Gamma\in[m]$. Then program (54) is equivalent to

$\displaystyle\begin{split}\inf_{x,p,\theta}&\ f(x),\\\
\text{s.t.}&\sum_{i\in[m]}g_{i}(x,\bar{u}^{i})+p_{i}+\theta\Gamma\leq 0,\\\
&p_{i}+\theta\geq(\overline{u}^{i})^{T}v^{i}+\delta^{*}((A^{i})^{T}v^{i}\mid\mathcal{Z}_{i})-g_{i,*}(x,v^{i})-g_{i}(x,\overline{u}^{i})\
\forall i\in[m],\\\ &p,\theta\geq 0,\\\ &x\in\mathcal{X}.\end{split}$ (57)

Furthermore, if Assumption 3.2 holds, the program (54) is equivalent to

$\displaystyle\begin{split}\inf_{x,p,\theta}&\ f(x)\\\ \mathrm{s.t.}&\
\sum_{i\in[m]}g_{i}(x,\bar{u}^{i})+p_{i}+\theta\Gamma\leq 0,\\\
&p_{i}+\theta\geq\delta^{*}((A^{i})^{T}l_{i}(x)\mid\mathcal{Z}_{i})\ \forall
i\in[m],\\\ &p,\theta\geq 0,\\\ &x\in\mathcal{X}.\end{split}$ (58)

The proof is omitted (see Corollaries 3.6 and 3.8). However, we would like to
point out that, contrary to Section 3, the dual variables $p$ and $\theta$ can
not be eliminated due to the additional inequality (56). This arises as
$\theta$ is additionally multiplied with $\Gamma$. However, since the feasible
set $\mathcal{X}$ was subject to uncertainty in program (54), it is not
necessary to optimize over $\mathcal{X}$ only.