# Wasserstein robust combinatorial optimization problems

Marcel Jackiewicz  Wrocław University of Science and Technology, Wrocław,
Poland
<EMAIL_ADDRESS>Adam Kasperski
Wrocław University of Science and Technology, Wrocław, Poland
<EMAIL_ADDRESS>Paweł
Zieliński111Corresponding author Wrocław University of Science and Technology,
Wrocław, Poland
<EMAIL_ADDRESS>
###### Abstract

This paper discusses a class of combinatorial optimization problems with
uncertain costs in the objective function. It is assumed that a sample of the
cost realizations is available, which defines an empirical probability
distribution for the random cost vector. A Wasserstein ball, centered at the
empirical distribution, is used to define an ambiguity set of probability
distributions. A solution minimizing the Conditional Value at Risk for a worst
probability distribution in the Wasserstein ball is computed. The complexity
of the problem is investigated. Exact and approximate solution methods for
various support sets are proposed. Some known results for the Wasserstein
robust shortest path problem are generalized and refined.

Keywords: uncertainty modelling; distributionally robust optimization;
Wasserstein distance

##  1 Introduction

In a traditional combinatorial optimization problem, we seek an object
composed of some elements of a ground set, which minimizes a linear objective
function. Unfortunately, most combinatorial optimization problems are NP-hard,
except for some special cases such as fundamental network problems (see, for
example [1, 20]). In many practical applications, the exact values of the
element costs are unknown. The method of handling this uncertainty mainly
depends on the knowledge available. In many situations, it is only possible to
specify an uncertainty set $\mathcal{U}$ which contains possible values of
uncertain costs. Then, some robust criteria, such as the min-max or the min-
max regret, can be used to compute a solution [19]. However, additional
knowledge in the scenario set is available in many situations. For example,
some bounds on mean and covariance matrix [6], or a family of confidence sets
for the random cost vector can be specified [24]. Also, a sample of
realizations of the random cost vector can be available. In all of these
cases, one can define a set of admissible probability distributions for the
random cost vector. Using a robust distributionally framework, we can minimize
some risk measure for the worst probability distribution in this set. A risk
measure commonly used in stochastic optimization is the Conditional Value at
Risk (CVaR) [21, 22]. The CVaR is a convex coherent risk measure that has a
nice interpretation and possesses many favorable computational properties.

When a sample of the random cost vector is available, then the Wasserstein
metric [15] can be used to define a set of admissible probability
distributions. The Wasserstein metric defines a distance between two
probability distributions on the same support set. A Wasserstein ball contains
then all probability distributions that are of some prescribed distance to the
empirical distribution, which is defined by the available sample of the random
cost vector. The Wasserstein ball contains all admissible probability
distributions, and the robust distributionally framework can be used to
compute a solution [8, 10]. The approach based on the Wasserstein distance can
be attractive when the sample size is small. In particular, it may outperform
the approach based on the sample average approximation [8].

Our paper is motivated by the paper by Wang et al. [23], in which the
Wasserstein robust approach has been applied to the shortest path problem. The
authors provided in [23] various mathematical programming formulations and
showed the results of some computational tests. In this paper, we generalize
the results obtained in [23] to all combinatorial problems. In particular, we
generalize the method of computing a worst probability distribution for a
given solution and the mathematical programming formulation for the
unrestricted support set. We also consider the problem with more restricted
support sets. In the simplest case, lower and upper bounds for the costs are
known, and the support set is a hyperrectangle in $\mathbb{R}^{n}_{+}$. We
refine the results for such a support set shown in [23]. Generally, any
closed, convex, and bounded support set (for example, an ellipsoid in
$\mathbb{R}^{n}_{+}$) can be used. For this case, we propose a row generation
algorithm, which can be applied when the sample size is not large. We also
propose a more efficient method of constructing a solution consisting of
solving the CVaR-optimization problem for an appropriately distorted sample.
We show that this algorithm can provide an approximate solution to the robust
Wasserstein problem. Finally, we also investigate the computational complexity
of the problem. We show that it is strongly NP-hard for most basic problems,
particularly for the shortest path problem discussed in [23]. We also present
the results of some computational tests. This paper is a significantly
extended version of the results presented in [13].

This paper is organized as follows. In Section 2, we present the problem
formulation. We also show how the problem can be reformulated in a more
tractable way, based on a characterization of the worst probability
distribution. In Section 3, we investigate the complexity of the problem. We
prove that the Wasserstein robust problem is strongly NP-hard for most basic
problems (particularly for the shortest path), except when CVaR is the
expectation. In Section 4, we propose various methods of solving the problem.
In Section 4.1, we discuss the case of unrestricted support set, i.e. when any
realization of cost in $\mathbb{R}^{n}_{+}$ can occur. We show a mathematical
programming formulation for this case and propose some exact and approximate
methods of solving it. In Section 4.2, we consider a simple case of restricted
support being a hyperrectangle in $\mathbb{R}^{n}_{+}$. We refine the known
results for this support set. In Section 4.3, we consider the problem with an
arbitrary closed, convex, and bounded support set, and we propose a row
generation algorithm for that case. In Section 4.3.1, we construct a more
efficient approximation algorithm and prove its approximation guarantee.
Finally, Section 5 contains the results of some computational tests for the
0-1 Knapsack problem.

##  2 Problem formulation

Consider the following combinatorial optimization problem:

$\mathcal{P}:\;\;\min_{\boldsymbol{x}\in\mathcal{X}}\;\boldsymbol{\xi}^{T}\boldsymbol{x},$

where $\mathcal{X}\subseteq\\{0,1\\}^{n}$ is a set of feasible solutions and
$\boldsymbol{\xi}\in\mathbb{R}_{+}^{n}$ is a given nonnegative cost vector.
Typically, $\mathcal{X}$ is described by a system of linear constraints of the
form $\boldsymbol{A}\boldsymbol{x}\geq\boldsymbol{b}$, for some fixed matrix
$\boldsymbol{A}\in\mathbb{R}^{m\times n}$ and vector
$\boldsymbol{b}\in\mathbb{R}^{m}$, with $\boldsymbol{x}\in\\{0,1\\}^{n}$. In
general, problem $\mathcal{P}$ is NP-hard, and only some special cases are
known to be polynomially solvable. One such a particular case is when the
matrix $~{}\boldsymbol{A}$ is totally unimodular, for example, when
$\mathcal{P}$ is the Shortest Path or the Minimum Assignment (see [1, 20]).

In practice, the true realization of the cost vector $\boldsymbol{\xi}$ is
often unknown before the optimal solution $\boldsymbol{x}$ to $\mathcal{P}$
must be determined. It should be rather regarded as a random vector
$\tilde{\boldsymbol{\xi}}$ with a probability distribution $\mathbb{P}$
supported on $\Xi\subseteq\mathbb{R}^{n}_{+}$. In this paper, we assume that
the support set $\Xi$ is convex. If $\Xi=\mathbb{R}^{n}_{+}$, then we say that
the support set is unrestricted. However, $\Xi$ can be restricted to a closed
and bounded set in many practical situations. In this case, $\Xi$ coincides
with an uncertainty set commonly used in robust optimization [2]. Vector
$\tilde{\boldsymbol{\xi}}$ induces a random cost
$\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}$ of solution
$\boldsymbol{x}\in\mathcal{X}$. To choose a solution, a risk measure that
assigns a real value to random solution cost should be used [14]. In this
paper, we will apply the following Conditional Value at Risk (Expected
Shortfall) [21, 22], which is commonly used in stochastic optimization (see,
e.g. [14]):

${\rm
CVaR}^{\alpha}_{\mathbb{P}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]=\inf\left\\{t\in\mathbb{R}:t+\frac{1}{\alpha}{\rm
E}_{\mathbb{P}}([\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}-t]_{+})\right\\}=\inf\left\\{t\in\mathbb{R}:t+\frac{1}{\alpha}\int_{\Xi}[\boldsymbol{\xi}^{T}\boldsymbol{x}-t]_{+}\mathbb{P}({\rm
d}\boldsymbol{\xi})\right\\},$ (1)

where $\alpha\in(0,1]$ is a fixed risk level, ${\rm E}_{\mathbb{P}}[\cdot]$ is
the expected value with respect to the probability distribution $\mathbb{P}$
and $[x]_{+}=\max\\{0,x\\}$. Note that for $\alpha=1$, the Conditional Value
at Risk is the expected solution cost ${\rm
E}_{\mathbb{P}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]$. Given a
probability distribution $\mathbb{P}$ for $\tilde{\boldsymbol{\xi}}$, we seek
a solution minimizing the Conditional Value at Risk at a given risk level
$\alpha\in(0,1]$, that is, we solve the following problem:

$\text{CVaR}~{}\mathcal{P}:\;\;\begin{array}[]{lll}\min&{\rm
CVaR}^{\alpha}_{\mathbb{P}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]\\\
&\boldsymbol{A}\boldsymbol{x}\geq\boldsymbol{b},\\\
&\boldsymbol{x}\in\\{0,1\\}^{n}.\end{array}$ (2)

In practical applications, the true probability distribution $\mathbb{P}$ in
problem (2) is rarely known exactly. Suppose that we have sample
$\hat{\boldsymbol{\xi}}_{1},\dots,\hat{\boldsymbol{\xi}}_{N}$ of
$\tilde{\boldsymbol{\xi}}$, which induces the empirical probability
distribution

$\widehat{\mathbb{P}}^{N}:=\frac{1}{N}\sum_{i=1}^{N}\delta_{\hat{\boldsymbol{\xi}}_{i}},$
(3)

where $\delta_{\boldsymbol{\xi}_{i}}$ is a Dirac distribution concentrating
unit mass at $\boldsymbol{\xi}_{i}\in\Xi$. In this paper we will use a more
convenient notation
$\widehat{\mathbb{P}}^{N}:=(\hat{\boldsymbol{\xi}}_{1},\dots,\hat{\boldsymbol{\xi}}_{N})$,
so we will identify $\widehat{\mathbb{P}}^{N}$ with a vector of realizations
$(\hat{\boldsymbol{\xi}}_{1},\dots,\hat{\boldsymbol{\xi}}_{N})$. We will
generally use the notation
$\mathbb{P}^{N}:=(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})$ to denote
a discrete probability distributions in $\Xi$, defined analogously as (3). The
indexed vectors
$\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N}\in\mathbb{R}^{n}_{+}$ are
realizations of the random vector $\tilde{\boldsymbol{\xi}}$. We point out
that some realizations in $\mathbb{P}^{N}$ can be repeated, which leads to a
nonuniform discrete probability distribution.

Given two probability distribution $\mathbb{Q}_{1}$ and $\mathbb{Q}_{2}$
supported on $\Xi$, we define the Wasserstein distance between them as follows
[15]:

$d_{W}(\mathbb{Q}_{1},\mathbb{Q}_{2})=\inf\left\\{\int_{\Xi\times\Xi}||\boldsymbol{\xi}_{1}-\boldsymbol{\xi}_{2}||_{q}\Pi({\rm
d}\boldsymbol{\xi}_{1},{\rm d}\boldsymbol{\xi}_{2}):\overset{\Pi\text{ is a
joint probability distribution in }\Xi\times\Xi}{\footnotesize\text{with
marginals }\tiny\mathbb{Q}_{1},\mathbb{Q}_{2}}\right\\},$

where $||\boldsymbol{v}||_{q}=(\sum_{i=1}^{n}|v_{i}|^{q})^{1/q}$ is the
$q$-norm in $\mathbb{R}^{n}$ for $q\in\overline{\mathbb{R}}_{\geq
1}=\mathbb{R}_{\geq 0}\cup\\{\infty\\}$. Using the Wasserstein distance, we
can define the following ambiguity set of probability distributions (also
called a Wasserstein ball) [8]:

$\mathbb{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})=\\{\mathbb{Q}\in\mathcal{M}(\Xi):d_{W}(\widehat{\mathbb{P}}^{N},\mathbb{Q})\leq\epsilon\\},$

where $\mathcal{M}(\Xi)$ is the set of all probability distributions in $\Xi$
and $\epsilon\geq 0$ is a given constant. The following theorem provides the
foundations for establishing a finite sample guarantees:

######  Theorem 1 ([8, 9]).

Assume that there exists $a>1$ such that

$A=\int_{\Xi}{\rm exp}(||\boldsymbol{\xi}||^{a})\mathbb{P}({\rm
d}\boldsymbol{\xi})<\infty.$

Then the true probability distribution $\mathbb{P}$ belongs to
$\mathbb{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$ with the confidence
$1-\beta$ for a fixed $\beta\in(0,1)$, where

$\epsilon=\left\\{\begin{array}[]{llll}\left(\frac{\log(c_{1}\beta^{-1})}{c_{2}N}\right)^{1/\max\\{n,2\\}}&\text{if}&N\geq\frac{\log(c_{1}\beta^{-1}}{c_{2}}),\\\
\left(\frac{\log(c_{1}\beta^{-1})}{c_{2}N}\right)^{1/a}&\text{if}&N<\frac{\log(c_{1}\beta^{-1}}{c_{2}}),\end{array}\right.$

and $c_{1},c_{2}$ are positive constants that depend on $A$, $a$ and $n$.

Given an empirical distribution $\widehat{\mathbb{P}}^{N}$ and $\epsilon\geq
0$, we consider the following distributionally robust problem [8]:

$\textsc{Distr}~{}\mathcal{P}:\;\;\begin{array}[]{lll}\min&\displaystyle\sup_{\mathbb{P}\in\mathbb{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}{\rm
CVaR}^{\alpha}_{\mathbb{P}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]\\\
&\boldsymbol{A}\boldsymbol{x}\geq\boldsymbol{b},\\\
&\boldsymbol{x}\in\\{0,1\\}^{n}.\end{array}$ (4)

If the supremum in (4) is attained by some probability distribution
$\mathbb{P}\in\mathbb{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$, then
$\mathbb{P}$ is called a worst probability distribution for $\boldsymbol{x}$.
In this paper, we will use the following lemma, which was originally proven
for the Shortest Path problem in [23, Lemma 2]. We extend the result [23] for
a general combinatorial problem $\mathcal{P}$.

######  Lemma 1.

For each solution $\boldsymbol{x}\in\mathcal{X}$, there is a worst probability
distribution which belongs to

$\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})=\\{\mathbb{P}^{N}=(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N}):\sum_{i=1}^{N}||\boldsymbol{\xi}_{i}-\hat{\boldsymbol{\xi}}_{i}||_{q}\leq
N\epsilon,\;\boldsymbol{\xi}_{i}\in\Xi,i\in[N]\\},$

where $[N]$ denotes the set $\\{1,\dots,n\\}$.

###### Proof.

See Appendix A. ∎

Lemma 1 shows that the worst probability distribution for a given solution
$\boldsymbol{x}$ is a discrete one and belongs to the closed, bounded and
convex set $\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$. The set
$\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$ has a nice description,
which we will exploit in the next part of the paper. Using Lemma 1, we can
represent (4) as the following optimization problem:

$\textsc{Distr}~{}\mathcal{P}:\;\;\begin{array}[]{lll}\min&\displaystyle\max_{\mathbb{P}^{N}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}{\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]\\\
&\boldsymbol{A}\boldsymbol{x}\geq\boldsymbol{b},\\\
&\boldsymbol{x}\in\\{0,1\\}^{n}.\end{array}$ (5)

In the next part of this paper, we will investigate the properties of the
$\textsc{Distr}~{}\mathcal{P}$ problem, using the formulation (5).

##  3 Minimizing the Conditional Value at Risk

Observe that $\textsc{Distr}~{}\mathcal{P}$ reduces to
$\textsc{CVaR}~{}\mathcal{P}$ for $\mathbb{P}=\widehat{\mathbb{P}}^{N}$ when
$\epsilon=0$. In this section we will focus on solving
$\textsc{CVaR}~{}\mathcal{P}$, i.e. on minimizing the Conditional Value at
Risk for a given discrete probability distribution
$\mathbb{P}^{N}=(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})$. We will
show some complexity and approximation results, which will be used to
characterize the computational properties of the more general
$\textsc{Distr}~{}\mathcal{P}$ problem. The $\textsc{CVaR}~{}\mathcal{P}$
problem for $\mathbb{P}^{N}=(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})$
can be represented as the following mixed integer program:

$\begin{array}[]{lll}\min&\displaystyle t+\frac{1}{\alpha
N}\sum_{i=1}^{N}u_{i}\\\ &\boldsymbol{\xi}_{i}^{T}\boldsymbol{x}-t\leq
u_{i},&i\in[N],\\\ &\boldsymbol{A}\boldsymbol{x}\geq\boldsymbol{b},\\\
&\boldsymbol{x}\in\\{0,1\\}^{n},\\\ &u_{i}\geq 0&i\in[N].\end{array}$ (6)

Here and subsequently, we will make use of the fact that the Conditional Value
at Risk is a special case of the Ordered Averaging Aggregation (OWA) criterion
introduced in [25]. Let $\boldsymbol{w}=(w_{1},\dots,w_{N})$ be a vector of
nonnegative weights such that $w_{1}+\dots+w_{N}=1$. The OWA criterion for
$\mathbb{P}^{N}=(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})$ is defined
as follows:

${\rm
Owa}^{\boldsymbol{w}}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]=\sum_{i=1}^{N}w_{i}\boldsymbol{\xi}_{\sigma(i)}^{T}\boldsymbol{x},$
(7)

where $\sigma$ is a permutation of $[N]$ such that
$\boldsymbol{\xi}^{T}_{\sigma(1)}\boldsymbol{x}\geq\boldsymbol{\xi}^{T}_{\sigma(2)}\boldsymbol{x}\geq\dots\geq\boldsymbol{\xi}^{T}_{\sigma(N)}\boldsymbol{x}$.

######  Proposition 1.

Assume that $\alpha\in(\frac{l-1}{N},\frac{l}{N}]$ for $l\in[N]$. Then

${\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]={\rm
Owa}^{\boldsymbol{w}}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}],$

where

$\boldsymbol{w}=\left\\{\begin{array}[]{lll}(1,0,\dots,0)&\text{if}&\alpha<\frac{1}{N},\\\
(\underbrace{\frac{1}{\alpha N},\dots,\frac{1}{\alpha N},1-\frac{l-1}{\alpha
N}}_{l\text{ positive weights}},\underbrace{0,\dots,0}_{N-l\text{
weights}})&\text{if}&\alpha\geq\frac{1}{N}.\end{array}\right.$ (8)

###### Proof.

Fix $\boldsymbol{x}\in\mathcal{X}$ and
$\mathbb{P}^{N}=(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})$. Assume
that
$\boldsymbol{\xi}^{T}_{1}\boldsymbol{x}\geq\boldsymbol{\xi}^{T}_{2}\boldsymbol{x}\geq\dots\geq\boldsymbol{\xi}^{T}_{N}\boldsymbol{x}$.
Using (6), let us rewrite ${\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]$
as the following linear programming problem:

$\begin{array}[]{llll}\min&\displaystyle t+\frac{1}{\alpha
N}\sum_{i=1}^{N}u_{i}\\\
&u_{i}+t\geq\boldsymbol{\xi}_{i}^{T}\boldsymbol{x},&i\in[N],\\\ &u_{i}\geq
0,&i\in[N].\end{array}$ (9)

The dual to (9) with dual variables $w_{i}$, $i\in[N]$, is

$\begin{array}[]{llll}\max&\displaystyle\sum_{i=1}^{N}\boldsymbol{\xi}^{T}_{i}\boldsymbol{x}w_{i}\\\
&\displaystyle\sum_{i=1}^{N}w_{i}=1,\\\ &0\leq w_{i}\leq\frac{1}{\alpha
N},&i\in[N].\end{array}$ (10)

The dual (10) can be solved using the following greedy method. If
$\frac{1}{\alpha N}>1$ (so $\alpha<\frac{1}{N}$), then we set $w_{1}=1$ and
$w_{i}=0$ for $i=2,\dots,N$. If $\frac{1}{\alpha N}\leq 1$, then we set
$w_{i}=\frac{1}{N\alpha}$ for $i=1,\dots,l-1$, $w_{l}=1-\frac{l-1}{\alpha N}$,
and $w_{i}=0$ for $i=l+1,\dots,N$. Hence, the optimal objective value of the
dual equals (7) with the weights defined as (8). By the linear programming
strong duality, the proposition follows. ∎

Observe that if $\alpha=\frac{l}{N}$ for some $l=1,\dots,N$, then ${\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]$
is just the average of the $l$ largest solution costs under
$\mathbb{P}^{N}=(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})$. Using
Proposition 1, we now characterize the complexity of
$\textsc{CVaR}~{}\mathcal{P}$ for some generic combinatorial optimization
problem $\mathcal{P}$. Namely, assume that $\mathcal{P}$ is the following
Representatives Selection problem (RS for short), in which we are given a set
$\mathcal{T}$ of $n$ tools, numbered from $1$ to $n$. This set is partitioned
into $\ell$ disjoint sets $T_{1},\ldots,T_{\ell}$. We wish to choose a subset
of the tools $\mathcal{T}$ that contains exactly one tool from each set
$T_{i}$, $i\in[\ell]$. In the deterministic case, each tool $j\in T$ has a
nonnegative cost $\xi_{j}$, and we seek a subset of the tools (a solution)
whose total cost is minimum. Clearly, the set of feaslible solutions
$\mathcal{X}_{s}$ can be described by the constraints $\sum_{j\in
T_{i}}x_{j}=1$ for each $i\in[\ell]$. It is easily seen that the RS problem,
in this case has a trivial solution, which can be constructed by setting
$x_{j_{i}}=1$, where $j_{i}$ is the index of the variable in $T_{i}$ with the
smallest cost under $\boldsymbol{\xi}=(\xi_{1},\ldots,\xi_{n})$. In the Min-
Max RS problem, we are given a set
$\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{K}\in\mathbb{R}_{+}^{n}$ of
realizations of the cost vector and we seek a solution minimizing the largest
cost, i.e. we solve the following problem:

$\min_{\boldsymbol{x}\in\mathcal{X}_{s}}\max_{i\in[K]}\boldsymbol{\xi}_{i}^{T}\boldsymbol{x}.$

The Min-Max RS problem has been investigated in [5, 7, 16]. In particular, it
has been shown that it is strongly NP-hard when $K$ is a part of the input. We
consider now the CVaR RS problem, i.e. the problem (6) with $\mathcal{X}_{s}$
and a fixed $\alpha\in(0,1]$.

######  Theorem 2.

The CVaR RS problem is strongly NP-hard for each $\alpha\in(0,1)$ when $K$ is
a part of the input.

###### Proof.

Given an instance
$(n,\mathcal{T},\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{K})$ of Min-Max
RS and $\alpha\in(0,1)$, we construct the corresponding instance
$(n^{\prime},\mathcal{T}^{\prime},\mathbb{P}^{N},\alpha)$ of CVaR RS as
follows. Let $n^{\prime}=n+1$ and $\mathcal{T}^{\prime}=\mathcal{T}\cup
T_{0}$, where $T_{0}=\\{n+1\\}$. This forms a set
$\mathcal{X}^{\prime}_{s}\in\\{0,1\\}^{n+1}$. Observe that $x_{n+1}=1$ in any
feasible solution $\boldsymbol{x}\in\mathcal{X}^{\prime}_{s}$. Let
$l=\lceil\frac{K\alpha}{1-\alpha}\rceil$ and fix $N=K+l-1$. Define the
probability distribution

$\mathbb{P}^{N}=(\boldsymbol{\xi}^{\prime}_{1},\dots,\boldsymbol{\xi}^{\prime}_{K},\underbrace{\boldsymbol{\zeta},\dots,\boldsymbol{\zeta}}_{l-1\text{
copies}}),$

where the costs of the variables $x_{i}$, $i\in[n]$, under
$\boldsymbol{\xi}^{\prime}_{i}$ are the same as under $\boldsymbol{\xi}_{i}$
and the cost of $x_{n+1}$ is 0; the costs of the variables $x_{i}$, $i\in[n]$,
under $\boldsymbol{\zeta}$ are 0 and the cost of $x_{n+1}$ is equal to a large
constant $M$ (we can choose, for example,
$M=\sum_{i=1}^{K}||\boldsymbol{\xi}_{i}||_{1}$). Using the equality $\lceil
x\rceil=x+r$ for $r\in[0,1)$, we get

$\frac{l-1}{N}=\frac{\lceil\frac{K\alpha}{1-\alpha}\rceil-1}{K+\lceil\frac{K\alpha}{1-\alpha}\rceil-1}=\frac{\frac{K\alpha}{1-\alpha}+r-1}{K+\frac{K\alpha}{1-\alpha}+r-1}=\frac{K\alpha+(1-\alpha)(r-1)}{K+(1-\alpha)(r-1)}<\alpha,$

where the inequality follows from the fact that $\alpha,r\in[0,1)$ and thus
$(1-\alpha)(r-1)\in[-1,0)$. We also obtain

$\frac{l}{N}=\frac{\lceil\frac{K\alpha}{1-\alpha}\rceil}{K+\lceil\frac{K\alpha}{1-\alpha}\rceil-1}\geq\frac{\frac{K\alpha}{1-\alpha}}{K+\frac{K\alpha}{1-\alpha}}=\alpha$

Hence $\alpha\in(\frac{l-1}{N},\frac{l}{N}]$. Using Proposition 1, we get for
any solution $\boldsymbol{x}\in\mathcal{X}^{\prime}_{s}$:

${\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]=\underbrace{\frac{1}{\alpha
N}M+\dots+\frac{1}{\alpha N}M}_{l-1\text{ times }}+(1-\frac{l-1}{\alpha
N})\boldsymbol{\xi}_{\sigma(1)}^{T}\boldsymbol{x},$

where
$\boldsymbol{\xi}_{\sigma(1)}^{T}\boldsymbol{x}=\max_{i\in[K]}\boldsymbol{\xi}_{i}^{T}\boldsymbol{x}$.
Note that $(1-\frac{l-1}{\alpha N})>0$, since there are $l$ positive weights
in (8) (see Proposition 1). Thus, there is a solution to Min-Max RS with the
maximum cost at most $c$ if and only if there is a solution to CVaR RS with
the Conditional Value at Risk at most $\frac{(l-1)M}{\alpha
N}+(1-\frac{l-1}{\alpha N})c$. ∎

Since for $\epsilon=0$, $\textsc{Distr}~{}\mathcal{P}$ is equivalent to
$\textsc{CVaR}~{}\mathcal{P}$, we get the following corollary:

######  Corollary 1.

The Distr RS problem is strongly NP-hard for each $\alpha\in(0,1)$.

The RS problem can be seen as a very special case of other basic combinatorial
optimization problems. In particular, it is a special case of the Shortest
Path problem. To see this, consider the series-parallel graph $G$ shown in
Figure 1.

Figure 1: An instance of the Shortest Path problem, corresponding to RS.

The arcs belonging to the subsequent layers of $G$ correspond to
$T_{1},\dots,T_{\ell}$. The costs of the arcs are equal to the costs of the
tools. It is easy to see that each $s-t$ path corresponds to some solution of
the RS problem and vice versa. Since every $s-t$ path in $G$ is also a
spanning tree of $G$, the same transformation applies to the Minimum Spanning
Tree problem. This leads to the following corollary:

######  Corollary 2.

The Distr Shortest Path and Distr Spanning Tree problems are strongly NP-hard
in series-parallel graphs for each $\alpha\in(0,1)$.

The $\textsc{CVaR}~{}\mathcal{P}$ problem for $\alpha=1$ reduces to minimizing
the expected solution cost. In this case, the problem with
$\mathbb{P}^{N}=(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})$ easily
reduces to solving the deterministic problem $\mathcal{P}$ with the aggregated
cost vector
$\hat{\boldsymbol{\xi}}=\frac{1}{N}\sum_{i=1}^{N}\boldsymbol{\xi}_{i}$. Hence,
the complexity of $\textsc{CVaR}~{}\mathcal{P}$ for $\alpha=1$ is then the
same as the complexity of $\mathcal{P}$. It has been shown in [17] that
solving $\mathcal{P}$ for the aggregated cost vector $\hat{\boldsymbol{\xi}}$
yields a $w_{1}N$-approximate solution to the problem of minimizing OWA with
nonincreasing weights, i.e. $w_{1}\geq w_{2}\geq\dots\geq w_{N}$. Using
Proposition 1 we conclude that $w_{1}=\min\\{1,\frac{1}{\alpha N}\\}$, so the
approximation ratio becomes $\min\\{N,\frac{1}{\alpha}\\}$. We have thus
established the following result:

######  Proposition 2.

If $\mathcal{P}$ can be solved in polynomial time, then
$\textsc{CVaR}~{}\mathcal{P}$ with $\alpha\in(0,1)$ is approximable within
$\min\\{N,\frac{1}{\alpha}\\}$.

##  4 Solving the Wasserstein distributionally robust problem

In this section, we will propose some exact and approximate methods of solving
the $\textsc{Distr}~{}\mathcal{P}$ problem. We will consider the problem with
various $q$-norms, $q\in\overline{\mathbb{R}}_{\geq 1}$, and support sets
$\Xi$. We start with the case when $\Xi=\mathbb{R}^{n}_{+}$. Then, we will
consider a support $\Xi$ being a hyperrectangle in $\mathbb{R}^{n}_{+}$ (such
a model has been considered in [23]). Finally, we will show some results for
any convex, closed, and bounded support $\Xi$.

###  4.1 The support set $\Xi=\mathbb{R}^{n}_{+}$

The following theorem is a generalization of the result obtained in [23]:

######  Theorem 3.

If $\Xi=\mathbb{R}^{n}_{+}$, then $\textsc{Distr}~{}\mathcal{P}$ can be
expressed as

$\begin{array}[]{lll}\min&{\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]+\gamma\epsilon||\boldsymbol{x}||_{q^{\prime}}\\\
&\boldsymbol{A}\boldsymbol{x}\geq\boldsymbol{b},\\\
&\boldsymbol{x}\in\\{0,1\\}^{n},\end{array}$ (11)

where $\gamma=N$ if $\alpha<\frac{1}{N}$, $\gamma=\frac{1}{\alpha}$ if
$\alpha\geq\frac{1}{N}$, and $||\cdot||_{q^{\prime}}$ is the dual norm to
$||\cdot||_{q}$, i.e. $\frac{1}{q}+\frac{1}{q^{\prime}}=1$.

###### Proof.

See Appendix A. ∎

If $q=1$, then (11) reduces to minimizing the Conditional Value at Risk for
the empirical distribution $\widehat{\mathbb{P}}^{N}$. Indeed, the dual norm
$||\boldsymbol{x}||_{\infty}$ is either 0 (when
$\boldsymbol{x}=\boldsymbol{0}$) or 1 (when
$\boldsymbol{x}\neq\boldsymbol{0})$ and the second component in the objective
function of (11) is constant. If $q=\infty$, then
$||\boldsymbol{x}||_{1}=\sum_{i=1}^{n}x_{i}$ and (11) becomes a mixed integer
program. Consider now the case of arbitrary $q\in\overline{\mathbb{R}}_{\geq
1}$. Since
$||\boldsymbol{x}||_{q^{\prime}}=(\sum_{i=1}^{n}x_{i})^{\frac{q}{q-1}}$, the
model (11) can be converted to

$\begin{array}[]{lll}\min&\displaystyle t+\frac{1}{\alpha
N}\sum_{i=1}^{N}u_{i}+\lambda^{\frac{q-1}{q}}\gamma\epsilon\\\
&\hat{\boldsymbol{\xi}}_{i}^{T}\boldsymbol{x}-t\leq u_{i},&i\in[N]\\\
&\boldsymbol{A}\boldsymbol{x}\geq\boldsymbol{b},\\\
&\displaystyle\sum_{i=1}^{n}x_{i}\leq\lambda,\\\
&\boldsymbol{x}\in\\{0,1\\}^{n},\\\ &u_{i}\geq 0,&i\in[N]\\\ &\lambda\geq
0.\end{array}$ (12)

In the formulation (12) we use (6) to represent ${\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]$.
In any optimal solution to (12) we can fix $\lambda=\sum_{i=1}^{n}x_{i}$ and
thus $\lambda=||\boldsymbol{x}||_{q^{\prime}}$. Hence the optimal value of
$\lambda$ is integer and takes one of the values in
$\Lambda=\\{n_{\min},\dots,n_{\max}\\}$, where $n_{\min}$ and $n_{\max}$ are
the minimum and the maximum cardinality of solution
$\boldsymbol{x}\in\mathcal{X}$, respectively. Thus, we need to solve (12) for
each fixed $\lambda\in\Lambda$ and choose a solution with the minimum value of
the objective function. Hence, (12) can be solved by solving a family of mixed
integer programs. If $\alpha=1$, then model (13) reduces to (see also [18])

$\begin{array}[]{lll}\min&\displaystyle{\rm
E}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]+\epsilon||\boldsymbol{x}||_{q^{\prime}}=\hat{\boldsymbol{\xi}}^{T}\boldsymbol{x}+\epsilon||\boldsymbol{x}||_{q^{\prime}}\\\
&\boldsymbol{A}\boldsymbol{x}\geq\boldsymbol{b},\\\
&\boldsymbol{x}\in\\{0,1\\}^{n},\end{array}$ (13)

where
$\hat{\boldsymbol{\xi}}=\frac{1}{N}\sum_{i=1}^{N}\hat{\boldsymbol{\xi}}_{i}$,
which can be represented equivalently as

$\begin{array}[]{lll}\min&\displaystyle\hat{\boldsymbol{\xi}}^{T}\boldsymbol{x}+\lambda^{\frac{q-1}{q}}\epsilon\\\
&\boldsymbol{A}\boldsymbol{x}\geq\boldsymbol{b},\\\
&\displaystyle\sum_{i=1}^{n}x_{i}\leq\lambda,\\\
&\boldsymbol{x}\in\\{0,1\\}^{n},\\\ &\lambda\geq 0.\end{array}$ (14)

Sometimes, (13) can be solved in polynomial time. Indeed, when $\mathcal{P}$
is polynomially solvable and $q=1$ or $q=\infty$. In the former case the term
$||\boldsymbol{x}||_{q^{\prime}}$ is constant, while in the latter case
$||\boldsymbol{x}||_{q^{\prime}}=\sum_{i=1}^{n}x_{i}$, which leads to a linear
objective function in (13). For arbitrary $q$, we can solve the formulation
(14) for each $\lambda\in\Lambda$, which can also be done in polynomial time
for some problems $\mathcal{P}$. For example, when $\mathcal{P}$ is the
Shortest Path, then (14) can be solved by solving a family of the Constrained
Shortest Path problems with all arc weights equal to 1 in the budget
constraint $\sum_{i=1}^{n}x_{i}\leq\lambda$. Such a special case of this
problem can be solved in polynomial time [11]. In [18] and alternative method
of solving (13) has been proposed. This method consists of solving a family of
$n+1$ deterministic problems $\mathcal{P}$ with some suitably chosen cost
vectors. However, our alternative approach is easier and also leads to
efficient solution methods for some particular problems.

######  Proposition 3.

If $(\ref{mod01})$ can be solved in polynomial time, then (11) is approximable
within $\gamma=\min\\{N,\frac{1}{\alpha}\\}$

###### Proof.

We will show first that for each $\alpha\in(0,1]$

${\rm
E}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]\leq{\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]\leq\gamma{\rm
E}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}].$
(15)

The first inequality in (15) easily follows from the definition of the
Conditional Value at Risk. To prove the second inequality, we will use
Proposition 1. If $\alpha<\frac{1}{N}$ (hence $N<\frac{1}{\alpha}$), then

${\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]=\hat{\boldsymbol{\xi}}_{\sigma(1)}^{T}\boldsymbol{x}\leq\sum_{i=1}^{N}\hat{\boldsymbol{\xi}}_{i}^{T}\boldsymbol{x}=N\cdot{\rm
E}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}].$

If $\alpha\geq\frac{1}{N}$ (hence $N\geq\frac{1}{\alpha}$), then

${\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]\leq\frac{1}{\alpha
N}\sum_{i=1}^{N}\hat{\boldsymbol{\xi}}_{i}^{T}\boldsymbol{x}=\frac{1}{\alpha}{\rm
E}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}],$

which yields (15). Let $\boldsymbol{x}^{\prime}$ be an optimal solution to
(13) and let $\boldsymbol{x}^{*}$ be an optimal solution to (11). Using (15)
and the fact that $\gamma\geq 1$ we obtain

$\frac{1}{\gamma}({\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{\prime}]+\gamma\epsilon||\boldsymbol{x}^{\prime}||_{q^{\prime}})\leq{\rm
E}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{\prime}]+\epsilon||\boldsymbol{x}^{\prime}||_{q^{\prime}}\leq{\rm
E}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{*}]+\epsilon||\boldsymbol{x}^{*}||_{q^{\prime}}\leq$
${\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{*}]+\gamma\epsilon||\boldsymbol{x}^{*}||_{q^{\prime}},$

which completes the proof. ∎

###  4.2 The support set $\Xi_{\boldsymbol{a},\boldsymbol{b}}$ and $q=1$

In this section, we examine the model investigated in [23], where the support
set is defined as
$\Xi_{\boldsymbol{a},\boldsymbol{b}}=\\{\boldsymbol{\xi}\in\mathbb{R}^{n}_{+}:\boldsymbol{a}\leq\boldsymbol{\xi}\leq\boldsymbol{b}\\}$,
so lower $\boldsymbol{a}\in\mathbb{R}_{+}^{n}$ and upper
$\boldsymbol{b}\in\mathbb{R}_{+}^{n}$ bounds on the costs are known. To solve
$\textsc{Distr}~{}\mathcal{P}$ for this support set, some mixed integer
programs have been constructed in [23]. In this section, we will show how the
programs can be simplified. Furthermore, a special case with $q=1$ can be
solved more efficiently.

If $\hat{\boldsymbol{\xi}}_{i}\in\Xi_{\boldsymbol{a},\boldsymbol{b}}$ for each
$i\in[N]$, then an optimal solution to $\textsc{Distr}~{}\mathcal{P}$ will not
change if we replace $\Xi_{\boldsymbol{a},\boldsymbol{b}}$ with
$\Xi_{\boldsymbol{0},\boldsymbol{b}}$, that is we fix the lower bounds
$\boldsymbol{a}=\boldsymbol{0}$. Indeed, a worst probability distribution
$\mathbb{P}^{N}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$ for
$\boldsymbol{x}$ is of the form
$\mathbb{P}^{N}=(\hat{\boldsymbol{\xi}}_{1}+\boldsymbol{\Delta}_{1},\dots,\hat{\boldsymbol{\xi}}_{N}+\boldsymbol{\Delta}_{N})$,
where $\boldsymbol{\Delta}_{i}\in\mathbb{R}^{n}_{+}$ for $i\in[N]$ (all the
components of $\boldsymbol{\Delta}_{i}$ are nonnegative). Therefore
$\mathbb{P}^{N}$ is still a worst probability distribution for
$\boldsymbol{x}$ if we fix $\boldsymbol{a}=\boldsymbol{0}$.

######  Proposition 4.

If the support set is $\Xi_{\boldsymbol{0},\boldsymbol{b}}$,
$\alpha=\frac{l}{N}$ for some $l\in[N]$ and $q=1$, then for each
$\boldsymbol{x}\in\mathcal{X}$

$\max_{\mathbb{P}^{N}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}{\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]=\min\left\\{\boldsymbol{b}^{T}\boldsymbol{x},{\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]+\frac{1}{l}N\epsilon\right\\}.$
(16)

###### Proof.

Fix $\boldsymbol{x}\in\mathcal{X}$ and assume that
$\hat{\boldsymbol{\xi}}_{1}^{T}\boldsymbol{x}\geq\dots\geq\hat{\boldsymbol{\xi}}_{N}^{T}\boldsymbol{x}$.
We show first that

$\max_{\mathbb{P}^{N}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}{\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]\leq\min\left\\{\boldsymbol{b}^{T}\boldsymbol{x},{\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]+\frac{1}{l}N\epsilon\right\\}.$
(17)

Indeed, the inequality
$\max_{\mathbb{P}^{N}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}{\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]\leq\boldsymbol{b}^{T}\boldsymbol{x}$
follows from the fact that $\boldsymbol{b}^{T}\boldsymbol{x}$ is the maximum
cost of $\boldsymbol{x}$ in $\Xi_{\boldsymbol{0},\boldsymbol{b}}$. Using
Proposition 1, we get for each
$\mathbb{P}^{N}=(\hat{\boldsymbol{\xi}}_{1}+\boldsymbol{\Delta}_{1},\dots,\hat{\boldsymbol{\xi}}_{N}+\boldsymbol{\Delta}_{N})\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$

${\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]=\frac{1}{l}\sum_{i=1}^{l}(\hat{\boldsymbol{\xi}}_{\sigma(i)}+\boldsymbol{\Delta}_{\sigma(i)})^{T}\boldsymbol{x}\leq\sum_{i=1}^{l}\hat{\boldsymbol{\xi}}_{i}^{T}\boldsymbol{x}+\frac{1}{l}\sum_{i=1}^{l}||\boldsymbol{\Delta}_{\sigma(i)}||_{1}\leq{\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]+\frac{1}{l}N\epsilon$

and (17) follows. Consider a probability distribution of the form

$\mathbb{P}^{{}^{\prime}N}=(\hat{\boldsymbol{\xi}}_{1}+\boldsymbol{\Delta}_{1},\dots,\hat{\boldsymbol{\xi}}_{l}+\boldsymbol{\Delta}_{l},\hat{\boldsymbol{\xi}}_{l+1},\dots,\hat{\boldsymbol{\xi}}_{N})\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N}),$

where $\sum_{i=1}^{l}||\boldsymbol{\Delta}_{i}||_{1}\leq N\epsilon$,
$\boldsymbol{\Delta}_{i}\geq\boldsymbol{0}$, and $\Delta_{ij}=0$ if $x_{j}=0$
for $i\in[N]$, $j\in[n]$. Using Proposition 1, we get

${\rm
CVaR}^{\alpha}_{\mathbb{P}^{{}^{\prime}N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]=\frac{1}{l}\sum_{i=1}^{l}(\hat{\boldsymbol{\xi}}_{i}+\boldsymbol{\Delta}_{i})^{T}\boldsymbol{x}={\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]+\frac{1}{l}\sum_{i=1}^{l}\boldsymbol{\Delta}_{i}^{T}\boldsymbol{x}={\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]+\frac{1}{l}\sum_{i=1}^{l}||\boldsymbol{\Delta}_{i}||_{1}.$

Consider two cases:

  1. 1.

$\sum_{i=1}^{l}||\boldsymbol{\Delta}_{i}||_{1}<N\epsilon$. This means that
either
$(\hat{\boldsymbol{\xi}}_{i}+\boldsymbol{\Delta}_{i})^{T}\boldsymbol{x}=\boldsymbol{b}^{T}\boldsymbol{x}$
for each $i=1,\dots,l$ or we can further increase $\Delta_{ij}$ for some
$x_{j}=1$ so that $\sum_{i=1}^{l}||\boldsymbol{\Delta}_{i}||_{1}=N\epsilon$
(and we go to Case 2). In the former case (see Proposition 1)

${\rm
CVaR}^{\alpha}_{\mathbb{P}^{{}^{\prime}N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]=\boldsymbol{b}^{T}\boldsymbol{x}\leq{\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]+\frac{1}{l}N\epsilon.$

  2. 2.

$\sum_{i=1}^{l}||\boldsymbol{\Delta}_{i}||_{1}=N\epsilon$. Then

${\rm
CVaR}^{\alpha}_{\mathbb{P}^{{}^{\prime}N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]={\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]+\frac{1}{l}N\epsilon\leq\boldsymbol{b}^{T}\boldsymbol{x},$

where the last inequality follows from the fact that
$\boldsymbol{b}^{T}\boldsymbol{x}$ is an upper bound on ${\rm
CVaR}^{\alpha}_{\mathbb{P}^{{}^{\prime}N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]$.

The above cases show that equality in (17) holds. ∎

We can find an optimal solution to $\textsc{Distr}~{}\mathcal{P}$ for the
problem satisfying the assumptions of Proposition 4 by solving two easier
problems. Let $\boldsymbol{x}_{1}\in\mathcal{X}$ minimize
$\boldsymbol{b}^{T}\boldsymbol{x}$ and $\boldsymbol{x}_{2}\in\mathcal{X}$
minimize ${\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]$.
Solution $\boldsymbol{x}_{1}$ can be found be solving the deterministic
problem $\mathcal{P}$, while $\boldsymbol{x}_{2}$ can be computed using the
MIP formulation (6). Let $\boldsymbol{x}^{\prime}$ be the solution among
$\boldsymbol{x}_{1}$, $\boldsymbol{x}_{2}$ that has smaller value of (16)
breaking ties arbitrarily. Assume that $\boldsymbol{x}^{*}\in\mathcal{X}$ is
an optimal solution to $\textsc{Distr}~{}\mathcal{P}$. Then

$\min\left\\{\boldsymbol{b}^{T}\boldsymbol{x}^{*},{\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{*}]+\frac{1}{l}N\epsilon\right\\}\geq\min\left\\{\boldsymbol{b}^{T}\boldsymbol{x}^{\prime},{\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{\prime}]+\frac{1}{l}N\epsilon\right\\}$

and, according to Proposition 4, $\boldsymbol{x}^{\prime}$ is also optimal to
$\textsc{Distr}~{}\mathcal{P}$. The algorithm for computing
$\boldsymbol{x}^{\prime}$ can be faster than solving the MIP formulation
proposed in [23].

###  4.3 A general convex support set $\Xi$ and
$q\in\overline{\mathbb{R}}_{\geq 1}$

In this section, we will propose some methods of solving
$\textsc{Distr}~{}\mathcal{P}$ for any bounded, closed, and convex support
$\Xi$ and $q\in\overline{\mathbb{R}}_{\geq 1}$. To simplify the presentation,
we will also assume that $\alpha=\frac{l}{N}$ for $l\in[N]$. Let us first
rewrite (5) as follows:

$\begin{array}[]{llll}\min&z\\\ &{\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]\leq
z,&\forall\mathbb{P}^{N}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})\\\
&\boldsymbol{x}\in\mathcal{X}.\end{array}$ (18)

######  Proposition 5.

If $\alpha=\frac{l}{N}$ for $l\in[N]$, then for each
$\mathbb{P}^{N}=(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})$

${\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]=\max_{\overset{A\subseteq\\{1,\dots,N\\}}{|A|=l}}\frac{1}{l}\left(\sum_{i\in
A}\boldsymbol{\xi}_{i}^{T}\right)\boldsymbol{x}$

###### Proof.

This is a direct consequence of Proposition 1. If $\alpha=\frac{l}{N}$ for
some $l\in[N]$, then the Conditional Value at Risk is the average of the $l$
largest costs of $\boldsymbol{x}$ under
$\mathbb{P}^{N}=(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})$. ∎

Using Proposition 5, we can represent (18) as

$\begin{array}[]{llll}\min&z\\\ &\displaystyle\frac{1}{l}\left(\sum_{i\in
A}\boldsymbol{\xi}_{i}^{T}\right)\boldsymbol{x}\leq
z,&\forall(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N}),\forall
A\subseteq\\{1,\dots,n\\},|A|=l,\\\ &\boldsymbol{x}\in\mathcal{X}.\end{array}$
(19)

Let us define the uncertainty set

$\mathcal{U}=\left\\{\frac{1}{l}\sum_{i\in
A}\boldsymbol{\xi}_{i}:(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N}),A\subseteq\\{1,\dots,N\\},|A|=l\right\\}.$

We can then represent (19) more briefly as follows:

$\begin{array}[]{llll}\min&z\\\
&\displaystyle\boldsymbol{\zeta}^{T}\boldsymbol{x}\leq
z,&\forall\boldsymbol{\zeta}\in\mathcal{U},\\\
&\boldsymbol{x}\in\mathcal{X}.\end{array}$ (20)

Problem (20) can be solved by using a standard row generation algorithm shown
in Figure 2. For any finite subset $\mathcal{U}^{\prime}\subseteq\mathcal{U}$
(20) is a mixed integer program. By solving it, we get a solution
$\boldsymbol{x}^{*}\in\mathcal{X}$ with a lower bound $z^{*}_{LB}$ on the
optimal objective value $z^{*}$ of (20). We then compute a worst probability
distribution
$\mathbb{P}^{N}=(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$
for $\boldsymbol{x}^{*}$. Evaluating ${\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{*}]$
gives us an upper bound $z^{*}_{UB}$ on the optimal objective value of (20).
The cut for $\boldsymbol{x}^{*}$ can be generated by identifying the subset of
$l$ worst realizations for $\boldsymbol{x}^{*}$ in $\mathbb{P}^{N}$. Namely,
$\boldsymbol{\zeta}=\frac{1}{l}\sum_{i=1}^{l}\boldsymbol{\xi}_{\sigma(i)}$,
where
$\boldsymbol{\xi}_{\sigma(1)}^{T}\boldsymbol{x}^{*}\geq\dots\geq\boldsymbol{\xi}_{\sigma(n)}^{T}\boldsymbol{x}^{*}$,
is added to $\mathcal{U}^{\prime}$. We have to initialize the set
$\mathcal{U}^{\prime}$ to start the algorithm. In the simplest approach, we
can add one realization, say
$\boldsymbol{\zeta}=\frac{1}{l}\sum_{i=1}^{l}\hat{\boldsymbol{\xi}}_{i}$ to
$\mathcal{U}^{\prime}$.

1: Generate a nonempty subset $\mathcal{U}^{\prime}\subseteq\mathcal{U}$.

2: $z^{*}_{UB}:=+\infty$

3: repeat

4: Solve the problem (20) with $\mathcal{U}^{\prime}$ obtaining
$\boldsymbol{x}^{*}$ with $z^{*}_{LB}$

5: Compute a worst probability distribution
$\mathbb{P}^{N}=(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$
for $\boldsymbol{x}^{*}$.

6: if ${\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{*}]<z^{*}_{UB}$
then

7: $\boldsymbol{x}^{\prime}:=\boldsymbol{x}^{*}$

8: end if

9: $z^{*}_{UB}:=\min\\{z^{*}_{UB},{\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{*}]\\}$

10:
$\mathcal{U}^{\prime}:=\mathcal{U}^{\prime}\cup\\{\frac{1}{l}\sum_{i=1}^{l}\boldsymbol{\xi}_{\sigma(i)}\\}$,
where
$\boldsymbol{\xi}_{\sigma(1)}^{T}\boldsymbol{x}^{*}\geq\dots\geq\boldsymbol{\xi}_{\sigma(n)}^{T}\boldsymbol{x}^{*}$

11: until $(z^{*}_{UB}-z^{*}_{LB})/z^{*}_{LB}\leq\varepsilon$

12: return $\boldsymbol{x}^{\prime}$

Figure 2: A row generation algorithm.

Unfortunately, computing a worst probability distribution for
$\boldsymbol{x}^{*}$ in step 5 of the algorithm is not a trivial task. Using
Lemma 1, we will consider the following optimization problem:

$\max_{\mathbb{P}^{N}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}{\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}],$

where the solution $\boldsymbol{x}\in\mathcal{X}$ is fixed. If
$\alpha=\frac{l}{N}$ for some $l\in[N]$, then, according to Proposition 1,
${\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]$
is the average of the $l$ largest costs under $\mathbb{P}^{N}$. Therefore, the
problem can be expressed as follows:

$\begin{array}[]{lll}\max&\displaystyle\frac{1}{l}\sum_{i=1}^{N}y_{i}\boldsymbol{\xi}_{i}^{T}\boldsymbol{x}\\\
&\displaystyle\sum_{i=1}^{N}||\boldsymbol{\xi}_{i}-\hat{\boldsymbol{\xi}}_{i}||_{q}\leq
N\epsilon,\\\ &\displaystyle\sum_{i=1}^{N}y_{i}=l,\\\
&\boldsymbol{\xi}_{i}\in\Xi,&i\in[N],\\\
&y_{i}\in\\{0,1\\},&i\in[N].\end{array}$ (21)

The nonlinear terms $y_{i}\boldsymbol{\xi}_{i}^{T}\boldsymbol{x}$ in (21) can
be linearized using standard techniques. Problem (21) can be solved by using
some available solvers, for example, CPLEX [12], when $q=1,2,\infty$ and $\Xi$
is described by linear or second-order cone constraints. Observe that (21)
becomes a tractable convex problem when $l=N$ or $l=1$. In the former case,
the CVaR criterion is the expectation, while in the latter one, it is the
maximum cost of $\boldsymbol{x}$ under $\mathbb{P}^{N}$. In general, (21) is
tractable when $N$ is not large, which is true in many practical applications
when the available sample size is small.

####  4.3.1 Approximation algorithm

In this section, we propose a method for computing approximate solutions to
$\textsc{Distr}~{}\mathcal{P}$ with a convex, closed, and bounded support set
$\Xi$. Let $\overline{\boldsymbol{\xi}}$ maximize
$\boldsymbol{1}^{T}\boldsymbol{\xi}$ over $\boldsymbol{\xi}\in\Xi$, where
$\boldsymbol{1}=(1,1,\dots,1)^{T}$. Suppose that
$\alpha\in(\frac{l-1}{N},\frac{l}{N}]$ for some $l\in[N]$. Let $c\geq 1$ be
the smallest constant such that

$||\overline{\boldsymbol{\xi}}-\hat{\boldsymbol{\xi}}_{i}||_{q}\leq
c\frac{\epsilon N}{l},\;\;i\in[N].$ (22)

Define
$\mathbb{P}^{{}^{\prime}N}=(\boldsymbol{\xi}_{1}^{\prime},\dots,\boldsymbol{\xi}_{N}^{\prime})$,
where

$\boldsymbol{\xi}^{\prime}_{i}=\hat{\boldsymbol{\xi}}_{i}+\frac{\overline{\boldsymbol{\xi}}-\hat{\boldsymbol{\xi}}_{i}}{c},\;i\in[N].$

Since $\hat{\boldsymbol{\xi}}_{i}\in\Xi$ and
$\overline{\boldsymbol{\xi}}\in\Xi$, we get
$\boldsymbol{\xi}_{i}^{\prime}\in\Xi$. Indeed,
$\boldsymbol{\xi}_{i}^{\prime}=\frac{c-1}{c}\hat{\boldsymbol{\xi}}_{i}+\frac{1}{c}\overline{\boldsymbol{\xi}}$,
which is a convex combination of $\hat{\boldsymbol{\xi}}_{i}^{\prime}$ and
$\overline{\boldsymbol{\xi}}$ for each $c\geq 1$. Vector
$\boldsymbol{\xi}_{i}^{\prime}$ lies on the line segment joining
$\hat{\boldsymbol{\xi}}_{i}$ and $\overline{\boldsymbol{\xi}}$. The
distribution $\mathbb{P}^{{}^{\prime}N}$ can be seen as a distorted sample
$\widehat{\mathbb{P}}^{N}$ in which the realizations
$\hat{\boldsymbol{\xi}}_{i}$ are moved towards a bad realization
$\overline{\boldsymbol{\xi}}$. Let
$\boldsymbol{\zeta}=(\zeta_{1},\dots,\zeta_{n})\in\mathbb{R}^{n}_{+}$, where
$\zeta_{i}$ maximizes the component $\xi_{i}$ over $\boldsymbol{\xi}\in\Xi$.
An example is shown in Figure 3.

Figure 3: A sample support set $\Xi\subseteq\mathbb{R}^{2}$, distribution
$\mathbb{P}^{{}^{\prime}N}=(\boldsymbol{\xi}_{1}^{\prime},\boldsymbol{\xi}_{2}^{\prime},\boldsymbol{\xi}_{3}^{\prime})$,
$\overline{\boldsymbol{\zeta}}$.

######  Theorem 4.

If $\boldsymbol{x}^{\prime}\in\mathcal{X}$ minimizes ${\rm
CVaR}^{\alpha}_{\mathbb{P}^{\prime}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]$
and $\boldsymbol{\zeta}^{T}\boldsymbol{x}^{\prime}\leq
b\cdot\overline{\boldsymbol{\xi}}^{T}\boldsymbol{x}^{\prime}$ for some
constant $b\geq 1$. Then $\boldsymbol{x}^{\prime}$ is a $(b\cdot
c)$-approximate solution to $\textsc{Distr}~{}\mathcal{P}$.

###### Proof.

Let $\boldsymbol{x}^{*}$ be an optimal solution to
$\textsc{Distr}~{}\mathcal{P}$ with a worst probability distribution
$\mathbb{P}^{*N}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$. We will
show that

${\rm
CVaR}^{\alpha}_{\mathbb{P}^{*N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{*}]\geq{\rm
CVaR}^{\alpha}_{\mathbb{P}^{{}^{\prime}N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{*}]\geq{\rm
CVaR}^{\alpha}_{\mathbb{P}^{{}^{\prime}N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{\prime}].$
(23)

The second inequality in (23) follows directly from the assumption of the
theorem. It remains to show the first one. Let us represent
$\mathbb{P}^{{}^{\prime}N}$ as follows

$\mathbb{P}^{{}^{\prime}N}=(\hat{\boldsymbol{\xi}}_{1}+\boldsymbol{\Delta}^{\prime}_{1},\dots,\hat{\boldsymbol{\xi}}_{N}+\boldsymbol{\Delta}^{\prime}_{N}),$

where $\boldsymbol{\Delta}^{\prime}_{i}\in\mathbb{R}^{n}$ for $i\in[N]$. Using
Proposition 1, we get

${\rm
CVaR}^{\alpha}_{\mathbb{P}^{{}^{\prime}N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{*}]=\sum_{i=1}^{l}w_{i}(\hat{\boldsymbol{\xi}}_{\sigma(i)}+\boldsymbol{\Delta}^{\prime}_{\sigma(i)})^{T}\boldsymbol{x}^{*},$

where
$(\hat{\boldsymbol{\xi}}_{\sigma(1)}+\boldsymbol{\Delta}^{\prime}_{\sigma(1)})^{T}\boldsymbol{x}^{*}\geq\dots\geq(\hat{\boldsymbol{\xi}}_{\sigma(l)}+\boldsymbol{\Delta}^{\prime}_{\sigma(l)})^{T}\boldsymbol{x}^{*}\geq\dots\geq(\hat{\boldsymbol{\xi}}_{\sigma(N)}+\boldsymbol{\Delta}^{\prime}_{\sigma(N)})^{T}\boldsymbol{x}^{*}$
and $\sigma$ is permutation of $[N]$. Let us construct a probability
distribution $\mathbb{P}^{{}^{\prime\prime}N}$ in which
$\boldsymbol{\xi}^{{}^{\prime\prime}}_{i}=\hat{\boldsymbol{\xi}}_{i}+\boldsymbol{\Delta}^{\prime}_{i}=\hat{\boldsymbol{\xi}}_{i}+\frac{1}{c}(\overline{\boldsymbol{\xi}}-\hat{\boldsymbol{\xi}}_{i})$
if $i\in\\{\sigma(1),\dots,\sigma(l)\\}$ and
$\boldsymbol{\xi}^{{}^{\prime\prime}}_{i}=\hat{\boldsymbol{\xi}}_{i}$,
otherwise. Obviously

${\rm
CVaR}^{\alpha}_{\mathbb{P}^{{}^{\prime}N}}[\boldsymbol{\xi}^{T}\boldsymbol{x}^{*}]={\rm
CVaR}^{\alpha}_{\mathbb{P}^{{}^{\prime\prime}N}}[\boldsymbol{\xi}^{T}\boldsymbol{x}^{*}].$
(24)

and

$\frac{1}{N}\sum_{i=1}^{N}||\boldsymbol{\xi}^{\prime\prime}_{i}-\hat{\boldsymbol{\xi}}_{i}||_{q}=\frac{1}{N}\sum_{i=1}^{l}\left\lVert\frac{\overline{\boldsymbol{\xi}}-\hat{\boldsymbol{\xi}}_{\sigma(i)}}{c}\right\rVert_{q}=\frac{1}{N}\sum_{i=1}^{l}\frac{1}{c}||\overline{\boldsymbol{\xi}}-\hat{\boldsymbol{\xi}}_{\sigma(i)}||_{q}\leq\frac{1}{N}\sum_{i=1}^{l}\frac{\epsilon
N}{l}=\epsilon,$

where the last inequality follows from (22). Hence, we conclude that
$\mathbb{P}^{{}^{\prime\prime}N}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$.
Consequently, ${\rm
CVaR}^{\alpha}_{\mathbb{P}^{{}^{\prime\prime}N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{*}]\leq{\rm
CVaR}^{\alpha}_{\mathbb{P}^{*N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{*}]$,
which together with (24) imply (23). Let

$\mathbb{P}_{u}^{N}=\left(\frac{\overline{\boldsymbol{\xi}}}{c},\dots,\frac{\overline{\boldsymbol{\xi}}}{c}\right).$

Because $\hat{\boldsymbol{\xi}}_{i}\in\mathbb{R}^{n}_{+}$, $c\geq 1$, and thus
$(\hat{\boldsymbol{\xi}}_{i}+\frac{\overline{\boldsymbol{\xi}}-\hat{\boldsymbol{\xi}}_{i}}{c})^{T}\boldsymbol{x}^{\prime}=((1-\frac{1}{c})\hat{\boldsymbol{\xi}}_{i}+\frac{1}{c}\overline{\boldsymbol{\xi}})^{T}\boldsymbol{x}^{\prime}\geq\frac{1}{c}\overline{\boldsymbol{\xi}}^{T}\boldsymbol{x}^{\prime}$
for each $i\in[N]$, we obtain

${\rm
CVaR}^{\alpha}_{\mathbb{P}^{{}^{\prime}N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{\prime}]\geq{\rm
CVaR}^{\alpha}_{\mathbb{P}_{u}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{\prime}]=\frac{1}{c}\overline{\boldsymbol{\xi}}^{T}\boldsymbol{x}^{\prime}\geq\frac{1}{cb}\boldsymbol{\zeta}^{T}\boldsymbol{x}^{\prime}\geq\frac{1}{bc}{\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}^{\prime}]$
(25)

for each $\mathbb{P}^{N}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$.
Inequalities (25) and (23) imply the theorem. ∎

For the support set $\Xi_{\boldsymbol{a},\boldsymbol{b}}$, we get
$\boldsymbol{\zeta}=\overline{\boldsymbol{\xi}}$, which leads to the following
result.

######  Theorem 5.

If the support set is $\boldsymbol{\Xi}_{\boldsymbol{a},\boldsymbol{b}}$ and
$\boldsymbol{x}^{\prime}$ minimizes ${\rm
CVaR}^{\alpha}_{\mathbb{P}^{\prime}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]$,
then $\boldsymbol{x}^{\prime}$ is a $c$-approximate solution to
$\textsc{Distr}~{}\mathcal{P}$.

The algorithm described in this section can be seen as another method of
dealing with the sample $\widehat{\mathbb{P}}^{N}$. If $N$ is small, it may be
advantageous to distort this sample towards some bad realization
$\overline{\boldsymbol{\xi}}$ to obtain more robust solutions. Observe that we
do not need to know the whole shape of the support set $\Xi$. It is only
enough to assume that $\Xi$ is convex and $\overline{\boldsymbol{\xi}}\in\Xi$.
One can also try other methods of choosing $\overline{\boldsymbol{\xi}}$. For
example $\overline{\boldsymbol{\xi}}$ can minimize a distance to
$\boldsymbol{\zeta}$ over all $\boldsymbol{\xi}\in\Xi$. We can also choose an
arbitrary value of $c\geq 1$. We then get a heuristic solution whose
performance can be compared to other approaches.

##  5 Computational tests

In this section, we will show the results of some computational tests. We will
investigate the performance of the Wasserstein robust approach for the minimum
0-1 Knapsack problem, which is a fundamental combinatorial optimization
problem often used to test the proposed concepts (see, e.g. [3]). Recall that
the deterministic  0-1 Knapsack is already NP-hard.

We are given a set of items $[n]$. For each item $i\in[n]$ a nonnegative
weight $w_{i}$ is specified and the set of feasible solution is
$\mathcal{X}=\\{\boldsymbol{x}\in\\{0,1\\}^{n}:\sum_{i\in[n]}w_{i}x_{i}\geq
W\\}$, where $W\geq 0$ is a given capacity. In our experiments, each $w_{i}$
was a random number drawn from the uniform probability distribution in the
interval $[0,1]$ (i.e. $w_{i}\sim\mathcal{U}([0,1])$). The value of $W$ was
then set to $0.4\sum_{i\in[n]}w_{i}$. The random cost vector
$\tilde{\boldsymbol{\xi}}=(\tilde{\xi}_{1},\dots,\tilde{\xi}_{n})$ of the
items was defined as follows. For each component $\tilde{\xi}_{i}$ of
$\tilde{\boldsymbol{\xi}}$ an interval
$[\underline{\xi}_{i},\overline{\xi}_{i}]$ was determined, where
$\underline{\xi}_{i}=\max\\{0,w_{i}-\alpha_{i}\\}$,
$\alpha_{i}\sim\mathcal{U}([0,1])$ and
$\overline{\xi}_{i}=\underline{\xi}_{i}+2\beta_{i}$,
$\beta_{i}\sim\mathcal{U}([0,1])$. Then the component $\tilde{\xi}_{i}$ has a
truncated normal distribution in the interval
$[\underline{\xi}_{i},\overline{\xi}_{i}]$ with the expected value $w_{i}$ and
the standard deviation $0.7w_{i}$. All the random variables
$\alpha_{i},\beta_{i}$, $i\in[n]$, were mutually independent. The method of
creating the instance can be justified by the fact that in practical
applications, the items having larger weights also have larger costs. Observe
that the support set $\Xi$ is the Cartesian product of
$[\underline{\xi}_{i},\overline{\xi}_{i}]$ for $i\in[n]$.

Figure 4: The $0.9$-quantiles of $\boldsymbol{x}_{i}$ (horizontal line),
$\boldsymbol{y}_{i}^{\epsilon}$ (dotted line) and
$\boldsymbol{z}_{i}^{\epsilon}$ (grey line) for four empirical distributions
$\widehat{\mathbb{P}}^{N}_{1},\dots,\widehat{\mathbb{P}}^{N}_{4}$ of size 30.
Figure 5: The average $0.9$-quantiles of $\boldsymbol{x}_{i}$ (horizontal
line), $\boldsymbol{y}_{i}^{\epsilon}$ (dotted line) and
$\boldsymbol{z}_{i}^{\epsilon}$ (grey line) for ten empirical distributions
$\widehat{\mathbb{P}}^{N}_{1},\dots,\widehat{\mathbb{P}}^{N}_{10}$ of size 30.

The first experiment was carried out as follows. We fixed $n=100$ and
generated an instance $(\boldsymbol{w},W,\tilde{\boldsymbol{\xi}})$ of the
problem. We then generated 10 random samples of size $N=30$ of
$\boldsymbol{\tilde{\xi}}$ obtaining ten empirical distributions
$\widehat{\mathbb{P}}^{N}_{1},\dots,\widehat{\mathbb{P}}^{N}_{10}$. For each
empirical distribution $\widehat{\mathbb{P}}^{N}_{i}$, $i=1,\dots,10$, we
computed an optimal solution $\boldsymbol{x}_{i}$ to
$\textsc{CVaR}~{}\mathcal{P}$ with $\alpha=0.1$. We have thus applied the
traditional approach based on the sample average approximation. Then for each
$\epsilon=0.0025,0.005,0.00525,\dots,0.1$ and $i=1,\dots,10$, we computed an
optimal solution $\boldsymbol{y}_{i}^{\epsilon}$ to
$\text{Distr}~{}\mathcal{P}$ with
$\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}_{i}^{N}))$ using the row
generation algorithm and a solution $\boldsymbol{z}_{i}^{\epsilon}$ using the
approximation algorithm proposed in Section 4.3.1. We also chose $\alpha=0.1$
and $p=\infty$ in the definition of the Wasserstein ball. We now face the
problem of comparing the solutions $\boldsymbol{x}_{i}$ to
$\boldsymbol{y}_{i}^{\epsilon}$ and $\boldsymbol{z}_{i}^{\epsilon}$. The cost
$\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}$ of a given solution
$\boldsymbol{x}$ is a random variable. The robustness of $\boldsymbol{x}$ can
be measured by computing the $0.9$-quantile $q_{0.9}$ of
$\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}$ \- with probability $0.9$, the
largest cost of $\boldsymbol{x}$ will not exceed $q_{0.9}$. The solutions with
smaller values of $q_{0.9}$ will be regarded as more robust. For a given
solution, the quantile $q_{0.9}$ can be approximated by generating a very
large sample of $\tilde{\boldsymbol{\xi}}$. In our experiments, we chose a
sample size of $100~{}000$ for this purpose.

Figure 4 shows four representative examples among the ten generated. The
horizontal line represents the $q_{0.9}$ quantile of $\boldsymbol{x}_{i}$. The
dotted line is the $q_{0.9}$ quantile of $\boldsymbol{y}_{i}^{\epsilon}$ and
the grey line is is the $q_{0.9}$ quantile of $\boldsymbol{z}_{i}^{\epsilon}$
for each tested $\epsilon$. The performance of the solutions depends on the
sample. In almost all cases, the performance of
$\boldsymbol{z}_{i}^{\epsilon}$, computed by the approximation algorithm, was
better than $\boldsymbol{x}_{i}$. For the solution
$\boldsymbol{y}_{i}^{\epsilon}$, the conclusion is not so decisive. In most
cases, we also get better solutions, but sometimes the performance of
$\boldsymbol{z}_{i}^{\epsilon}$ was worse than $\boldsymbol{x}_{i}$,
especially when the solution $\boldsymbol{x}_{i}$ has a smaller value of
$q_{0.9}$. Figure 4 shows the average performance (average values of $q_{0.9}$
of solutions) over all 10 samples.

In the second experiment, we focused on the approximation algorithm
constructed in Section 4.3.1. We again fixed $n=100$ and generated an instance
$(\boldsymbol{w},W,\tilde{\boldsymbol{\xi}})$ of the problem. We then
generated 10 random samples of size $N=30$ of $\boldsymbol{\tilde{\xi}}$
obtaining the empirical distributions
$\widehat{\mathbb{P}}^{N}_{1},\dots,\widehat{\mathbb{P}}^{N}_{10}$. We fixed
$\alpha=0.5$. For this choice of $\alpha$, the value of $l$ in the model (21)
is equal to 15, and the model turned out to be hard to solve. Therefore, we
only applied the approximation algorithm for the tested instances. For each
empirical distribution $\widehat{\mathbb{P}}^{N}_{i}$, $i=1,\dots,10$, we
computed an optimal solution $\boldsymbol{x}_{i}$ to
$\textsc{CVaR}~{}\mathcal{P}$. Then for each
$\epsilon=0.0025,0.005,0.00525,\dots,1$ and $i=1,\dots,10$, we computed a
solution $\boldsymbol{z}_{i}^{\epsilon}$ using the approximation algorithm
proposed in Section 4.3.1. We choose $p=\infty$ in the definition of the
Wasserstein ball. As in the previous experiment, the robustness of
$\boldsymbol{x}_{i}$ and $\boldsymbol{z}_{i}^{\epsilon}$ were evaluated by
computing the $q_{0.9}$ quantiles for each solution, using a simulation on a
very large sample. The results for four representative cases are shown in
Figure 6. In the majority of cases, the performance of
$\boldsymbol{z}_{i}^{\epsilon}$ was better than $\boldsymbol{x}_{i}$, except
for the one case when the performance of $\boldsymbol{x}_{i}$ itself was good
and the performance of $\boldsymbol{z}_{i}^{\epsilon}$ was similar.
Interestingly, in all the cases, the value of $\epsilon$ should not be too
small and too large. For $\epsilon\geq 0.9$ a large deterioration in the
performance of $\boldsymbol{z}_{i}^{\epsilon}$ was observed. The average
performance of the approximation algorithm over ten random samples is shown in
Figure 7. On average, the best choice of $\epsilon$ for the tested instances
was between $0.1$ and $0.7$.

Figure 6: The $0.9$-quantiles of $\boldsymbol{x}_{i}$ (horizontal line) and
$\boldsymbol{z}_{i}^{\epsilon}$ (grey line) for four empirical distributions
$\widehat{\mathbb{P}}^{N}_{1},\dots,\widehat{\mathbb{P}}^{N}_{4}$ of size 30.
Figure 7: The average $0.9$-quantiles of $\boldsymbol{x}_{i}$ (horizontal
line) and $\boldsymbol{z}_{i}^{\epsilon}$ (grey line) for ten empirical
distributions
$\widehat{\mathbb{P}}^{N}_{1},\dots,\widehat{\mathbb{P}}^{N}_{10}$ of size 30.

##  6 Conclusions

In this paper, we discussed the class of combinatorial optimization problems
with uncertain costs in the objective function. Assuming that a sample of cost
realizations is available, we used the Wasserstein distance to define a set of
admissible probability distributions for the random costs vector. We then seek
a solution minimizing the CVaR risk measure for the worst probability
distribution. We showed that the problem is strongly NP-hard for basic
combinatorial optimization problems (in particular for the shortest path
problem), except for the case when CVaR becomes the expectation. We showed
some exact and approximation methods of solving the problem. In particular, we
proposed a row generation algorithm which can be applied to arbitrary convex
support sets. We also constructed an approximation algorithm whose idea is to
minimize CVaR for an appropriately distorted sample. Some computational tests
indicated that the distributionally robust approach, based on the Wasserstein
distance, may give better results than the sample average approximation.

An interesting open problem is the complexity of computing a worst probability
distribution for a given solution. In this paper, we used a mixed integer
programming formulation for this purpose, which, however, can be complex to
solve for larger instances. More efficient algorithms for particular support
sets (for example, ellipsoidal ones) should be constructed. Also, the proposed
algorithms should be tested on other combinatorial problems, possibly
considering real data.

#### Acknowledgements

The authors were supported by the National Science Centre, Poland, grant
2022/45/B/HS4/00355.

## References

  * [1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin.  Network Flows: theory, algorithms, and applications.  Prentice Hall, Englewood Cliffs, New Jersey, 1993.
  * [2] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski.  Robust optimization.  Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, 2009.
  * [3] D. Bertsimas and M. Sim.  The price of robustness.  Operations research, 52:35–53, 2004.
  * [4] S. P. Boyd and L. Vandenberghe.  Convex optimization.  Cambridge university press, 2004.
  * [5] V. G. Deineko and G. J. Woeginger.  Complexity and in-approximability of a selection problem in robust optimization.  4OR - A Quarterly Journal of Operations Research, 11:249–252, 2013\.
  * [6] E. Delage and Y. Ye.  Distributionally robust optimization under moment uncertainty with application to data-deriven problems.  Operations Research, 58:595–612, 2010.
  * [7] A. Dolgui and S. Kovalev.  Min-max and min-max (relative) regret approaches to representatives selection problem.  4OR - A Quarterly Journal of Operations Research, 10:181–192, 2012\.
  * [8] P. M. Esfahani and D. Kuhn.  Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations.  Mathematical Programming, Ser. A, 171:115–166, 2018.
  * [9] N. Fournier and A. Guillin.  On the rate of convergence in Wasserstein distance of the empirical measure.  Probability Theory and Related Fields, 162:1–32, 2014.
  * [10] R. Gao and A. J. Kleywegt.  Distributionally robust stochastic optimization with Wasserstein distance.  Mathematics of Operations Research, 48:603–1211, 2023.
  * [11] R. Hassin.  Approximation Schemes for the Restricted Shortest Path Problem.  Mathematics of Operations Research, 17:36–42, 1992.
  * [12] IBM ILOG CPLEX Optimization Studio.  CPLEX User’s manual.  https://www.ibm.com.
  * [13] M. Jackiewicz, A. Kasperski, and P. Zieliński.  Solving Wasserstein distributionally robust combinatorial optimization problems.  In Proceedings of OR 2023, to appear, 2023.
  * [14] P. Kall and S. W. Wallace.  Stochastic Programming.  John Wiley and Sons, 1994.
  * [15] L. V. Kantorovich and G. S. Rubinshtein.  On a space of totally additive functions.  Vestnik, Leningrad University, 13:52–59, 1958.
  * [16] A. Kasperski, A. Kurpisz, and P. Zieliński.  Approximability of the robust representatives selection problem.  Operations Research Letters, 43:16–19, 2015.
  * [17] A. Kasperski and P. Zieliński.  Combinatorial optimization problems with uncertain costs and the OWA criterion.  Theoretical Computer Science, 565:102–112, 2015.
  * [18] H. Kim, D. Watel, A. Faye, and C. Hervet.  On the complexity of the data-driven Wasserstein distributionally robust binary problem.  Technical report, hal-03595342, 2022.
  * [19] P. Kouvelis and G. Yu.  Robust Discrete Optimization and its Applications.  Kluwer Academic Publishers, 1997.
  * [20] C. H. Papadimitriou and K. Steiglitz.  Combinatorial optimization: algorithms and complexity.  Dover Publications Inc., 1998.
  * [21] G. C. Pflug.  Some remarks on the Value-at-Risk and the Conditional Value-at-Risk.  In S. P. Uryasev, editor, Probabilistic Constrained Optimization: Methodology and Applications, pages 272–281. Kluwer Academic Publishers, 2000.
  * [22] R. T. Rockafellar and S. P. Uryasev.  Optimization of conditional value-at-risk.  The Journal of Risk, 2:21–41, 2000.
  * [23] Z. Wang, K. You, S. Song, and Y. Zhang.  Wasserstein distributionally robust shortest path problem.  European Journal of Operational Research, 284:31–43, 2020.
  * [24] W. Wiesemann, D. Kuhn, and M. Sim.  Distributionally robust convex optimization.  Operations Research, 62:1358–1376, 2014.
  * [25] R. R. Yager.  On ordered weighted averaging aggregation operators in multi-criteria decision making.  IEEE Transactions on Systems, Man and Cybernetics, 18:183–190, 1988\.

##  Appendix A Appendix

###### Proof of Lemma 1.

The proof is similar in spirit to [23, Lemma 2]. Since the function
$t+\frac{1}{\alpha}\int_{\Xi}[\boldsymbol{\xi}^{T}\boldsymbol{x}-t]_{+}\mathbb{P}({\rm
d}\boldsymbol{\xi})$ is convex in $t$ and linear in $\mathbb{P}({\rm
d}\boldsymbol{\xi})$ we can write:

$\displaystyle\sup_{\mathbb{P}\in\mathbb{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}{\rm
CVaR}^{\alpha}_{\mathbb{P}}[\boldsymbol{\xi}^{T}\boldsymbol{x}]$
$\displaystyle=\sup_{\mathbb{P}\in\mathbb{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}\inf\left\\{t\in\mathbb{R}:t+\frac{1}{\alpha}\int_{\Xi}[\boldsymbol{\xi}^{T}\boldsymbol{x}-t]_{+}\mathbb{P}({\rm
d}\boldsymbol{\xi})\right\\}$
$\displaystyle=\inf\left\\{t\in\mathbb{R}:t+\frac{1}{\alpha}\sup_{\mathbb{P}\in\mathbb{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}\int_{\Xi}[\boldsymbol{\xi}^{T}\boldsymbol{x}-t]_{+}\mathbb{P}({\rm
d}\boldsymbol{\xi})\right\\}.$ (26)

If $\mathbb{P}\in\mathbb{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$, then
$\mathbb{P}({\rm d}\boldsymbol{\xi})=\sum_{i=1}^{N}\Pi({\rm
d}\boldsymbol{\xi},\hat{\boldsymbol{\xi}}_{i})$ and we can express the inner
optimization problem in (26) as

$\begin{array}[]{lll}v^{*}=\sup&\displaystyle\int_{\Xi}\sum_{i=1}^{N}[\boldsymbol{\xi}^{T}\boldsymbol{x}-t]_{+}\Pi({\rm
d}\boldsymbol{\xi},\hat{\boldsymbol{\xi}}_{i})\\\
&\displaystyle\int_{\Xi}\Pi({\rm
d}\boldsymbol{\xi},\hat{\boldsymbol{\xi}}_{i})=\frac{1}{N},&i\in[N],\\\
&\displaystyle\int_{\Xi}\sum_{i=1}^{N}||\boldsymbol{\xi}-\hat{\boldsymbol{\xi}}_{i}||_{q}\Pi({\rm
d}\boldsymbol{\xi},\hat{\boldsymbol{\xi}}_{i})\leq\epsilon,\\\ &\Pi({\rm
d}\boldsymbol{\xi},\hat{\boldsymbol{\xi}}_{i})\geq 0,&i\in[N].\end{array}$
(27)

The dual to (27) is

$\begin{array}[]{lll}u^{*}=\inf&\displaystyle\frac{1}{N}\sum_{i=1}^{N}s_{i}+\lambda\epsilon\\\
&[\boldsymbol{\xi}^{T}\boldsymbol{x}-t]_{+}-\lambda||\boldsymbol{\xi}-\hat{\boldsymbol{\xi}}_{i}||_{q}\leq
s_{i},&\forall\boldsymbol{\xi}\in\Xi,i\in[N],\\\ &\lambda\geq 0,\end{array}$

where $\lambda\geq 0$ and $s_{1},\dots,s_{N}\in\mathbb{R}$ are Lagrangian
multipliers, which can be equivalently rewritten as follows

$u^{*}=\inf_{\lambda\geq
0}\sup_{\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N}\in\Xi}\frac{1}{N}\sum_{i=1}^{N}([\boldsymbol{\xi}_{i}^{T}\boldsymbol{x}-t]_{+}-\lambda||\boldsymbol{\xi}_{i}-\hat{\boldsymbol{\xi}}_{i}||_{q})+\lambda\epsilon=$

$\inf_{\lambda\geq
0}\sup_{\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N}\in\Xi}\frac{1}{N}\sum_{i=1}^{N}[\boldsymbol{\xi}_{i}^{T}\boldsymbol{x}-t]_{+}-\lambda\left(\frac{1}{N}\sum_{i=1}^{N}||\boldsymbol{\xi}_{i}-\hat{\boldsymbol{\xi}}_{i}||_{q}-\epsilon\right).$
(28)

Problem (28) is equivalent to

$\begin{array}[]{lll}\displaystyle
u^{*}=\sup&\displaystyle\frac{1}{N}\sum_{i=1}^{N}[\boldsymbol{\xi}_{i}^{T}\boldsymbol{x}-t]_{+}\\\
&\displaystyle\frac{1}{N}\sum_{i=1}^{N}||\boldsymbol{\xi}_{i}-\hat{\boldsymbol{\xi}}_{i}||_{q}\leq\epsilon\\\
&\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N}\in\Xi\end{array}$

The set of feasible solutions to this problem is closed and bounded, and the
objective function is continuous. Therefore, the supremum is attained.
Furthermore, the set of feasible solutions is exactly
$\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$. Hence

$u^{*}=\max_{(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}\frac{1}{N}\sum_{i=1}^{N}[\boldsymbol{\xi}_{i}^{T}\boldsymbol{x}-t]_{+}.$
(29)

By weak duality, we get $u^{*}\geq v^{*}$ and by (26) we have

$\sup_{\mathbb{P}\in\mathbb{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}{\rm
CVaR}^{\alpha}_{\mathbb{P}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]\leq\inf\left\\{t\in\mathbb{R}:t+\frac{1}{\alpha}\max_{\mathbb{P}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}\frac{1}{N}\sum_{i=1}^{N}[\boldsymbol{\xi}_{i}^{T}\boldsymbol{x}-t]_{+}\right\\}=\max_{\mathbb{P}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}{\rm
CVaR}^{\alpha}_{\mathbb{P}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}].$
(30)

It is easy to see that
$\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})\subseteq\mathbb{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$.
Indeed, for
$\mathbb{P}^{N}=(\boldsymbol{\xi}_{1},\dots,\boldsymbol{\xi}_{N})\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$,
consider the joint probability distribution
$\Pi=((\boldsymbol{\xi}_{1},\hat{\boldsymbol{\xi}}_{1}),\dots,(\boldsymbol{\xi}_{N},\hat{\boldsymbol{\xi}}_{N}))$
in $\Xi\times\Xi$. Then

$\int_{\Xi\times\Xi}||\boldsymbol{\xi}_{1}-\boldsymbol{\xi}_{2}||_{q}\Pi({\rm
d}\boldsymbol{\xi}_{1},{\rm
d}\boldsymbol{\xi}_{2})=\frac{1}{N}\sum_{i=1}^{N}||\boldsymbol{\xi}_{i}-\hat{\boldsymbol{\xi}}_{i}||_{q}\leq\epsilon$

and $d_{W}(\widehat{\mathbb{P}}^{N},\mathbb{P}^{N})\leq\epsilon$. Hence, and
by (30), we obtain

$\sup_{\mathbb{P}\in\mathbb{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}{\rm
CVaR}^{\alpha}_{\mathbb{P}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]=\max_{\mathbb{P}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}{\rm
CVaR}^{\alpha}_{\mathbb{P}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}].$

∎

###### Proof of Theorem 3.

Assume that $\alpha\in(\frac{l-1}{N},\frac{l}{N}]$ for some $l\in[N]$. For the
support set $\Xi=\mathbb{R}^{n}_{+}$ we get

$\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})=\\{(\hat{\boldsymbol{\xi}}_{1}+\boldsymbol{\Delta}_{1},\dots,\hat{\boldsymbol{\xi}}_{N}+\boldsymbol{\Delta}_{N}):\sum_{i=1}^{N}||\boldsymbol{\Delta}_{i}||_{q}\leq
N\epsilon,\;\boldsymbol{\Delta}_{i}\in\mathbb{R}^{n},i\in[N]\\}.$ (31)

Let us fix $\boldsymbol{x}\in\mathcal{X}$ and assume that

$\hat{\boldsymbol{\xi}}^{T}_{\sigma(1)}\boldsymbol{x}\geq\hat{\boldsymbol{\xi}}^{T}_{\sigma(2)}\boldsymbol{x}\geq\dots\geq\hat{\boldsymbol{\xi}}^{T}_{\sigma(N)}\boldsymbol{x}.$

Let
$\mathbb{P}^{N}=(\hat{\boldsymbol{\xi}}_{1}+\boldsymbol{\Delta}_{1},\dots,\hat{\boldsymbol{\xi}}_{N}+\boldsymbol{\Delta}_{N})\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$
be a worst probability distribution for $\boldsymbol{x}$ such that
$(\hat{\boldsymbol{\xi}}_{\sigma^{\prime}(1)}+\boldsymbol{\Delta}_{\sigma^{\prime}(1)})^{T}\boldsymbol{x}\geq\dots\geq(\hat{\boldsymbol{\xi}}_{\sigma^{\prime}(N)}+\boldsymbol{\Delta}_{\sigma^{\prime}(N)})^{T}\boldsymbol{x}$.
Then, using Proposition 1

${\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]=\sum_{i=1}^{N}w_{i}(\hat{\boldsymbol{\xi}}_{\sigma^{\prime}(i)}+\boldsymbol{\Delta}_{\sigma^{\prime}(i)})^{T}\boldsymbol{x}\leq\sum_{i=1}^{N}w_{i}(\hat{\boldsymbol{\xi}}_{\sigma(i)}+\boldsymbol{\Delta}_{\sigma^{\prime}(i)})^{T}\boldsymbol{x}\leq{\rm
CVaR}^{\alpha}_{\mathbb{P}^{*N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}],$
(32)

where $\mathbb{P}^{*N}$ is the probability distribution, in which
$\boldsymbol{\xi}^{*}_{\sigma(i)}=\hat{\boldsymbol{\xi}}_{\sigma(i)}+\boldsymbol{\Delta}_{\sigma^{\prime}(i)}$,
$i\in[N]$. The last inequality in (32) follows from the fact that $w_{1}\geq
w_{2}\geq\dots\geq w_{N}$. It is easy to see that
$\mathbb{P}^{*N}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})$ and,
according to (32), $\mathbb{P}^{*N}$ is also a worst probability distribution
for $\boldsymbol{x}$. Therefore, we get

$\max_{\mathbb{P}^{N}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}{\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]=\left\\{\begin{array}[]{llll}\max&\displaystyle\sum_{i=1}^{N}w_{i}(\hat{\boldsymbol{\xi}}_{\sigma(i)}+\boldsymbol{\Delta}_{i})^{T}\boldsymbol{x}\\\
&\displaystyle\sum_{i=1}^{N}||\boldsymbol{\Delta}_{i}||_{q}\leq\epsilon N,\\\
&\boldsymbol{\Delta}_{i}\in\mathbb{R}^{n},&i\in[N].\end{array}\right.$ (33)

Since, by Proposition 1,
$\sum_{i=1}^{N}w_{i}\hat{\boldsymbol{\xi}}_{\sigma(i)}^{T}\boldsymbol{x}={\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]$,

$\max_{\mathbb{P}^{N}\in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}^{N})}{\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]={\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]+\left\\{\begin{array}[]{llll}\max&\displaystyle\sum_{i=1}^{N}w_{i}\boldsymbol{\Delta}_{i}^{T}\boldsymbol{x}\\\
&\displaystyle\frac{1}{N}\sum_{i=1}^{N}||\boldsymbol{\Delta}_{i}||_{q}\leq\epsilon,\\\
&\boldsymbol{\Delta}_{i}\in\mathbb{R}^{n},&i\in[N].\end{array}\right.$ (34)

Let us focus on the inner maximization problem in (34). The Lagrangian
function with Lagrangian multiplier $v\geq 0$ for this problem takes the
following form:

$L(\boldsymbol{\Delta}_{1},\dots,\boldsymbol{\Delta}_{N},v)=\sum_{i=1}^{N}w_{i}\boldsymbol{\Delta}_{i}^{T}\boldsymbol{x}-v(\frac{1}{N}\sum_{i=1}^{N}||\boldsymbol{\Delta}_{i}||_{q}-\epsilon)=$

$\sum_{i=1}^{l}(w_{i}\boldsymbol{\Delta}_{i}^{T}\boldsymbol{x}-v\frac{1}{N}||\boldsymbol{\Delta}_{i}||_{q})-v\frac{1}{N}\sum_{i=l+1}^{N}||\boldsymbol{\Delta}_{i}||_{q}+v\epsilon,$

which follows from the fact that $w_{l+1}=\dots=w_{N}=0$. We now show that

$\sup_{\boldsymbol{\Delta}_{i}}(w_{i}\boldsymbol{\Delta}_{i}^{T}\boldsymbol{x}-v\frac{1}{N}||\boldsymbol{\Delta}_{i}||_{q})=\left\\{\begin{array}[]{lll}0&\text{if}&Nw_{i}||\boldsymbol{x}||_{q^{\prime}}\leq
v,\\\
\infty&\text{if}&Nw_{i}||\boldsymbol{x}||_{q^{\prime}}>v.\end{array}\right.$
(35)

Indeed, from the definition of the dual norm (see, e.g., [4]), we get for each
$t\geq 0$

$t||\boldsymbol{x}||_{q^{\prime}}=\sup\\{\boldsymbol{\Delta}^{T}_{i}\boldsymbol{x}:||\boldsymbol{\Delta}_{i}||_{q}\leq
t\\}$

and, because $v\geq 0$

$\sup_{\boldsymbol{\Delta}_{i}}(w_{i}\boldsymbol{\Delta}_{i}^{T}\boldsymbol{x}-v\frac{1}{N}||\boldsymbol{\Delta}_{i}||_{q})=\sup_{t\geq
0}\sup_{||\boldsymbol{\Delta}_{i}||_{q}\leq
t}(w_{i}\boldsymbol{\Delta}_{i}^{T}\boldsymbol{x}-v\frac{1}{N}t)=$
$\sup_{t\geq
0}(w_{i}t||\boldsymbol{x}||_{q^{\prime}}-v\frac{1}{N}t)=\sup_{t\geq
0}t(w_{i}||\boldsymbol{x}||_{q^{\prime}}-v\frac{1}{N}),$

which implies (35). Hence

$\inf_{v}\sup_{\boldsymbol{\Delta}_{1},\dots,\boldsymbol{\Delta}_{N}}L(\boldsymbol{\Delta}_{1},\dots,\boldsymbol{\Delta}_{N},v)=\left\\{\begin{array}[]{lll}v\epsilon&\text{if}&Nw_{i}||\boldsymbol{x}||_{q^{\prime}}\leq
v,\;i\in[l],\\\ \infty&\text{otherwise}.\end{array}\right.$

The optimization problem in (34) is a convex one that satisfies the Slater
condition for each $\epsilon>0$. Thus, by strong duality

${\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]={\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]+\max_{i\in[l]}Nw_{i}\epsilon||\boldsymbol{x}||_{q^{\prime}}.$

Finally, using the definition of the weights in Proposition 1, we obtain ${\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\boldsymbol{\xi}^{T}\boldsymbol{x}]={\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\boldsymbol{\xi}^{T}\boldsymbol{x}]+N\epsilon||\boldsymbol{x}||_{q^{\prime}}$
if $\alpha\leq\frac{1}{N}$ and ${\rm
CVaR}^{\alpha}_{\mathbb{P}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]={\rm
CVaR}^{\alpha}_{\widehat{\mathbb{P}}^{N}}[\tilde{\boldsymbol{\xi}}{}^{T}\boldsymbol{x}]+\frac{1}{\alpha}\epsilon||\boldsymbol{x}||_{q^{\prime}}$,
otherwise. This yields (11).

∎