ngerman-x-latestngermanngerman-x-latest german-x-latestgermangerman-x-latest

# Approaches for Biobjective Integer Linear Robust Optimization

Fabian Chlumsky-Harttmann111supported by DFG under grant SCHO 1140/11-1
Faculty of Mathematics, University of Kaiserslautern-Landau  Marie Schmidt
Faculty of Mathematics and Computer Science, University of Würzburg  Anita
Schöbel  Faculty of Mathematics, University of Kaiserslautern-Landau
Fraunhofer Institute for Industrial Mathematics ITWM

#### Abstract

Real-world optimization problems often do not just involve multiple objectives
but also uncertain parameters. In this case, the goal is to find Pareto-
optimal solutions that are robust, i.e., reasonably good under all possible
realizations of the uncertain data. Such solutions have been studied in many
papers within the last ten years and are called _robust efficient_. However,
solution methods for finding robust efficient solutions are scarce. In this
paper, we develop three algorithms for determining robust efficient solutions
to biobjective mixed-integer linear robust optimization problems.

To this end, we draw from methods for both multiobjective optimization and
robust optimization: dichotomic search for biobjective mixed-integer
optimization problems and an optimization-pessimization approach from (single-
objective) robust optimization, which iteratively adds scenarios and thereby
increases the uncertainty set. We propose two algorithms that combine
dichotomic search with the optimization-pessimization method as well as a
dichotomic search method for biobjective linear robust optimization that
exploits duality. On the way we derive some other results: We extend
dichotomic search from biobjective linear problems to biobjective linear
minmax problems and generalize the optimization-pessimization method from
single-objective to multi-objective robust optimization problems.

We implemented and tested the three algorithms on linear and integer linear
instances and discuss their respective strengths and weaknesses.

##  1 Introduction

Real-world optimization problems are often complicated by two issues: First,
in many cases decision makers have not only one but multiple objectives.
Second, the optimization problems may involve uncertainty – be it through
prediction errors about parameters like demand, that will only be known in the
future, or measurement errors. These two issues are treated in the fields of
multiobjective optimization and robust optimization.

In order to do deal with problems that are both uncertain and multiobjective,
multiobjective robust optimization has been studied for more than ten years
leading to various models and theoretical results. However, research into
methods of actually solving such problems is still in its initial stages. In
this paper we propose three algorithms for computing robust efficient
solutions for uncertain biobjective mixed-integer linear optimization
problems.

In order to find a good solution for an uncertain multiobjective problem, a
notion of what constitutes a _robust efficient_ solution has to be formulated
first. This is not trivial since there is no straightforward way to generalize
the concept of Pareto optimality used in multiobjective optimization to
uncertain multiobjective problems or to generalize the notion of robustness to
multiobjective problems. Over the years, several concepts for robust
multiobjective efficiency have been proposed, (see [IS16, WD16] for surveys).
The oldest among them is the notion of _flimsily efficient_ (sometimes:
_possibly efficient_) and _highly efficient_ (sometimes: _necessarily
efficient_) solutions (see, e.g., [Bit80, IS96, Kuh+16, ES20]) describing
solutions that are efficient for at least one or for all considered scenarios,
respectively. Other notable concepts include _regret-robust efficiency_ (see
[RY13, Xid+17, GW22]), _multi-scenario efficiency_ (see [BS19]), _lightly
robust efficiency_ (see [Kuh+16, IS16]), _local efficiency w.r.t. the robust
counterpart_ (see [Chu20]), and three different generalizations of minmax
robustness to multiobjective problems called _set-based_ (see [EIS14]), _hull-
based_ (see [BF17]) and _point-based minmax efficiency_. The latter concept
has been introduced by Kuroiwa and Lee (see [KL12]) and is used in this paper.

For point-based minmax robust efficiency, many theoretical results exist:
Goberna, Jeyakumar, Li and Vicente-Pérez consider specific forms of data
uncertainty (box data uncertainty, norm data uncertainty, ellipsoidal
uncertainty) and provide deterministic reformulations (see [Gob+15]). Box
uncertainty with a limited sum of deviations has been considered in [HNS13].
In [Ant+20] necessary and sufficient conditions for robust
$\varepsilon$-efficient solutions for uncertain nonsmooth multiobjective
optimization problems are established, but no algorithmic method is provided.
In [WCL20a, WCL20] separation results and some characterizations of optimality
are developed, and the robustness gap for point-based minmax robust efficiency
has been introduced in [Krü+23]. The _price of robustness_ has been defined in
[SZK21]. Point-based minmax robust efficiency has been generalized to
_efficiency w.r.t. to a general cone_ (see [WLC15, Ide+14]) and it has been
applied to decision robustness in [EKS17].

As general algorithmic idea, many authors suggest scalarization approaches
transferring a robust multiobjective problem to a single-objective robust
problem, e.g, [EIS14, Ide+14, Gob+15], but the approaches proposed in those
papers are still on an abstract level and only capable of finding some robust
efficient solutions while in this paper we give concrete algorithms for
determining a representative set of all supported robust efficient solutions.
Other algorithmic approaches consider special cases, e.g., cardinality-
constrained uncertainty for combinatorial problems (see [Rai+18a]), uncertain
multiobjective shortest-path problems [Rai+18] or cardinality-constrained box
uncertainty in the context of portfolio selection problems [HNS14].

The remainder of the paper is organized as follows. In Section 2 we derive a
biobjective integer linear minmax optimization problem as robust counterpart
and collect other necessary preliminaries. Section 3.1 considers the problem
first and foremost as a biobjective problem. The well-known dichotomic search
algorithm for biobjective problems is briefly summarized before we show how it
can be extended to robust problems. The opposite approach is taken in Section
4.1, where the problem is considered from a robust optimization perspective.
An optimization-pessimization approach for (single-objective) robust
optimization is reviewed and then extended to multiobjective problems.

In Section 5 we combine dichotomic search and optimization-pessimization and
receive two different methods for finding robust efficient solutions. For the
special case of a bilinear continuous objective function, we additionally
develop a dual approach together with dichotomic search in Section 5.3.
Numerical results are given in Section 6 and, finally, some conclusions are
drawn and suggestions for further research are formulated in Section 7.

##  2 Problem definition and preliminaries

In this section we briefly review multiobjective robust optimization. We start
with restating some definitions from robust optimization and multiobjective
optimization which we then combine to the emerging topic of multiobjective
robust optimization. We define what a robust efficient solution to an
uncertain multi-objective problem is and from this we derive the biobjective
mixed-integer linear robust optimization problem (BRO) — the problem to be
solved in this paper. We finally recall some concepts of multiobjective
optimization which are needed later.

#### Single-objective robust optimization.

Robust optimization deals with uncertain optimization problems, i.e., problems
with some uncertain parameters $\xi\in\mathbb{R}^{m}$ which depend on
measurements, future developments, delays or other uncertainties. Every $\xi$
is called a _scenario_. As usual in robust optimization, we assume that the
set $\mathcal{U}\subseteq\mathbb{R}^{m}$ of all possible scenarios is known.
We call $\mathcal{U}$ _uncertainty set_. A single-objective uncertain problem
is described by a family of parameterized optimization problems

$\left\\{\min_{x\in\mathcal{X}}h(x,\xi)\right\\}_{\xi\in\mathcal{U}}$ (1)

with $\mathcal{X}\subseteq\mathbb{R}^{n}$ and
$h\colon\mathcal{X}\times\mathcal{U}\to\mathbb{R}$.

There is usually no solution that is optimal for all scenarios. Instead one
aims to find _robust solutions_ which are reasonably good for all (or most)
scenarios. Out of many robustness concepts that have been defined (see, e.g.,
[GS16] for an overview on different robustness concepts), minmax robustness is
one of the most commonly used. For a detailed account of the subject, we refer
to [BTEN09]. A solution to problem (1) is called _(minmax) robust optimal_ if
it is an optimal solution to its _robust counterpart_

$\displaystyle\textup{P}^{\textup{single}}(\mathcal{U})$
$\displaystyle\min_{x\in\mathcal{X}}\sup_{\xi\in\mathcal{U}}h(x,\xi).$ (2)

#### Multiobjective (deterministic) problems.

Now let us turn to multiobjective problems

$\min_{x\in\mathcal{X}}\underbrace{\begin{pmatrix}g_{1}(x)\\\ g_{2}(x)\\\
\vdots\\\ g_{p}(x)\end{pmatrix}}_{\eqqcolon g(x)}$ (3)

with $\mathcal{X}\subseteq\mathbb{R}^{n}$ and
$g_{i}\colon\mathcal{X}\to\mathbb{R}$, $i=1,2,\dots,p$.

Instead of minimizing a scalar objective function, we have to compare vectors
in order to find an optimal solution. As common in multi-objective
optimization, we use the following vector relations: For two vectors
$y,\bar{y}\in\mathbb{R}^{p}$, the ordering relations $<$ and $\leq$ are meant
to be component-wise. Furthermore, if $y\leq\bar{y}$ and $y\not=\bar{y}$, we
write $y\preceq\bar{y}$ and say that $y$ _dominates_ $\bar{y}$. Accordingly,
we define $\mathbb{R}_{\succeq}^{p}\coloneqq\\{r\in\mathbb{R}^{p}\colon
r\succeq 0\\}$ and $\mathbb{R}^{p}_{\geq},\mathbb{R}^{p}_{>}$. Biobjective
optimization is the special case of multiobjective optimization with $p=2$.

The most important concept for multiobjective optimization is _efficiency_
(also called _Pareto optimality_). Given a multiobjective problem (3) a
solution $x\in\mathcal{X}$ is called _efficient_ and its image
$g(x)\in\mathcal{Y}\coloneqq g(\mathcal{X})\subset\mathbb{R}^{p}$ is called
_nondominated_ if no solution $x^{\prime}\in\mathcal{X}\setminus\\{x\\}$
exists, such that $g(x^{\prime})$ dominates $g(x)$. By
$\mathcal{Y}_{\textup{N}}$ we denote the set of nondominated points. These
points form the _Pareto frontier_.

#### Multiobjective robust optimization.

Real-world optimization problems often have multiple objective functions _and_
uncertain parameters. We consider multiobjective uncertain optimization
problems which depend on a scenario $\xi\in\mathcal{U}\subseteq\mathbb{R}^{m}$

$\displaystyle\textup{P}(\xi)$
$\displaystyle\min_{x\in\mathcal{X}}\underbrace{\begin{pmatrix}f_{1}(x,\xi)\\\
f_{2}(x,\xi)\\\ \vdots\\\ f_{p}(x,\xi)\end{pmatrix}}_{\eqqcolon f(x,\xi)}$ (4)

with $\mathcal{X}\subseteq\mathbb{R}^{n}$,
$f_{i}\colon\mathcal{X}\times\mathcal{U}\to\mathbb{R}$, $i=1,2,\dots,p$.
Analogously to single-objective optimization, one calls the parameterized
family

$\\{P(\xi)\colon\xi\in\mathcal{U}\\}$ (5)

an _uncertain multiobjective optimization problem_. We are interested in
finding efficient solutions to the uncertain multiobjective optimization
problem, which are robust.

Several ways to generalize minmax robustness to multiobjective uncertain
problems have been proposed (see [IS16, WD16] for surveys). In this article we
aim to find _point-based minmax robust efficient_ solutions as defined in
[KL12, Kuh+16]. A solution is called _point-based minmax robust efficient_
(from now on: _robust efficient_) if it is an efficient solution to

$\displaystyle P(\mathcal{U})$
$\displaystyle\min_{x\in\mathcal{X}}\begin{pmatrix}\sup_{\xi\in\mathcal{U}}f_{1}(x,\xi)\\\
\sup_{\xi\in\mathcal{U}}f_{2}(x,\xi)\\\ \vdots\\\
\sup_{\xi\in\mathcal{U}}f_{p}(x,\xi)\\\ \end{pmatrix}.$ (6)

$P(\mathcal{U})$ is called the _robust counterpart_ of the uncertain
multiobjective optimization problem (5) or just _multiobjective robust_
problem. Since $\mathcal{U}$ is varied within some of the proposed algorithms,
we refer to the specific set $\mathcal{U}$ in the notation $P(\mathcal{U})$.

To improve readability, we define
$f_{i}^{\mathcal{U}}(x)\coloneqq\sup_{\xi\in\mathcal{U}}f_{i}(x,\xi)$,
$i=1,2,\dots,p$ and set
$f^{\mathcal{U}}(x)\eqqcolon(f_{1}^{\mathcal{U}}(x),f_{2}^{\mathcal{U}}(x),\dots,f_{p}^{\mathcal{U}}(x))^{t}$
as the vector containing the $p$ objective functions. Problem (6) can hence be
interpreted as a (deterministic) multiobjective problem of type (3) with
$g\coloneqq f^{\mathcal{U}}$ as objective function. This point of view is used
in Section 3 and in Algorithms 5.2 and 5.3.

Finally, note that

$f^{\mathcal{U}^{\prime}}(x)\leq f^{\mathcal{U}}(x)\textup{ for
}\mathcal{U}^{\prime}\subseteq\mathcal{U}\textup{.}$ (7)

#### The problem to be solved: (BRO) – biobjective mixed-integer linear robust
optimization.

We consider uncertain biobjective optimization problems with $p=2$. Their
robust counterpart is given in (6), i.e., we receive the following biobjective
mixed-integer linear program with minmax objective function,

$\displaystyle\textup{BRO}(\mathcal{U})$
$\displaystyle\min_{x\in\mathcal{X}}\begin{pmatrix}\sup_{\xi\in\mathcal{U}}f_{1}(x,\xi)\\\
\sup_{\xi\in\mathcal{U}}f_{2}(x,\xi)\end{pmatrix}\textup{.}$ (BRO)

Our goal is to determine the Pareto frontier and the associated efficient
solutions of $\textup{BRO}(\mathcal{U})$.

For $\textup{BRO}(\mathcal{U})$ we always assume the following:

  * •

(BRO-1) a feasible set
$\mathcal{X}=P\cap(\mathbb{Z}^{k}\times\mathbb{R}^{n-k})$ where
$P\subseteq\mathbb{R}^{n}$ is a polytope and $0\leq k\leq n$,

  * •

(BRO-2) a polytope or finite set $\mathcal{U}\subseteq\mathbb{R}^{m}$, and

  * •

(BRO-3) functions $f_{1},f_{2}\colon\mathcal{X}\times\mathcal{U}\to\mathbb{R}$
which are linear in $x$ for every fixed $\xi\in\mathcal{U}$ and quasi-convex
and continuous in $\xi$ for every fixed $x\in\mathcal{X}$.

Under the latter two assumptions, (BRO-2) and (BRO-3), the supremum in the
definition of (BRO) is always attained and we can write maximum instead, i.e.,
$f^{\mathcal{U}}_{i}(x)=\max_{\xi\in\mathcal{U}}f_{i}(x,\xi)$ for
$x\in\mathcal{X}$, $i=1,2$. (BRO-3) guarantees that
$f_{i}\colon\mathcal{X}\times\mathcal{U}\to\mathbb{R}$ is jointly continuous
in $(x,\xi)$ (see, e.g., [KD69]). Finally, the feasible set $\mathcal{X}$
determines the type of the problem at hand: For $k=0$ the problem is a (pure)
_linear_ minmax problem, for $k=n$ the problem is an _integer linear_ minmax
problem and for $1\leq k<n$ we have a _mixed-integer linear_ minmax problem.

#### Concepts from multi-objective optimization.

We recall some concepts from multiobjective optimization which we need in this
paper. Consider the deterministic multiobjective problem (3). We first define
two special types of efficient solutions, namely _supported efficient_ and
_extreme supported efficient_ solutions. There exist slightly different
characterizations of these solutions. We use the definitions of Özpeynirci and
Köksalan (see [ÖK10]) and call a point $y\in\mathcal{Y}$ _extreme supported
nondominated_ , if there is no convex combination of nondominated points
$y^{(1)},y^{(2)},\dots,y^{(n)}\in\mathcal{Y}\setminus\\{y\\}$ such that
$\sum_{i=1}^{n}\lambda_{i}y^{(i)}\leq y$. We call a point _supported
nondominated_ , if there is no convex combination of nondominated points
$y^{(1)},y^{(2)},\dots,y^{(n)}\in\mathcal{Y}\setminus\\{y\\}$ such that
$\sum_{i=1}^{n}\lambda_{i}y^{(i)}<y$. A solution $x\in\mathcal{X}$ is called
_(extreme) supported efficient_ , if $y=g(x)$ is (extreme) supported
nondominated. A supported efficient solution can be found by solving the
scalarized weighted-sum problem

$\displaystyle P(\lambda)$
$\displaystyle\min_{x\in\mathcal{X}}\lambda_{1}g_{1}(x)+\lambda_{2}g_{2}(x)+\dots+\lambda_{p}g_{p}(x)$

for some weight vector $\lambda\in\mathbb{R}^{p}_{\succeq 0}$. We use
$\mathcal{Y}_{\textup{ESN}}$ to denote the set of extreme supported
nondominated points. Any subset of $\mathcal{X}$ whose image under $g$ is the
set of nondominated points $\mathcal{Y}_{\textup{N}}$ is called a
_representative set_ ; a set whose image under $g$ equals the set of extreme
supported nondominated points $\mathcal{Y}_{\textup{ESN}}$ is called
_representative set for the extreme supported efficient solutions_.

In the following we state two properties that are essential to prove some of
our results. The first is the existence of the _ideal point_

$y^{\text{I}}\coloneqq\begin{pmatrix}\min_{x\in\mathcal{X}}g_{1}(x)\\\
\min_{x\in\mathcal{X}}g_{2}(x)\\\ \vdots\\\
\min_{x\in\mathcal{X}}g_{p}(x)\end{pmatrix}$

for (3). We say that the _ideal point property_ is satisfied if an ideal point
exists, i.e.,

$\min_{x\in\mathcal{X}}g_{i}(x)\textup{ exists for }i=1,2,\dots,p.$ (ideal)

The second property we need is the _domination property_ (see [Hen86]).

For all $y\in\mathcal{Y}\setminus\mathcal{Y}_{\textup{N}}$, there exists a
point $y^{\prime}\in\mathcal{Y}_{\textup{N}}$ with $y^{\prime}\preceq y$.
(dom)

The following result is well known.

######  Lemma 1.

Let a multiobjective problem (3) be given. If $\mathcal{X}$ is finite, or if
$\mathcal{X}$ is compact and $g$ is continuous, then both, (ideal) and (dom)
hold.

###### Proof.

For (ideal) this is due to Weierstrass’ Extreme Value Theorem, for (dom) we
refer to [Hen86]. ∎

#### Domination and ideal point property for multiobjective robust
optimization problems.

We conclude this section by discussing under which assumptions (ideal) and
(dom) are satisfied for _robust_ multiobjective problems (see (6)), i.e., for
the case that the objective functions of (3) are given as $g=f^{\mathcal{U}}$.
For a discussion of (dom) in the context of multiobjective robust
optimization, see also [SZK21].

######  Theorem 2.

Let either

  1. (i)

$\mathcal{X}$ and $\mathcal{U}$ be compact and $f$ jointly continuous in
$\mathcal{X}$ and $\mathcal{U}$,

  2. (ii)

$\mathcal{X}$ be finite, $\mathcal{U}$ compact and $f$ continuous in
$\mathcal{U}$ for every fixed $x\in\mathcal{X}$,

  3. (iii)

$\mathcal{U}$ be finite, $\mathcal{X}$ compact and $f$ continuous in
$\mathcal{X}$ for every fixed $\xi\in\mathcal{U}$, or

  4. (iv)

$\mathcal{X}$ and $\mathcal{U}$ both be finite.

Then both, (dom) and (ideal) are satisfied for a multiobjective robust
optimization problem (3).

###### Proof.

We set $g_{i}(x)\coloneqq\sup_{\xi\in\mathcal{U}}f_{i}(x,\xi)$,
$i=1,2,\dots,p$, and distinguish two cases:

  * (a)

$\mathcal{X}$ is finite: Due to Lemma 1, (dom) and (ideal) hold if
$g_{i}(x)=\sup_{\xi\in\mathcal{U}}f_{i}(x,\xi)$ exists for all
$x\in\mathcal{X}$. This is the case since either $\mathcal{U}$ is finite or
$\mathcal{U}$ is compact and $f_{i}(x,\cdot)$ continuous for every fixed
$x\in\mathcal{X}$.

  * (b)

$\mathcal{X}$ is compact: In this case, Lemma 1 requires that $g_{i}(x)$ is
continuous. This holds since

    * –

either $\mathcal{U}$ is finite, hence $g(x)$ is continuous as the maximum of a
finite set of continuous functions $f(\cdot,\xi)$, $\xi\in\mathcal{U}$,

    * –

or $\mathcal{U}$ is compact and $f$ is jointly continuous in $(x,\xi)$ and
hence again, $g_{i}(x)$ is continuous.

∎

We conclude that (dom) and (ideal) hold for (BRO).

######  Corollary 3.

(BRO) satisfies both, (dom) and (ideal).

###### Proof.

By the assumptions of (BRO), $\mathcal{X}$ and $\mathcal{U}$ are both compact
(see (BRO-1) and (BRO-2)) and
$f_{i}:\mathcal{X}\times\mathcal{U}\to\mathbb{R}$ is jointly continuous in
$(x,\xi)$ for $i=1,2$ (BRO-3). Theorem 2 hence gives the result. ∎

##  3 Dichotomic search for biobjective minmax optimization

In this section we view our problem (BRO) as a deterministic biobjective
(mixed-integer) linear minmax problem. First, in Section 3.1, we repeat
dichotomic search from literature. In Section 3.2 we generalize this method
from biobjective mixed-integer linear optimization to biobjective mixed-
integer linear _minmax_ optimization, i.e., to problems of type (BRO).

###  3.1 Dichotomic search for biobjective mixed-integer linear optimization

We consider a special case of (3), namely biobjective linear mixed-integer
optimization problems,

$\min_{x\in\mathcal{X}}\begin{pmatrix}g_{1}(x)\\\
g_{2}(x)\end{pmatrix}\text{.}$ (8)

The feasible set $\mathcal{X}\subseteq\mathbb{R}^{n}$ is a polyhedron and as
in (BRO) it is intersected with $\mathbb{Z}^{k}\times\mathbb{R}^{n-k}$. The
objective functions $g_{1},g_{2}\colon\mathcal{X}\to\mathbb{R}$ are linear
functions.

A well-known approach to solve such problems is _dichotomic search_ ,
formulated in Algorithm 3.1. The method has first been published by Aneja and
Nair in 1979 (see [AN79]) and Cohon (see [Coh78]) for more specific problem
classes and is now part of multi-objective folklore and sometimes also known
as _Aneja and Nair’s bicriteria method_ (e.g., [UT94]) or _CAN method_ (e.g.,
[ÖK10]). Most frequently, it is used to solve biobjective _linear_ problems.
However, it can also be applied to biobjective _mixed-integer linear_ problems
where it determines all extreme supported efficient nondominated points
$Y^{\ast}$ and a representative set of extreme supported nondominated
solutions $X^{\ast}$. Dichotomic search takes advantage of the fact that in
$\mathbb{R}^{2}$ sorting nondominated solutions with respect to their first
coordinates is the same as reverse sorting by the second coordinate, i.e., for
two nondominated solutions $y^{l},y^{r}\in\mathcal{Y}\subset\mathbb{R}^{2}$,
$y^{l}_{1}<y^{r}_{1}$ implies $y^{r}_{2}>y^{l}_{2}$. The idea is to start with
the lexicographically optimal solutions and then in each step find a supported
non-dominated point “between” two given supported non-dominated points. The
method proceeds iteratively until all extreme supported nondominated points
are identified. Algorithmically, first, the lexicographic optimal solutions
$x^{L},x^{R}$ for (8) are computed. After that, in each iteration, a tuple
$(y^{l},y^{r})$ of two points known to be supported nondominated is taken and
$\lambda=(y^{l}_{2}-y^{r}_{2},y^{r}_{1}-y^{l}_{1})$, corresponding to the
slope $\frac{y^{l}_{2}-y^{r}_{2}}{y^{r}_{1}-y^{l}_{1}}$ of the line segment
from $y^{l}$ to $y^{r}$, is chosen. Solving the corresponding weighted-sum
(scalarized) problem

$\min_{x\in\mathcal{X}}\lambda^{t}g(x)$

either finds a new supported nondominated point between $y^{l}$ and $y^{r}$ or
certifies that there is no such point. The algorithm terminates when all
extreme supported nondominated points – each with a corresponding extreme
supported efficient solution – have been discovered. It might find also
supported nondominated points which are not extreme supported nondominated,
but these can be easily identified and removed.

0: Biobjective mixed-integer linear optimization problem (8).

0: Feasible set $\mathcal{X}$ is a polyhedron intersected with
$\mathbb{R}^{n-k}\times\mathbb{Z}^{k}$ for some $k\in\\{0,\ldots,n\\}$.

1: Initialize $\mathcal{L}\coloneqq\emptyset$. {$\mathcal{L}$ will contain
list of tuple images $(y^{l},y^{r})$ satisfying
$y^{l}_{1}<y^{r}_{1},y^{l}_{2}>y^{r}_{2}$}

2: Compute $\varepsilon_{1}\coloneqq\min_{x\in\mathcal{X}}g_{1}(x)$.

3: Determine
$x^{L}\in\operatorname*{arg\,min}_{x\in\mathcal{X}}\\{g_{2}(x)\colon
g_{1}(x)\leq\varepsilon_{1}\\}$.

4: Set $y^{L}\coloneqq g(x^{L})$.

5: Compute $\varepsilon_{2}\coloneqq\min_{x\in\mathcal{X}}g_{2}(x)$.

6: Determine
$x^{R}\in\operatorname*{arg\,min}_{x\in\mathcal{X}}\\{g_{1}(x)\colon
g_{2}(x)\leq\varepsilon_{2}\\}$.

7: Set $y^{R}\coloneqq g(x^{R})$.

8: if $y^{L}=y^{R}$ then

9: STOP. Only one nondominated image found.

10: return $Y^{\ast}=\\{y^{L}\\},X^{\ast}=\\{x^{L}\\}$.

11: else

12:
$Y^{\ast}=\\{y^{L},y^{R}\\},X^{\ast}=\\{x^{L},x^{R}\\},\mathcal{L}=\\{(y^{L},y^{R})\\}$.

13: end if

14: while $L\not=\emptyset$ do

15: Remove element $(y^{l},y^{r})$ from $\mathcal{L}$.

16: Compute $\lambda\coloneqq(y^{l}_{2}-y^{r}_{2},y^{r}_{1}-y^{l}_{1})$.

17: Determine
$x^{\ast}\in\operatorname*{arg\,min}_{x\in\mathcal{X}}\lambda^{T}g(x)$.

18: Set $y^{\ast}\coloneqq g(x^{\ast})$.

19: if $\lambda^{T}y^{\ast}<\lambda^{T}y^{l}$. then

20: Add $y^{\ast}$ to $Y^{\ast}$, add $x^{\ast}$ to $X^{\ast}$.

21: Add $(y^{l},y^{\ast}),(y^{\ast},y^{r})$ to $\mathcal{L}$.

22: end if

23: end while

24: return $Y^{\ast}$: contains all extreme supported nondominated points.

25: return $X^{\ast}$: contains a representative set of extreme supported
efficient solutions.

Determine lexicographic solutions

Solve weighted-sum problem for weights $\lambda$

Algorithm 3.1 Dichotomic search

Finiteness and correctness of Algorithm 3.1 follow from the considerations
above which are derived from the literature (e.g., [PKL19, ÖK10]) and are
stated in the following lemma. The lemma is valid if (8) satisfies (ideal).
This is a slight generalization to [ÖK10] who assumed that (8) is bounded by
the origin, i.e., $g_{i}(x)$, $i=1,2$, are non-negative for all
$x\in\mathcal{X}$.

######  Lemma 4 (e.g., [ÖK10]).

Let a biobjective problem as in (8) be given, i.e.,

  * •

with linear objectives $g_{1}$, $g_{2}$ and

  * •

a feasible set $\mathcal{X}$ that is a polyhedron intersected with
$\mathbb{R}^{n-k}\times\mathbb{Z}^{k}$.

  * •

Furthermore, let (ideal) hold for (8).

Then Algorithm 3.1 returns a set $Y^{\ast}$ containing all extreme supported
nondominated points and a set $X^{\ast}$ containing a representative set of
extreme supported efficient solutions after $2|Y^{\ast}|-3$ iterations (lines
15–22) if $|Y^{\ast}|>2$ and zero iterations if $|Y^{\ast}|=1$.

It is known that in the case of biobjective linear optimization problems, the
set of all extreme supported nondominated points and a representative set of
extreme supported efficient solutions can be used to construct all
nondominated points and a representative set of efficient solutions,
respectively. We will show a related result for (BRO) in Lemma 16 in Section
5.

###  3.2 Dichotomic search for biobjective mixed-integer linear _minmax_
optimization

Our goal is to apply dichotomic search to (BRO), i.e., to a biobjective mixed-
integer linear robust optimization problem which is given as the minmax
problem introduced in Section 2

$\displaystyle\textup{BRO}(\mathcal{U})$
$\displaystyle\min_{x\in\mathcal{X}}\begin{pmatrix}\sup_{\xi\in\mathcal{U}}f_{1}(x,\xi)\\\
\sup_{\xi\in\mathcal{U}}f_{2}(x,\xi)\end{pmatrix}$ (BRO revisited)

Recall that the functions $f_{1}$ and $f_{2}$ are linear in $x$ for every
fixed $\xi\in\mathcal{U}$ and
$\mathcal{X}=P\cap(\mathbb{Z}^{k}\times\mathbb{R}^{n-k})$ for a polyhedron $P$
and $0\leq k\leq n$, i.e., without the supremum (BRO) would satisfy the
requirements of Lemma 4. However, since the functions
$f_{i}^{\mathcal{U}}\colon\mathcal{X}\to\mathbb{R}$,
$x\mapsto\sup_{\xi\in\mathcal{U}}f_{i}(x,\xi)$, $i=1,2$, are not linear, we
aim to transform (BRO) to a biobjective mixed-integer linear optimization
problem, i.e., to a problem of type (8) for which we can apply dichotomic
search.

We proceed in two steps. The first step is to transform (BRO) to its
bottleneck version, i.e., to

$\displaystyle\textup{BRO}_{\textup{BN}}(\mathcal{U})$
$\displaystyle\min\begin{pmatrix}y_{1}\\\ y_{2}\end{pmatrix}$
$\displaystyle\text{s.t. }y_{1}$ $\displaystyle\geq f_{1}(x,\xi)$
$\displaystyle\;\forall\xi\in\mathcal{U}$ $\displaystyle y_{2}$
$\displaystyle\geq f_{2}(x,\xi)$ $\displaystyle\;\forall\xi\in\mathcal{U}$
$\displaystyle x$ $\displaystyle\in\mathcal{X}$ $\displaystyle y$
$\displaystyle\in\mathbb{R}^{2}$

This is justified by the following lemma which regards the relationship of
$\textup{BRO}(\mathcal{U})$ and $\textup{BRO}_{\textup{BN}}(\mathcal{U})$.

######  Lemma 5.

Let a problem of type (BRO) be given. In particular, let $\mathcal{U}$ be
compact and
$f_{i}(x,\cdot)\colon\operatorname*{conv}(\mathcal{U})\to\mathbb{R}$,
$x\in\mathcal{X}$, $i=1,2$, be continuous. Then

  1. (i)

$\\{(x,y):x\in\mathcal{X},y\geq f^{\mathcal{U}}(x)\\}\not=\emptyset$ is the
set of feasible solutions for $\textup{BRO}_{\textup{BN}}(\mathcal{U})$.

  2. (ii)

$X\subseteq\mathcal{X}$ is the set of efficient solutions to
$\textup{BRO}(\mathcal{U})$ if and only if $\\{(x,y):x\in
X,y=f^{\mathcal{U}}(x)\\}$ is the set of efficient solutions to
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$. In particular, the set of
nondominated points for $\textup{BRO}(\mathcal{U})$ and
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$ coincide.

  3. (iii)

The set of extreme supported nondominated points for
$\textup{BRO}(\mathcal{U})$ and $\textup{BRO}_{\textup{BN}}(\mathcal{U})$
coincide.

  4. (iv)

$X\subseteq\mathcal{X}$ is a representative set of extreme supported efficient
solutions to $\textup{BRO}(\mathcal{U})$ if and only if $\\{(x,y)\colon x\in
X,y=f^{\mathcal{U}}(x)\\}$ is a representative set of extreme supported
efficient solutions to $\textup{BRO}_{\textup{BN}}(\mathcal{U})$.

###### Proof.

  1. (i)

Directly by definition of $\textup{BRO}_{\textup{BN}}(\mathcal{U})$. The
feasible set of $\textup{BRO}_{\textup{BN}}(\mathcal{U})$ is not empty due to
compactness of $\mathcal{U}$.

  2. (ii)

Let $(x,y)$ be efficient for $\textup{BRO}_{\textup{BN}}(\mathcal{U})$. We
show that this yields $y=f^{\mathcal{U}}(x)$: Clearly, $y\geq
f^{\mathcal{U}}(x)$ otherwise $(x,y)$ is not feasible for
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$, (see (i)). Now assume that
$y_{i}>\max_{\xi\in\mathcal{U}}f_{i}(x,\xi)$ for $i\in\\{1,2\\}$. Then $(x,y)$
is dominated by the feasible solution $(x,f^{\mathcal{U}}(x))$ and hence not
efficient. The set of efficient solutions to
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$ hence is contained in
$\\{(x,f^{\mathcal{U}}(x)):x\in\mathcal{X}\\}$.

Note that $f^{\mathcal{U}}(x)$ is the objective function value of $x$ in
$\textup{BRO}(\mathcal{U})$ and also of $(x,f^{\mathcal{U}}(x))$ in
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$. This yields that $x$ is efficient
to $\textup{BRO}(\mathcal{U})$ if and only if $(x,f^{\mathcal{U}}(x))$ is
efficient to $\textup{BRO}_{\textup{BN}}(\mathcal{U})$. Hence, $X$ is the set
of efficient solutions to $\textup{BRO}(\mathcal{U})$ if and only if
$\\{(x,f^{\mathcal{U}}(x)):x\in X\\}$ is the set of efficient solutions to
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$ and the sets of nondominated points
of both problems coincide.

  3. (iii)

The definition of extreme supported nondominated solutions only uses the set
of nondominated points in objective space. Due to (ii) the set of nondominated
points for $\textup{BRO}(\mathcal{U})$ and
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$ coincide, hence also their extreme
supported nondominated points.

  4. (iv)

Let $X\subseteq\mathcal{X}$ be a representative set of extreme supported
efficient solutions to $\textup{BRO}(\mathcal{U})$. Then $f^{\mathcal{U}}(X)$
is the set of extreme supported nondominated points for
$\textup{BRO}(\mathcal{U})$. According to (iii), $f^{\mathcal{U}}(X)$ is also
the set of extreme supported nondominated points to
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$. Since $f^{\mathcal{U}}(X)$ is the
image of $\\{(x,f^{\mathcal{U}}(x)):x\in X\\}$ for
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$, the latter set is a representative
set of extreme supported efficient solutions to
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$.

Let there be a representative set of extreme supported efficient solutions to
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$. By (ii), it takes the form
$\\{(x,y)\colon x\in X,y=f^{\mathcal{U}}(x)\\}$ for some
$X\subseteq\mathcal{X}$.

Its image $f^{\mathcal{U}}(X)$ then is the set of extreme supported
nondominated solutions to $\textup{BRO}_{\textup{BN}}(\mathcal{U})$, and
according to (iii), also to $\textup{BRO}(\mathcal{U})$. Consequently, $X$ is
a representative set of extreme supported efficient solutions to
$\textup{BRO}(\mathcal{U})$.

∎

$\textup{BRO}_{\textup{BN}}(\mathcal{U})$ has linear objective functions.
However, to ensure its feasible set meets the requirements of Lemma 4, we
additionally need that the feasible set of
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$ is a polyhedron intersected with
$\mathbb{Z}^{k}\times\mathbb{R}^{n-k}$ for $0\leq k\leq n$. Then Algorithm 3.1
can be applied to $\textup{BRO}_{\textup{BN}}(\mathcal{U})$ and determines all
its extreme supported nondominated points and a representative set of extreme
supported efficient solutions. In the following lemma we show more, namely
that we do not need the bottleneck version but can apply Algorithm 3.1
directly to $\textup{BRO}(\mathcal{U})$ to receive the extreme supported
nondominated points and a representative set of extreme supported efficient
solutions of $\textup{BRO}(\mathcal{U})$, if the set $\mathcal{U}$ of
scenarios is finite.

######  Lemma 6.

Let a problem of type (BRO) be given and let (BRO-1) and (BRO-3) hold. We
assume that $\mathcal{U}$ is non-empty and finite.

Then Algorithm 3.1 applied to (BRO) returns a set $Y^{\ast}$ containing all
extreme supported nondominated points and a set $X^{\ast}$ containing a
representative set of extreme supported efficient solutions after
$2|Y^{\ast}|-3$ iterations (lines 14-23) if $|Y^{\ast}|>2$ and zero iterations
if $|Y^{\ast}|=1$.

###### Proof.

The proof is in two parts: First, we show that dichotomic search _applied to
the bottleneck version_ $\textup{BRO}_{\textup{BN}}(\mathcal{U})$ of
$\textup{BRO}(\mathcal{U})$ returns a representative set of extreme supported
efficient solutions and the set of all extreme supported nondominated points
for the (non-bottleneck) problem $\textup{BRO}(\mathcal{U})$. Second, we show
that applying dichotomic search directly to $\textup{BRO}(\mathcal{U})$ yields
the exact same solutions as applying it to the bottleneck version
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$.

For the first part we use that the bottleneck version of the problem, i.e.,
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$, meets the requirements of Lemma 4:
We use the assumptions made for (BRO) and see that
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$ is a biobjective problem with two
linear objectives $y_{1}$ and $y_{2}$. For the feasible set note that the
original feasible set $\mathcal{X}$ of $\textup{BRO}(\mathcal{U})$ is given as
$\mathcal{X}=P\cap(\mathbb{R}^{n-k}\times\mathbb{Z}^{k})$. Since we add two
variables and two linear constraints for each scenario from the finite set
$\mathcal{U}$ (see part (i) of Lemma 5) also the resulting feasible set for
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$ can be written as
$P^{\prime}\cap(\mathbb{R}^{n^{\prime}-k}\times\mathbb{Z}^{k})$ with a new
polyhedron $P^{\prime}$ and dimension $n^{\prime}=n+2$. Furthermore, (ideal)
holds due to Corollary 3.

Thus, due to Lemma 4, dichotomic search (Algorithm 3.1) can be applied and a
set $Y^{\ast}_{BN}$ containing all extreme supported nondominated points and a
representative set of extreme supported efficient solutions $X^{\ast}_{BN}$
for $\textup{BRO}_{\textup{BN}}(\mathcal{U})$ are determined after
$2|Y^{\ast}|-3$ iterations (lines 14-23) if $|Y^{\ast}|>2$ and zero iterations
if $|Y^{\ast}|=1$.

Lemma 5 (iv) shows that $X^{*}_{BN}=\\{(x,f^{\mathcal{U}}(x))\colon x\in X\\}$
for some set $X\subseteq\mathcal{X}$ which is a representative set of extreme
supported efficient solutions of $\textup{BRO}(\mathcal{U})$.

For the second part, note that the difference between using
$\textup{BRO}(\mathcal{U})$ or $\textup{BRO}_{BN}(\mathcal{U})$ concerns lines
2, 3, 5, 6, and each iteration of line 17 of Algorithm 3.1. However, there is
no difference between applying these steps to $\textup{BRO}(\mathcal{U})$ and
$\textup{BRO}_{\textup{BN}}(\mathcal{U})$: the feasible set of the latter
problem is of higher dimension than the feasible set of the former but their
outcomes in the objective space $\mathbb{R}^{2}$ coincide (see Lemma 5) and
only those are needed for subsequent computations. ∎

The lemma above justifies the application of dichotomic search to our problem
of interest (BRO) if $\mathcal{U}$ is finite. However, in (BRO) $\mathcal{U}$
may be a polytope. On the other hand, in (BRO-3) we made the additional – and
thus far unnecessary – assumption that
$f_{i}(x,\cdot)\colon\mathcal{U}\to\mathbb{R}$, $i=1,2$ are quasi-convex.
Utilizing this additional requirement, we now show that Lemma 6 is still valid
if $\mathcal{U}$ is a polytope instead of a finite set.

######  Lemma 7.

Let a problem of type (BRO) be given and let (BRO-1) and (BRO-3) hold. We
assume that $\mathcal{U}$ is a polytope.

Then Algorithm 3.1 applied to (BRO) returns a set $Y^{\ast}$ containing all
extreme supported nondominated points and a set $X^{\ast}$ containing a
representative set of extreme supported efficient solutions after
$2|Y^{\ast}|-3$ iterations (lines 14-23) if $|Y^{\ast}|>2$ and zero iterations
if $|Y^{\ast}|=1$.

###### Proof.

If $\mathcal{U}$ is a polytope it has a finite number of (not necessarily
known) extreme points $\xi_{1},\ldots,\xi_{l}$. Since the functions
$f_{1}(x,\cdot),f_{2}(x,\cdot)\colon\operatorname*{conv}(\mathcal{U})\to\mathbb{R}$,
$x\in\mathcal{X}$ are quasi-convex, according to [EIS14, Theorem 5.9],
$\textup{BRO}(\mathcal{U})$ and $\textup{BRO}(\\{\xi_{1},\ldots,\xi_{l}\\})$
are equivalent since their objective functions $f^{\mathcal{U}}$ and
$f^{\\{\xi_{1},\ldots,\xi_{l}\\}}$ are the same.

Lemma 6 justifies that we can apply Algorithm 3.1 to
$\textup{BRO}(\\{\xi_{1},\ldots,\xi_{l}\\})$ and get all extreme supported
nondominated points and a representative set of extreme supported efficient
solutions of $\textup{BRO}(\\{\xi_{1},\ldots,\xi_{l}\\})$ and hence also of
$\textup{BRO}(\mathcal{U})$ in $2|Y^{\ast}|-3$ iterations if $|Y^{\ast}|>2$
and zero iterations if $|Y^{\ast}|=1$. This, however, requires that
$\xi_{1},\ldots,\xi_{l}$ are known. Since finding the vertices of a given
polytope, known as _vertex enumeration_ , is a hard problem (see [Kha+09]), we
apply Algorithm 3.1 directly to $\textup{BRO}(\mathcal{U})$ without using the
extreme points of $\mathcal{U}$. Luckily, this can be done by using the
equivalence of $\textup{BRO}(\\{\xi_{1},\ldots,\xi_{l}\\})$ and
$\textup{BRO}(\mathcal{U})$ once more:

Namely, we replace $\textup{BRO}(\\{\xi_{1},\ldots,\xi_{l}\\})$ by
$\textup{BRO}(\mathcal{U})$ whenever it occurs in Algorithm 3.1, i.e, in Steps
2,3,6,7 and in Step 17 and note that it does not change any result.
Summarizing, we can also apply Algorithm 3.1 directly to
$\textup{BRO}(\mathcal{U})$. ∎

##  4 Optimization-pessimization for biobjective optimization

In the previous section, we conceived the problem (BRO) primarily as a
biobjective problem – with the more complicated objective function
$f^{\mathcal{U}}$ – and suggested biobjective optimization methods. In this
section, we take the perspective of a robust optimizer and apply a method
known from robust optimization. More precisely, we use a cutting plane
approach, called _optimization-pessimization_ , which is designed to find
minmax robust solutions of uncertain (but single-objective) optimization
problems. The approach is reviewed in Section 4.1 and extended to multi-
objective optimization problems in Section 4.2.

###  4.1 Optimization-pessimization for single-objective robust optimization

This section deals with uncertain (single-objective) optimization problems,

$\left\\{\min_{x\in\mathcal{X}}h(x,\xi)\colon\xi\in\mathcal{U}\right\\}\text{.}$
(1 revisited)

More specifically, we want to determine minmax robust solutions for such
problems and, to that end, solve the robust counterpart,

$\displaystyle\textup{P}^{\textup{single}}(\mathcal{U})$
$\displaystyle\min_{x\in\mathcal{X}}\sup_{\xi\in\mathcal{U}}h(x,\xi)\text{.}$
(2 revisited)

We assume that for every fixed $x\in\mathcal{X}$ the function
$h(x,\cdot)\colon\operatorname*{conv}(\mathcal{U})\to\mathbb{R}$ is continuous
and quasi-convex and that $\mathcal{U}$ is compact. Hence,
$\sup_{\xi\in\mathcal{U}}h(x,\xi)$ is attained for all $x\in\mathcal{X}$ and
from now on we can write $\max_{\xi\in\mathcal{U}}h(x,\xi)$ instead. Let us
denote
$z(\mathcal{U})\coloneqq\min_{x\in\mathcal{X}}\max_{\xi\in\mathcal{U}}h(x,\xi)$
as optimal objective function value of (2) for a given uncertainty set
$\mathcal{U}$.

There exist many approaches for solving problem (2), which are grouped in
[GYd15] into two classes: The first class of algorithms is based on
reformulations to avoid the maximum over an (often infinite) set. We follow
this approach in Section 5.3. The algorithms of the second class proceed
iteratively. They start with a small set of scenarios and add scenarios step
by step. These approaches are known under various names such as _cutting set
method_ ([MB09]), _cutting plane method_ ([BDL16]), _scenario relaxation
procedure_ ([Ass+08], [ABV09]), _outer approximation method_ ([Ree94] [BNA13]
[GS16]), _(modified) Benders decomposition approach_ ([Mon06], [SAG11]), or
_implementor-adversarial framework_ ([Bie07]).

We refer to it as _optimization-pessimization_. The idea is to utilize that
robust optimization problems are easier to solve for (very) small uncertainty
sets: The routine starts with a reduced set of scenarios
$\mathcal{U}^{\prime}$ for which a robust solution is determined. For this
solution, the routine determines a worst-case scenario out of the full
uncertainty set $\mathcal{U}$ which is added to $\mathcal{U}^{\prime}$. For
the new scenario set, a new robust solution is found. This procedure is
repeated until the quality of the solution found is good enough, see Figure 1
for an illustration.

Optimization: Determine robust solution $x^{\ast}\in\mathcal{X}$ of
$\textup{P}^{\textup{single}}(\mathcal{U}^{\prime})$ finding
$x^{\ast}\in\operatorname*{arg\,min}_{x\in\mathcal{X}}\max_{\xi\in\mathcal{U}^{\prime}}h(x,\xi)$
Pessimization: Determine worst-case scenario $\xi^{\ast}\in\mathcal{U}$ for
given $x^{\ast}$ finding
$\xi^{\ast}\in\operatorname*{arg\,max}_{\xi\in\mathcal{U}}h(x^{\ast},\xi)$ Add
scenario: $\mathcal{U}^{\prime}\coloneqq\mathcal{U}^{\prime}\cup\\{\xi\\}$
Figure 1: Optimization-pessimization for robust single-objective optimization
problems

Formally, the optimization and pessimization problems are defined as follows:
For any $\mathcal{U}^{\prime}\subseteq\mathcal{U}$ the _optimization problem_
is defined as

$\displaystyle\textup{P}^{\textup{single}}(\mathcal{U}^{\prime})$
$\displaystyle
z(\mathcal{U}^{\prime})\coloneqq\min_{x\in\mathcal{X}}\max_{\xi\in\mathcal{U}^{\prime}}h(x,\xi).$

It is a relaxation of $\textup{P}^{\textup{single}}(\mathcal{U})$ and, thus,
yields a lower bound for $\textup{P}^{\textup{single}}(\mathcal{U})$, i.e.,

$z(\mathcal{U}^{\prime})\leq z(\mathcal{U})\text{.}$ (9)

For a given $x\in\mathcal{X}$, the _pessimization problem_

$\displaystyle\text{Pess}(x)$ $\displaystyle
h^{\mathcal{U}}(x)\coloneqq\max_{\xi\in\mathcal{U}}h(x,\xi)$

evaluates $x$ over the complete set of scenarios $\mathcal{U}$ and, thus,
provides an upper bound for $z(\mathcal{U})$, i.e.,

$h^{\mathcal{U}}(x)\geq z(\mathcal{U})\textup{.}$ (10)

Algorithm 4.1 describes how this method can be put to use algorithmically if
$\mathcal{U}$ is a polytope or finite.

0: Robust optimization problem $P(\mathcal{U})$ as in (2).

0: Finite initial set $\mathcal{U}^{(0)}\subseteq\mathcal{U}$.

0: Either $\mathcal{U}$ finite or $\mathcal{U}$ a polytope and $h(x,\cdot)$
continuous and quasi-convex.

Set $k\coloneqq 0$.

repeat

Set $\mathcal{U}^{(k+1)}\coloneqq\mathcal{U}^{(k)}$.

Determine
$x^{k}\in\operatorname*{arg\,min}_{x\in\mathcal{X}}\\{\max_{\xi\in\mathcal{U}^{k}}h(x,\xi)\\}$.
Set $z(\mathcal{U}^{(k)})\coloneqq\max_{\xi\in\mathcal{U}^{(k)}}h(x^{k},\xi)$.

For given $x^{k}$ determine solution
$\xi^{k}\in\operatorname*{arg\,max}_{\mathcal{U}}h(x^{k},\xi^{k})$. Set
$h^{\mathcal{U}}(x^{k})\coloneqq h(x^{k},\xi^{k})$.

Add $\xi^{k}$ to $\mathcal{U}^{(k+1)}$.

Set $k\coloneqq k+1$.

until $h^{\mathcal{U}}(x^{k-1})=z(\mathcal{U}^{(k-1)})$.

return robust solution $x^{\ast}$.

return set of worst-case scenarios
$\mathcal{U}^{\textup{FINAL}}\coloneqq\mathcal{U}^{k}$.

Optimization

Pessimization

Algorithm 4.1 Optimization-pessimization for single-objective robust
optimization

The routine produces a sequence of sets

$\mathcal{U}^{(0)}\subseteq\mathcal{U}^{(1)}\subseteq\mathcal{U}^{(2)}\subseteq\dots\subseteq\mathcal{U}.$
(11)

According to (9) we receive a sequence of lower bounds

$z(\mathcal{U}^{(0)})\leq z(\mathcal{U}^{(1)})\leq
z(\mathcal{U}^{(2)})\leq\dots\leq z(\mathcal{U})$ (12)

and, a feasible solution $x^{k}$ in each iteration from which we can derive an
upper bound according to (10), i.e.,

$z(\mathcal{U}^{(k)})\leq z(\mathcal{U})\leq h^{\mathcal{U}}(x^{k})\textup{.}$
(13)

We stop when lower and upper bound coincide. Then an optimal solution to (2)
and thus a (minmax) robust optimal solution to (1) has been found. For more
detailed discussions of the method we refer to [BDL16, ABV09, PS20]. The
finiteness of Algorithm 4.1 for uncertainty sets $\mathcal{U}$ that are
polytopes is shown in the following lemma in part (ii).

######  Lemma 8.

Assume that $\textup{P}^{\textup{single}}(\mathcal{U})$ has an optimal
solution and $\textup{P}^{\textup{single}}(\mathcal{U}^{\prime})$ has an
optimal solution for all finite $\mathcal{U}^{\prime}\subseteq\mathcal{U}$.

  1. (i)

Let $\mathcal{U}$ be finite. Then Algorithm 4.1 returns a solution to
$\textup{P}^{\textup{single}}(\mathcal{U})$ in at most $|\mathcal{U}|$
iterations.

  2. (ii)

Let $\mathcal{U}$ be a polytope or finite and let
$\operatorname*{ext}(\mathcal{U})$ be its set of extreme points. Let
$h(x,\cdot)\colon\operatorname*{conv}(\mathcal{U})\to\mathbb{R}$,
$x\in\mathcal{X}$, be continuous and quasi-convex. Then Algorithm 4.1 returns
a solution to $\textup{P}^{\textup{single}}(\mathcal{U})$ in at most
$|ext(\mathcal{U})|$ iterations if we choose an algorithm for the
pessimization problem $\textup{Pess}(x)$ which always finds an extreme point
of $\mathcal{U}$.

###### Proof.

Algorithm 4.1 stops if the lower and upper bound for $z(\mathcal{U})$ coincide
(see line 8 of Algorithm 4.1), i.e., if
$h^{\mathcal{U}}(x^{k})=z(\mathcal{U}^{(k)})$. We hence have that $x^{k}$ is
an optimal solution. Note that

$\max_{\xi\in\mathcal{U}}h(x^{k},\xi)=h^{\mathcal{U}}(x^{k})=z(\mathcal{U}^{(k)})=\max_{\xi\in\mathcal{U}^{(k)}}h(x^{k},\xi)\textup{,}$
(14)

if at least one worst-case scenario of $\mathcal{U}$ for $x^{k}$ is already
contained in $\mathcal{U}^{(k)}$. For a finite uncertainty set, in every
iteration either a new worst-case scenario is added or (14) holds and the
procedure stops. The latter happens after at most $|\mathcal{U}|$ iterations
which shows (i).

For (ii), consider the pessimization problem $\textup{Pess}(x^{k})$: here we
maximize a continuous function over a compact set $\mathcal{U}$, i.e., a
maximum always exists. Since $h(x,\cdot)$ is quasi-convex, a maximum is always
attained at an extreme point of $\mathcal{U}$. If we choose an algorithm that
returns an extreme point for such optimization problems, we add a new extreme
point in each iteration. Since the number of extreme points of $\mathcal{U}$
is finite the procedure stops when (14) holds. As in part (i) this happens
after at most $|\operatorname*{ext}(\mathcal{U})|$ iterations. ∎

We remark that Algorithm 4.1 also converges for bounded non-polyhedral sets
$\mathcal{U}$ under uniform Lipschitz-continuity in $x$ for all fixed values
of $\xi$ (see [MB09]).

###  4.2 Optimization-pessimization for multi-objective robust optimization

#### Optimization and pessimization problem in the multiobjective case.

In order to apply optimization-pessimization to (BRO), we need to generalize
it to biobjective problems. In this section we go a step further and consider
minmax problems with $p$ objective functions, i.e.,

$\displaystyle P(\mathcal{U})$
$\displaystyle\min_{x\in\mathcal{X}}\begin{pmatrix}\sup_{\xi\in\mathcal{U}}f_{1}(x,\xi)\\\
\sup_{\xi\in\mathcal{U}}f_{2}(x,\xi)\\\ \vdots\\\
\sup_{\xi\in\mathcal{U}}f_{p}(x,\xi)\\\ \end{pmatrix}\text{.}$ (6 revisited)

for which we aspire to determine a representative set of extreme supported
efficient solutions. With this purpose in mind, we develop a generalized
version of optimization-pessimization of Section 4.1.

The optimization problem $P(\mathcal{U}^{\prime})$ for
$\mathcal{U}^{\prime}\subseteq\mathcal{U}$ is the multiobjective optimization
problem

$\displaystyle P(\mathcal{U}^{\prime})$ $\displaystyle
z(\mathcal{U}^{\prime})\coloneqq\min_{x\in\mathcal{X}}\begin{pmatrix}\sup_{\xi\in\mathcal{U}^{\prime}}f_{1}(x,\xi)\\\
\sup_{\xi\in\mathcal{U}^{\prime}}f_{2}(x,\xi)\\\ \vdots\\\
\sup_{\xi\in\mathcal{U}^{\prime}}f_{p}(x,\xi)\end{pmatrix}\text{.}$ (15)

The pessimization problem

$\displaystyle\textup{Pess}(x)$ $\displaystyle
f^{\mathcal{U}}(x)\coloneqq\begin{pmatrix}\sup_{\xi\in\mathcal{U}}f_{1}(x,\xi)\\\
\sup_{\xi\in\mathcal{U}}f_{2}(x,\xi)\\\ \vdots\\\
\sup_{\xi\in\mathcal{U}}f_{p}(x,\xi)\end{pmatrix}$ (16)

for given $x\in\mathcal{X}$ consists of $p$ indepedent pessimization problems.

#### Lower and upper bounds provided by the optimization and the pessimization
problem.

We first discuss the optimization and pessimization problems in relation to
(6) which we are interested to solve.

For single-objective problems (6), the solutions to
$\textup{P}^{\textup{single}}(\mathcal{U}^{\prime})$ and $\textup{Pess}(x)$
provide lower and upper bounds to (6). In the multi-objective setting we do
not evaluate single solutions, but we need to evaluate (Pareto) sets. Sets can
be compared by set order relations, one of the most common ones is the _upper
setless order_ : For two sets $Y_{1},Y_{2}\subset\mathbb{R}^{p}$ it is defined
as follows:

$Y_{1}\preceq^{upp}Y_{2}\mbox{ if for all }y\in Y_{2}\mbox{ there exists
}\tilde{y}\in Y_{1}\mbox{ with }\tilde{y}\leq y.$

In this sense, we can say that $Y_{1}$ is an (upper setless) lower bound on
$Y_{2}$. We now use the upper setless order to generalize (13) showing that
for multi-objective optimization we also get lower and upper bounds on (6)
when solving (15) and (16) for a subset $\mathcal{U}^{\prime}$ of
$\mathcal{U}$. More precisely, let $X^{\ast}(\mathcal{U})$ be the set of
efficient solutions to (6). Then $\\{f^{\mathcal{U}}(x)\colon x\in
X^{\ast}(\mathcal{U})\\}$ describes the Pareto frontier of (6). It can be
bounded based on the solutions of the relaxation $P(\mathcal{U}^{\prime})$ as
follows.

######  Lemma 9.

Let $\mathcal{U}^{\prime}\subseteq\mathcal{U}$ and denote
$X^{\ast}(\mathcal{U}^{\prime})$ and $X^{\ast}(\mathcal{U})$ the set of
efficient solutions of $P(\mathcal{U}^{\prime})$, and $P(\mathcal{U})$,
respectively. Assume that $P(\mathcal{U}^{\prime})$, and $P(\mathcal{U})$ both
satisfy the domination property (dom). Then the following holds for the upper
setless order $\preceq^{upp}$:

$\\{f^{\mathcal{U}^{\prime}}(x)\colon x\in
X^{\ast}(\mathcal{U}^{\prime})\\}\preceq^{upp}\\{f^{\mathcal{U}}(x)\colon x\in
X^{\ast}(\mathcal{U})\\}\preceq^{upp}\\{f^{\mathcal{U}}(x)\colon x\in
X^{\ast}(\mathcal{U}^{\prime})\\}$ (17)

###### Proof.

We first show the left hand side of (17). To this end, take $x\in
X^{\ast}(\mathcal{U})$. We want to show that there exists $\tilde{x}\in
X^{\ast}(\mathcal{U}^{\prime})$ such that

$f^{\mathcal{U}^{\prime}}(\tilde{x})\leq f^{\mathcal{U}}(x).$ (18)

From $\mathcal{U}^{\prime}\subseteq\mathcal{U}$ we get that
$f^{\mathcal{U}^{\prime}}(x)\leq f^{\mathcal{U}}(x)$, see (7). Hence, if $x\in
X^{\ast}(\mathcal{U}^{\prime})$ we set $\tilde{x}\coloneqq x$ and are done.
Otherwise, $x\not\in X^{\ast}(\mathcal{U}^{\prime})$, i.e., $x$ is not an
efficient solution to $P(\mathcal{U}^{\prime})$. Then, due to the domination
property, there exists $\tilde{x}\in X^{\ast}(\mathcal{U}^{\prime})$ with
$f^{\mathcal{U}^{\prime}}(\tilde{x})\leq f^{\mathcal{U}^{\prime}}(x)\leq
f^{\mathcal{U}}(x)$ and (18) holds.

For the right hand side, we take $x\in X^{\ast}(\mathcal{U}^{\prime})$. The
goal is to find $\tilde{x}\in X^{\ast}(\mathcal{U})$ such that

$f^{\mathcal{U}}(\tilde{x})\leq f^{\mathcal{U}}(x)\textup{.}$

Similar as above, if $x\in X^{\ast}(\mathcal{U})$ we set $\tilde{x}\coloneqq
x$ and are done. Otherwise, $x$ is not efficient for $P(\mathcal{U})$ and due
to the domination property we find $\tilde{x}\in X^{\ast}(\mathcal{U})$ with
$f^{\mathcal{U}}(\tilde{x})\leq f^{\mathcal{U}}(x)$ which finishes the proof.
∎

The statement in (17) is the multiobjective analog of (13).

#### Reduction of the scenario set.

In this paragraph, we examine the conditions under which a reduced uncertainty
set $\mathcal{U}^{\prime}\subset\mathcal{U}$ already contains all relevant
scenarios, such that the efficient solutions $P(\mathcal{U}^{\prime})$ are the
same as those of $P(\mathcal{U})$. In the single-objective setting this is the
case if for an efficient solution to $P(\mathcal{U}^{\prime})$ a worst-case
scenario is already included in $\mathcal{U}^{\prime}$ (see (14)). We call
this the worst-case property (wc). The following theorem formalizes the above
considerations and shows when the efficient solutions of $P(\mathcal{U})$ and
$P(\mathcal{U}^{\prime})$ coincide.

######  Theorem 10.

Let $\mathcal{U}^{\prime}\subset\mathcal{U}$. Consider $x\in\mathcal{X}$. If
we have

$\displaystyle\sup_{\xi\in\mathcal{U}^{\prime}}f_{i}(x,\xi)=\sup_{\xi\in\mathcal{U}}f_{i}(x,\xi)\text{
for all }i=1,2,\dots,p\text{,}$ (wc)

then the following holds:

$x\text{ is efficient for }P(\mathcal{U}^{\prime})\Rightarrow x\text{ is
efficient for }P(\mathcal{U})\text{.}$

Additionally, if the domination property (dom) holds for
$P(\mathcal{U}^{\prime})$ and _all_ solutions $x\in\mathcal{X}$ that are
efficient for $P(\mathcal{U}^{\prime})$ satisfy (wc), then the following
holds:

$\displaystyle x\text{ is efficient for
}P(\mathcal{U}^{\prime})\Leftrightarrow x\text{ is efficient for
}P(\mathcal{U})\text{.}$

###### Proof.

$\Rightarrow$: Let $x$ be efficient for $P(\mathcal{U}^{\prime})$ and satisfy
(wc), i.e., $f^{\mathcal{U}^{\prime}}(x)=f^{\mathcal{U}}(x)$. Assume to the
contrary that $x$ is not efficient for $P(\mathcal{U})$, i.e., there exists
$x^{\prime}\in\mathcal{X}$, such that

$f^{\mathcal{U}}(x^{\prime})\preceq f^{\mathcal{U}}(x)\text{.}$ (19)

$\mathcal{U}^{\prime}\subseteq\mathcal{U}$, hence
$f^{\mathcal{U}^{\prime}}(x^{\prime})\leq f^{\mathcal{U}}(x^{\prime})$, see
(7). This leads to

$f^{\mathcal{U}^{\prime}}(x^{\prime})\stackrel{{\scriptstyle\eqref{eq:U'relaxation}}}{{\leq}}f^{\mathcal{U}}(x^{\prime})\stackrel{{\scriptstyle\eqref{eq:pb-
proof01}}}{{\preceq}}f^{\mathcal{U}}(x)\stackrel{{\scriptstyle\eqref{eq:WCincluded}}}{{=}}f^{\mathcal{U}^{\prime}}(x),$

which contradicts efficiency of $x$ for $P(\mathcal{U}^{\prime})$.

$\Leftarrow$: Let (wc) hold for all solutions which are efficient for
$P(\mathcal{U}^{\prime})$ and let $x$ be efficient for $P(\mathcal{U})$.
Assume to the contrary that $x\in\mathcal{X}$ is not efficient for
$P(\mathcal{U}^{\prime})$. Then, since the domination property holds, there is
a solution $x^{\prime}\in\mathcal{X}$ that is efficient for
P($\mathcal{U}^{\prime}$) such that

$f^{\mathcal{U}^{\prime}}(x^{\prime})\preceq
f^{\mathcal{U}^{\prime}}(x)\text{.}$ (20)

Note that since $x^{\prime}$ is efficient for $P(\mathcal{U}^{\prime})$, it
satisfies (wc). Together with $\mathcal{U}^{\prime}\subseteq\mathcal{U}$ we
receive

$f^{\mathcal{U}}(x^{\prime})\stackrel{{\scriptstyle\eqref{eq:WCincluded}}}{{=}}f^{\mathcal{U}^{\prime}}(x^{\prime})\stackrel{{\scriptstyle\eqref{eq:pb-
proof02}}}{{\preceq}}f^{\mathcal{U}^{\prime}}(x)\stackrel{{\scriptstyle\eqref{eq:U'relaxation}}}{{\leq}}f^{\mathcal{U}}(x)\text{.}$

This contradicts the assumption of $x$ being efficient for $P(\mathcal{U})$. ∎

Checking _all_ efficient solutions of a multiobjective problem is
computationally hard (or even impossible). Thus, in the next result we
strengthen the above theorem in a fashion that (wc) must only be satisfied for
all solutions from a representative set.

######  Theorem 11.

Let the domination property (dom) be satisfied for $P(\mathcal{U})$ and
$P(\mathcal{U}^{\prime})$. If there is a representative set
$\mathcal{R}^{\prime}$ of efficient solutions for $P(\mathcal{U}^{\prime})$
whose elements satisfy (wc), then we have:

  1. (i)

$x\in\mathcal{R}^{\prime}$ $\Rightarrow$ $x$ is efficient for
$P(\mathcal{U})$,

  2. (ii)

$x$ is efficient for $P(\mathcal{U})$ $\Rightarrow$ $x$ is efficient for
$P(\mathcal{U}^{\prime})$, and

  3. (iii)

$\mathcal{R}^{\prime}$ is a representative set of efficient solutions to
$P(\mathcal{U})$.

###### Proof.

  1. (i)

Let $x\in\mathcal{R}^{\prime}$. In particular, $x$ is efficient for
$P(\mathcal{U}^{\prime})$ and by assumption it satisfies (wc). We can hence
apply Theorem 10 and conclude that $x$ is efficient for $P(\mathcal{U})$.

  2. (ii)

Let $x$ be efficient for $P(\mathcal{U})$ and assume $x$ is not efficient for
$P(\mathcal{U}^{\prime})$. Due to the domination property, there is is a
solution $x^{\prime}$ that satisfies
$f^{\mathcal{U}^{\prime}}(x^{\prime})\preceq f^{\mathcal{U}^{\prime}}(x)$.
Moreover, since $\mathcal{R}^{\prime}$ is a representative set for
$P(\mathcal{U}^{\prime})$ we can choose $x^{\prime}\in\mathcal{R}^{\prime}$.
Hence, (wc) holds for $x^{\prime}$ and we receive

$f^{\mathcal{U}}(x^{\prime})\stackrel{{\scriptstyle\eqref{eq:WCincluded}}}{{=}}f^{\mathcal{U}^{\prime}}(x^{\prime})\stackrel{{\scriptstyle}}{{\preceq}}f^{\mathcal{U}^{\prime}}(x)\stackrel{{\scriptstyle\eqref{eq:U'relaxation}}}{{\leq}}f^{\mathcal{U}}(x)\text{.}$

This contradicts efficiency of $x$ for $P(\mathcal{U})$.

  3. (iii)

Let $\mathcal{R}\subset\mathcal{X}$ be a representative set of efficient
solutions for $P(\mathcal{U})$. We show that
$f^{\mathcal{U}}(\mathcal{R}^{\prime})=f^{\mathcal{U}}(\mathcal{R})$.
$\subset$: Let $y^{\prime}\in f^{\mathcal{U}}(\mathcal{R}^{\prime})$. Then
$y^{\prime}=f^{\mathcal{U}}(x^{\prime})$ for some
$x^{\prime}\in\mathcal{R}^{\prime}$. According to (i), $x^{\prime}$ is
efficient for $P(\mathcal{U})$, hence $y^{\prime}\in
f^{\mathcal{U}}(\mathcal{R})$.
$\supset$: Let $y\in f^{\mathcal{U}}(\mathcal{R})$. Then
$y=f^{\mathcal{U}}(x)$ for some $x$ that is efficient for $P(\mathcal{U})$.
According to (ii), $x$ is also efficient for $P(\mathcal{U}^{\prime})$. Hence,
$x^{\prime}\in\mathcal{R}^{\prime}$ exists such that
$f^{\mathcal{U}^{\prime}}(x)=f^{\mathcal{U}^{\prime}}(x^{\prime})$. This leads
to

$y=f^{\mathcal{U}}(x)\stackrel{{\scriptstyle\eqref{eq:U'relaxation}}}{{\geq}}f^{\mathcal{U}^{\prime}}(x)=f^{\mathcal{U}^{\prime}}(x^{\prime})\stackrel{{\scriptstyle\eqref{eq:WCincluded}}}{{=}}f^{\mathcal{U}}(x^{\prime})\textup{.}$

Since by assumption $y$ is nondominated for $P(\mathcal{U})$, equality must
hold true. Thus, $y=f^{\mathcal{U}}(x^{\prime})$ for
$x^{\prime}\in\mathcal{R}^{\prime}$ and, consequently, $y\in
f^{\mathcal{U}}(\mathcal{R}^{\prime})$.

∎

Theorem 11 shows that it is not necessary to check the worst-case property
(wc) for _all_ efficient solutions, rather it is sufficient to check it only
for a representative set. However, a representative set may still be infinite,
even for linear problems.

In Theorem 14 we show that the statement of Theorem 11 remains valid if we
replace the set of all efficient solutions not only by a representative set,
but even by a representative set of only their extreme supported solutions.
Recall that in Section 3.1 with dichotomic search we provided an algorithm for
computing such a representative set of extreme supported solutions. In
preparation for Theorem 14 we need the following lemma and corollary that
investigate the relation of extreme supported nondominated points with the set
of all images $\mathcal{Y}=f^{\mathcal{U}}(\mathcal{X})$.

######  Lemma 12.

Let a multi-objective optimization problem (3) with
$\mathcal{Y}\subsetneq\mathbb{R}^{p}$ compact be given and let
$\mathcal{Y}_{\textup{ESN}}\not=\emptyset$ be its set of extreme supported
nondominated points. We assume that $\mathcal{Y}_{\textup{ESN}}$ is finite.
Then
$\mathcal{Y}\subseteq\operatorname*{conv}(\mathcal{Y}_{\textup{ESN}})+\mathbb{R}^{p}_{\geq}$
holds.

###### Proof.

Assume there is a $\bar{y}\in\mathcal{Y}$ that does not lie in
$\operatorname*{conv}(\mathcal{Y}_{\textup{ESN}})+\mathbb{R}^{p}$. We then can
show that there is also $\hat{y}$ outside of
$\operatorname*{conv}(\mathcal{Y}_{\textup{ESN}})+\mathbb{R}^{p}$ which is
extreme supported nondominated, a contradiction.

So, assume to the contrary that
$\bar{y}\in\mathcal{Y}\setminus(\operatorname*{conv}(\mathcal{Y}_{\textup{ESN}})+\mathbb{R}^{p}_{\geq})$
exists. Then the sets $\\{\bar{y}\\}$ and
$\operatorname*{conv}(\mathcal{Y}_{\textup{ESN}})+\mathbb{R}^{p}_{\geq 1}$ are
disjoint, nonempty, closed and convex sets. Hence, a separating hyperplane
exists (see [BV04]), i.e., $\nu\in\mathbb{R}^{p}\setminus\\{0\\}$ and
$s\in\mathbb{R}$ exist such that

$\nu^{t}\bar{y}<s<\nu^{t}y,\;\forall
y\in\operatorname*{conv}(\mathcal{Y}_{\textup{ESN}})+\mathbb{R}^{p}_{\geq}\textup{.}$
(21)

The elements of
$\operatorname*{conv}(\mathcal{Y}_{\textup{ESN}})+\mathbb{R}^{p}_{\geq}$ can
get arbitrarily big in each component, hence $\nu_{i}\geq 0$ for all
$i=1,2,\dots,p$. Let now $z_{\nu}\coloneqq\min\\{\nu^{t}y\colon
y\in\mathcal{Y}\\}$ and
$\mathcal{Y}_{\nu}\coloneqq\operatorname*{arg\,min}\\{\nu^{t}y\colon
y\in\mathcal{Y}\\}$. Since $\bar{y}\in\mathcal{Y}$, we get

$\nu^{t}y^{\ast}\leq\nu^{t}\bar{y}<s,\;\forall y^{\ast}\in\mathcal{Y}_{\nu}.$
(22)

Together with (21) this shows that the elements in $\mathcal{Y}_{\nu}$ can be
separated from
$\operatorname*{conv}(\mathcal{Y}_{\textup{ESN}})+\mathbb{R}_{\geq}^{p}$ and,
hence, cannot be extreme supported nondominated themselves. Specifically, the
lexicographic minimum,
$\hat{y}\coloneqq\operatorname*{lex\,min}_{y\in\mathcal{Y}_{\nu}}$, i.e.,
$\hat{y}_{j}=\min\\{y_{j}\colon
y\in\mathcal{Y}_{\nu},y_{1}=\hat{y}_{1},\dots,y_{j-1}=\hat{y}_{j-1}\\}$,
$j=1,2,\dots,p$, is not extreme supported nondominated (the existence of this
point follows from compactness of $\mathcal{Y}$).

Hence, a nontrivial convex combination of nondominated points
$y^{(1)},\dots,y^{(n)}\in\mathcal{Y}$ exists such that

$\hat{y}\geq\sum_{i=1}^{n}\lambda_{i}y^{(i)}\textup{.}$ (23)

Now we assume that $y^{(i)}\not\in\mathcal{Y}_{\nu}$ for at least one
$i=1,2,\dots,n$. Wlog., assume $y^{(1)}\not\in\mathcal{Y}_{\nu}$. Then

$\nu^{t}\sum_{i=1}^{n}\lambda_{i}y^{(i)}=\lambda_{1}\underbrace{\nu^{t}y^{(1)}}_{>z_{\nu}}+\sum_{i=2}^{n}\underbrace{\nu^{t}\lambda_{i}y^{(i)}}_{\geq
z_{\nu}}>\sum_{i=1}^{n}\lambda_{i}z_{\nu}=z_{\nu}=\nu^{t}\hat{y}\textup{.}$
(24)

Since $\nu_{i}\geq 0$, $i=1,2,\dots,n$, (24) contradicts (23). Thus, our
assumption that $y^{(i)}\not\in\mathcal{Y}_{\nu}$ for at least one
$i=1,2,\dots,n$ is contradicted and we have that $y^{(i)}\in\mathcal{Y}_{\nu}$
for all $i=1,2,\dots,n$.

Consequently, a nontrivial convex combination only consisting of nondominated
points $y^{(1)},\dots,y^{(n)}\in\mathcal{Y}_{\nu}\subseteq\mathcal{Y}$ exists
such that (23) holds. This, however, is not possible since, by definition,
$\hat{y}$ is the lexicographic minimum of $\mathcal{Y}_{\nu}$ and thus all
other elements of $\mathcal{Y}_{\nu}$ lie in the lexicographic cone
$\hat{y}+\\{y\in\mathbb{R}^{p}\colon y_{1}=y_{2}=\dots
y_{i}=0,y_{i+1}>0\textup{ for some }i=0,1,\dots,p\\}$. ∎

The following corollary will be used in the proof of the subsequent theorem.

######  Corollary 13.

Under the assumptions of Lemma 12 for any
$y\in\mathcal{Y}\setminus\mathcal{Y}_{\textup{ESN}}$, a nontrivial convex
combination

$\sum_{i=1}^{n}\lambda_{i}y^{(i)}\leq y$

with $y^{(1)},\dots,y^{(n)}\in\mathcal{Y}_{\textup{ESN}}$ exists.

We can now utilize the above corollary and show that the statement of Theorem
11 remains valid even if only representative sets of extreme supported
efficient solutions are considered.

######  Theorem 14.

Let the domination property (dom) be satisfied for $P(\mathcal{U})$ and
$P(\mathcal{U}^{\prime})$. If $\mathcal{Y}$ is compact and there is a finite
representative set $\mathcal{R}^{\prime}_{\text{ESE}}$ of extreme supported
efficient solutions for $P(\mathcal{U}^{\prime})$ whose elements satisfy (wc),
then

  1. (i)

$x\in\mathcal{R}^{\prime}_{\text{ESE}}$ $\Rightarrow$ $x$ is extreme supported
efficient for $P(\mathcal{U})$,

  2. (ii)

$x$ is extreme supported efficient for $P(\mathcal{U})$ $\Rightarrow$ $x$ is
extreme supported efficient for $P(\mathcal{U}^{\prime})$, and

  3. (iii)

$\mathcal{R}^{\prime}_{\text{ESE}}$ is a representative set of extreme
supported efficient solutions to $P(\mathcal{U})$.

###### Proof.

  1. (i)

Let $x\in\mathcal{R}^{\prime}_{\text{ESE}}$. Assume to the contrary that $x$
is not extreme supported efficient for $P(\mathcal{U})$, i.e., there exists a
nontrivial convex combination of solutions efficient for $P(\mathcal{U})$
$x^{\prime}_{1},\dots,x^{\prime}_{n}\in\mathcal{X}$, and
$\lambda\in\mathbb{R}_{\geq 0}$, $\sum_{i=1}^{n}\lambda_{i}=1$ such that

$\sum_{i=1}^{n}\lambda_{i}f^{\mathcal{U}}(x^{\prime}_{i})\leq
f^{\mathcal{U}}(x)\text{,}$ (25)

and $f^{\mathcal{U}}(x^{\prime}_{i})\not=f^{\mathcal{U}}(x)$ for all
$i=1,2,\dots,n$.

$\mathcal{U}^{\prime}\subseteq\mathcal{U}$, hence
$f^{\mathcal{U}^{\prime}}(x^{\prime}_{i})\leq
f^{\mathcal{U}}(x^{\prime}_{i})$, $i=1,2\dots,n$, see (7). This leads to

$\displaystyle\sum_{i=1}^{n}\lambda_{i}f^{\mathcal{U}^{\prime}}(x^{\prime}_{i})\stackrel{{\scriptstyle\eqref{eq:U'relaxation}}}{{\leq}}\sum_{i=1}^{n}\lambda_{i}f^{\mathcal{U}}(x^{\prime}_{i})\stackrel{{\scriptstyle\eqref{eq:pb-
proof11}}}{{\leq}}f^{\mathcal{U}}(x)\stackrel{{\scriptstyle\eqref{eq:WCincluded}}}{{=}}f^{\mathcal{U}^{\prime}}(x).$
(26)

Hence, extreme supported efficiency of $x$ for $P(\mathcal{U}^{\prime})$ is
contradicted or

$f^{\mathcal{U}^{\prime}}(x^{\prime}_{i})=f^{\mathcal{U}^{\prime}}(x)\textup{
for at least one }i=1,2,\dots,n$ (27)

must hold. Assume that (27) holds. Then

$f^{\mathcal{U}}(x)\stackrel{{\scriptstyle\eqref{eq:WCincluded}}}{{=}}f^{\mathcal{U}^{\prime}}(x)\stackrel{{\scriptstyle\eqref{eq:pb-
proof13}}}{{=}}f^{\mathcal{U}^{\prime}}(x_{i}^{\prime})\stackrel{{\scriptstyle\eqref{eq:U'relaxation}}}{{\leq}}f^{\mathcal{U}}(x_{i}^{\prime})$

follows. Since $x_{i}^{\prime}$ is efficient for $P(\mathcal{U})$, equality
holds. Hence, $f^{\mathcal{U}}(x^{\prime}_{i})\not=f^{\mathcal{U}}(x)$ for all
$i=1,2,\dots,n$ is contradicted.

  2. (ii)

Let $x$ be extreme supported efficient for $P(\mathcal{U})$. Assume to the
contrary that $x\in\mathcal{X}$ is not extreme supported efficient for
$P(\mathcal{U}^{\prime})$. Then Corollary 13 can be applied to the problem
$P(\mathcal{U}^{\prime})$ with
$\mathcal{Y}=f^{\mathcal{U}^{\prime}}(\mathcal{X})$ and there exists a
nontrivial convex combination
$x^{\prime}_{1},\dots,x^{\prime}_{n}\in\mathcal{R}^{\prime}_{\textup{ESE}}$,
and $\lambda\in\mathbb{R}_{\geq 0}$, $\sum_{i=1}^{n}\lambda_{i}=1$ such that

$\sum_{i=1}^{n}\lambda_{i}f^{\mathcal{U}^{\prime}}(x^{\prime}_{i})\leq
f^{\mathcal{U}^{\prime}}(x)$ (28)

and $f^{\mathcal{U}^{\prime}}(x^{\prime}_{i})\not=f^{\mathcal{U}^{\prime}}(x)$
for all $i=1,2,\dots,n$.

Note that since $x^{\prime}_{i}\in\mathcal{R}^{\prime}_{\textup{ESE}}$,
$i=1,2,\dots,n$, they satisfy (wc). Together with
$\mathcal{U}^{\prime}\subseteq\mathcal{U}$ we receive

$\sum_{i=1}^{n}\lambda_{i}f^{\mathcal{U}}(x^{\prime}_{i})\stackrel{{\scriptstyle\eqref{eq:WCincluded}}}{{=}}\sum_{i=1}^{n}\lambda_{i}f^{\mathcal{U}^{\prime}}(x^{\prime}_{i})\stackrel{{\scriptstyle\eqref{eq:pb-
proof14}}}{{\leq}}f^{\mathcal{U}^{\prime}}(x)\stackrel{{\scriptstyle\eqref{eq:U'relaxation}}}{{\leq}}f^{\mathcal{U}}(x)\text{.}$
(29)

This contradicts the assumption of $x$ being extreme supported efficient for
$P(\mathcal{U})$ or

$f^{\mathcal{U}}(x^{\prime}_{i})=f^{\mathcal{U}}(x)\textup{ for at least one
}i=1,2,\dots,n$ (30)

must hold. Assume (30) holds.

Then

$f^{\mathcal{U}^{\prime}}(x)\stackrel{{\scriptstyle\eqref{eq:U'relaxation}}}{{\leq}}f^{\mathcal{U}}(x)\stackrel{{\scriptstyle\eqref{eq:pb-
proof16}}}{{=}}f^{\mathcal{U}}(x_{i}^{\prime})\stackrel{{\scriptstyle\eqref{eq:WCincluded}}}{{=}}f^{\mathcal{U}^{\prime}}(x_{i}^{\prime})$

follows. Since $x_{i}^{\prime}$ is efficient for $P(\mathcal{U}^{\prime})$,
equality holds. Hence,
$f^{\mathcal{U}^{\prime}}(x^{\prime}_{i})\not=f^{\mathcal{U}^{\prime}}(x)$ for
all $i=1,2,\dots,n$ is contradicted.

  3. (iii)

Let $\mathcal{R}_{\text{ESE}}\subset\mathcal{X}$ be a representative set of
extreme supported efficient solutions for $P(\mathcal{U})$. Analogously to the
proof of Theorem 11 (iii) we show that
$f^{\mathcal{U}}(\mathcal{R}_{\text{ESE}}^{\prime})=f^{\mathcal{U}}(\mathcal{R}_{\text{ESE}})$.
$\subset$: Let $y^{\prime}\in
f^{\mathcal{U}}(\mathcal{R}_{\text{ESE}}^{\prime})$. Then
$y^{\prime}=f^{\mathcal{U}}(x^{\prime})$ for some
$x^{\prime}\in\mathcal{R}_{\text{ESE}}^{\prime}$. According to (i),
$x^{\prime}$ is extreme supported efficient for $P(\mathcal{U})$, hence
$y^{\prime}\in f^{\mathcal{U}}(\mathcal{R}_{\text{ESE}})$.
$\supset$: Let $y\in f^{\mathcal{U}}(\mathcal{R}_{\text{ESE}})$. Then
$y=f^{\mathcal{U}}(x)$ for some $x$ that is extreme supported efficient for
$P(\mathcal{U})$. According to (ii), $x$ is also extreme supported efficient
for $P(\mathcal{U}^{\prime})$. Hence,
$x^{\prime}\in\mathcal{R}^{\prime}_{\text{ESE}}$ exists such that
$f^{\mathcal{U}^{\prime}}(x)=f^{\mathcal{U}^{\prime}}(x^{\prime})$. This leads
to

$y=f^{\mathcal{U}}(x)\stackrel{{\scriptstyle\eqref{eq:U'relaxation}}}{{\geq}}f^{\mathcal{U}^{\prime}}(x)=f^{\mathcal{U}^{\prime}}(x^{\prime})\stackrel{{\scriptstyle\eqref{eq:WCincluded}}}{{=}}f^{\mathcal{U}}(x^{\prime})\textup{.}$

Since by assumption $y$ is extreme supported nondominated for
$P(\mathcal{U})$, equality must hold true. Thus,
$y=f^{\mathcal{U}}(x^{\prime})$ for
$x^{\prime}\in\mathcal{R}_{\text{ESE}}^{\prime}$ and, consequently, $y\in
f^{\mathcal{U}}(\mathcal{R}_{\text{ESE}}^{\prime})$.

∎

We can now formulate the multiobjective generalization of optimization-
pessimization.

#### Adaption of optimization-pessimization.

In order to deal with the multiobjective setting algorithmically, we modify
optimization-pessimization for multiobjective problems as it is described in
the following (see also Figure 2):

Optimization: Determine representative set of extreme supported efficient
solutions $X^{\ast}$ of $P(\mathcal{U}^{\prime})$ Pessimization: For all $x\in
X^{\ast}$, $i=1,2,\dots,p$: Determine worst-case scenario
$\xi^{\ast}\in\operatorname*{arg\,max}_{\xi\in\mathcal{U}}f_{i}(x^{\ast},\xi)$
Add scenarios to $\mathcal{U}^{\prime}$ Figure 2: Optimization-pessimization
for robust multiobjective optimization problems

When solving the _optimization problem_ $P(\mathcal{U}^{\prime})$ we do not
only determine one optimal solution, but a representative set $X^{\prime\ast}$
of extreme supported efficient solutions. In the subsequent _pessimization
step_ we consider _all_ solutions $x\in X^{\prime\ast}$. For each of them we
determine not just one worst-case scenario, but a worst-case scenario for each
of the $p$ objective functions independently. All of these
$p\cdot|X^{\prime\ast}|$ worst-case scenarios are then added to the
uncertainty set.

Algorithm 4.2 describes the exact procedure and the following lemma shows its
correctness.

0: Multi-objective robust optimization problem $P(\mathcal{U})$ as in (6).

0: Finite initial set $\mathcal{U}^{(0)}\subseteq\mathcal{U}$.

0: Either $\mathcal{U}$ finite or $\mathcal{U}$ a polytope and
$f_{i}(x,\cdot)$, $i=1,2,\dots,p$ continuous and quasi-convex.

0: (dom), (ideal) hold for $P(\mathcal{U})$ and for $P(\mathcal{U}^{\prime})$
for any finite subset $\mathcal{U}^{\prime}\subseteq\mathcal{U}$.

Set $k\coloneqq 0$.

repeat

Set $\mathcal{U}^{(k+1)}\coloneqq\mathcal{U}^{(k)}$.

Determine representative set for extreme supported efficient solutions
$X^{(k)\ast}$ and representative set for extreme supported nondominated points
$Y^{(k)\ast}$ of $P(\mathcal{U}^{(k)})$.

for all $x^{\ast}\in X^{(k)\ast}$ do

for all $i=1,2,\dots,p$ do

Determine
$\xi^{\ast}\in\operatorname*{arg\,max}_{\mathcal{U}}f_{i}(x^{\ast},\xi)$.

Add $\xi^{\ast}$ to $\mathcal{U}^{(k+1)}$.

end for

end for

$k\coloneqq k+1$

until $f^{\mathcal{U}}(x^{\ast})=f^{\mathcal{U}^{(k-1)}}(x^{\ast})$ for all
$x^{\ast}\in X^{(k-1)\ast}$.

return $X^{(k-1)\ast}$: representative set of extreme supported efficient
solutions of $P(\mathcal{U})$.

return $Y^{(k-1)\ast}$: set of extreme supported nondominated points of
$P(\mathcal{U})$.

return $\mathcal{U}^{\textup{FINAL}}\coloneqq\mathcal{U}^{k}$: set of worst-
case scenarios.

Algorithm 4.2 Optimization-pessimization for multi-objective robust
optimization

Optimization

Pessimization

######  Lemma 15.

Let (dom), (ideal) hold for $P(\mathcal{U})$ and for $P(\mathcal{U}^{\prime})$
for any finite subset $\mathcal{U}^{\prime}\subseteq\mathcal{U}$.

  1. (i)

Let $\mathcal{U}$ be finite. Then Algorithm 4.2 returns a representative set
of extreme supported efficient solutions to $P(\mathcal{U})$ in at most
$|\mathcal{U}|$ iterations.

  2. (ii)

Let $\mathcal{U}$ be a polytope or finite and
$f_{i}(x,\cdot)\colon\operatorname*{conv}(\mathcal{U})\to\mathbb{R}$,
$i=1,2,\dots,p$, be continuous and quasi-convex. Then Algorithm 4.2 returns a
representative set of extreme supported efficient solutions to (6) in at most
$k$ iterations where $k$ is the number of extreme points of $\mathcal{U}$, if
we choose an algorithm for the pessimization problem which always finds an
extreme point of $\mathcal{U}$.

###### Proof.

Algorithm 4.2 determines a representative set of extreme supported efficient
solutions to $\mathcal{U}^{(k-1)}$ in step $k$. It stops if

$f^{\mathcal{U}}(x^{\ast})=f^{\mathcal{U}^{(k-1)}}(x^{\ast})$ (31)

for all $x^{\ast}\in X^{(k-1)\ast}$.

Hence, $\mathcal{R}_{\textup{ESN}}=X^{(k-1)\ast}$ is a representative set of
extreme supported efficient solutions to $P(\mathcal{U}^{\prime})$ for
$\mathcal{U}^{(k-1)}$ whose elements satisfy (wc). Furthermore,
$\mathcal{Y}=f^{\mathcal{U}}(x)$ is compact, since it is the image of a
compact set under the function $\max_{\xi\in\mathcal{U}^{\prime}}f(x,\xi)$
that is continuous since $\mathcal{U}^{\prime}$ is finite. We can thus apply
Theorem 14 for $\mathcal{U}^{\prime}=\mathcal{U}^{(k-1)}\subseteq\mathcal{U}$
and, after termination, $X^{(k-1)\ast}$ is a representative set of extreme
supported efficient solutions to $P(\mathcal{U})$.

We now show the bounds on the number of iterations.

  1. ad (i)

In every iteration, either at least one new worst-case scenario is added or
(31) holds and the procedure stops. Since $\mathcal{U}$ is finite, the latter
happens after at most $|\mathcal{U}|$ iterations.

  2. ad (ii)

Consider the pessimization problem $\textup{Pess}(x^{k})$: here we maximize a
continuous function over a compact set $\mathcal{U}$, i.e., a maximum always
exists. Since $f(x,\cdot)$ is quasi-convex, the maximum is always attained at
an extreme point of $\mathcal{U}$. If we choose an algorithm that returns an
extreme point for such optimization problems, we add a new extreme point in
each iteration until (18) holds as in part (i).

∎

Algorithm 4.2 provides a method to solve problem (BRO) under the stated
assumptions. However, this is still challenging since in each iteration a
representative set for all extreme supported efficient solutions to
$P(\mathcal{U}^{\prime})$ for some $\mathcal{U}^{\prime}\subset\mathcal{U}$
needs to be found. In Section 5.2 we employ dichotomic search for this
purpose.

##  5 Algorithms for robust biobjective optimization

In Sections 3.2 and 4.2 algorithms known from (deterministic) biobjective and
(single-objective) robust optimization, respectively, have been generalized.
However, in each iteration of the proposed dichotomic search method (Algorithm
3.1, Lemma 7) a robust problem has to be solved and, similarly, in each
iteration of the proposed optimization-pessimization method (Algorithm 4.2,
Lemma 15) a multiobjective problem has to be solved. So far, we treated these
steps as if they were performed by an oracle.

In this section we put these steps into concrete terms and, in doing so,
present algorithms designed to solve uncertain biobjective problems, more
specifically the problem (BRO) as defined in Section 2. Throughout this
section we always assume that the assumptions of (BRO), i.e., (BRO-1),
(BRO-2), and (BRO-3) (see page BRO), hold.

Specifically, three different approaches to find minmax robust solutions for
$P(\mathcal{U})$ are presented:

  * •

A robust optimizer’s approach (ROA): We view the problem (BRO) primarily as a
_robust_ optimization problem – just with the added difficulty that it has two
objective functions – and, consequently, apply a method from robust
optimization, namely the generalized optimization-pessimization method
(Algorithm 4.2), to the problem $\textup{BRO}(\mathcal{U})$. The subproblem to
be solved in each iteration is a _biobjective_ problem
$\textup{BRO}(\mathcal{U}^{\prime})$ with a small uncertainty set
$\mathcal{U}^{\prime}\subseteq\mathcal{U}$ which we tackle by the generalized
version of dichotomic search (Algorithm 3.1). This algorithm is presented in
Section 5.1.

  * •

A multiobjective optimizer’s approach (MOA): We view the problem (BRO)
primarily as a _biobjective_ optimization problem – with the added difficulty
that we aim to find a _robust_ solution and the objective functions, thus,
contain a maximum – and, consequently, apply a method from biobjective
optimization, namely the generalized version of dichotomic search (Algorithm
3.1) to the problem $\textup{BRO}(\mathcal{U})$. The subproblem to be solved
in each iteration is a single-objective but _uncertain_ problem
$P(\mathcal{U},\lambda)$ which we tackle by the optimization-pessimization
method (Algorithm 4.1). This algorithm is presented in Section 5.2.

  * •

A multiobjective optimizer’s approach for bilinear problems using dualization
(DA): As in the aforementioned approach, we take the multiobjective
optimizer’s perspective and apply the generalized version of dichotomic search
(Algorithm 3.1) to the problem $\textup{BRO}(\mathcal{U})$. The subproblem
$P(\mathcal{U},\lambda)$ is directly solved through a reformulation in each
iteration. This algorithm is presented in Section 5.3.

Algorithms 5.1, 5.2, and 5.3 each determine all extreme supported nondominated
points and a corresponding representative set of extreme supported efficient
solution for $\textup{BRO}(\mathcal{U})$. The following lemma shows that these
sets can be used to determine _all_ nondominated points and a representative
set for all efficient solutions of $\textup{BRO}(\mathcal{U})$.

######  Lemma 16.

Let $\textup{BRO}(\mathcal{U})$ be given and let $\mathcal{X}$ be a polytope.
Further, let $\mathcal{Y}_{\textup{ESN}}$,
$|\mathcal{Y}_{\textup{ESN}}|<\infty$, be its set of nondominated extreme
supported points and $\mathcal{X}_{\textup{ESE}}$ a representative set of
extreme supported efficient solutions. Let
$\mathcal{X}_{\textup{ESE}}=\left\\{x^{(1)},x^{(2)},\dots,x^{(n)}\right\\}$,
$\mathcal{Y}_{\textup{ESN}}=\left\\{y^{(1)},y^{(2)},\dots,y^{(n)}\right\\}$,
$y^{(1)}_{1}<y^{(2)}_{1}<\dots<y^{(n)}_{1}$ and $f(x^{(i)})=y^{(i)}$ for
$i=1,2,\dots,n$ . Then

$\displaystyle\mathcal{X}^{\ast}$
$\displaystyle\coloneqq\bigcup_{i=1,2,\dots,n-1}\left\\{\lambda
x^{(i)}+(1-\lambda)x^{(i+1)}\colon\lambda\in(0,1)\right\\}$ is a
representative set (of efficient solutions) and
$\displaystyle\mathcal{Y}^{\ast}$
$\displaystyle\coloneqq\bigcup_{i=1,2,\dots,n-1}\left\\{\lambda
y^{(i)}+(1-\lambda)y^{(i+1)}\colon\lambda\in(0,1)\right\\}$

is the set of nondominated points of $\textup{BRO}(\mathcal{U})$.

###### Proof.

Let $\bar{x}\in\mathcal{X}^{\ast}$. Then $\bar{x}=\lambda
x^{(i)}+(1-\lambda)x^{(i+1)}$ for some $i=1,2,\dots,n-1$, $\lambda\in(0,1)$,
and

$\displaystyle\bar{y}\coloneqq f^{\mathcal{U}}(\bar{x})$
$\displaystyle=\max_{\xi\in\mathcal{U}}f(\lambda
x^{(i)}+(1-\lambda)x^{(i+1)},\xi)$
$\displaystyle=\max_{\xi\in\mathcal{U}}\left\\{\lambda
f(x^{(i)},\xi)+(1-\lambda)f(x^{(i+1)},\xi)\right\\}$
$\displaystyle\leq\max_{\xi\in\mathcal{U}}\lambda
f(x^{(i)},\xi)+\max_{\xi\in\mathcal{U}}(1-\lambda)f(x^{(i+1)},\xi)$
$\displaystyle=\lambda
f^{\mathcal{U}}(x^{(i)})+(1-\lambda)f^{\mathcal{U}}(x^{(i+1)})$
$\displaystyle=\lambda y^{(i)}+(1-\lambda)y^{(i+1)}.$

However, since by Lemma 12 we have
$\mathcal{Y}\subseteq\operatorname*{conv}(\mathcal{Y}_{\textup{ESN}})+\mathbb{R}_{\geq}^{2}$
and since $\\{\lambda y^{(i)}+(1-\lambda)y^{(i+1)}\\}$ is a facet of
$\operatorname*{conv}(\mathcal{Y}_{\textup{ESN}})$, there is no
$y\in\mathcal{Y}$ with $y\preceq\lambda y^{(i)}+(1-\lambda)y^{(i+1)}$. Thus,
we have $\bar{y}=\lambda y^{(i)}+(1-\lambda)y^{(i+1)}$ and $\bar{y}$ is
nondominated. This shows that the solutions in $\mathcal{X}^{\ast}$ are
efficient and the points in $\mathcal{Y}^{\ast}$ are nondominated.

It remains to be shown that all nondominated points are included in
$\mathcal{Y}^{\ast}\cup\mathcal{Y}_{\textup{ESN}}$. This, however, follows
directly from the fact that, by Lemma 12
$\mathcal{Y}\subseteq\operatorname*{conv}(\mathcal{Y}_{\textup{ESN}})+\mathbb{R}_{g}eq^{2}$.
∎

###  5.1 A robust optimizer’s approach

The robust optimizer’s approach is based on the idea of applying the
generalization of optimization-pessimization (Algorithm 4.2). In the $k$-th
iteration a representative set of extreme supported efficient solutions to
$P(\mathcal{U}^{(k)})$ has to be determined. For this purpose in Algorithm 5.1
we employ dichotomic search for robust biobjective linear mixed-integer
optimization problems as shown possible in Section 3.2.

0: Biobjective mixed-integer linear robust optimization problem (BRO).

0: Finite initial set $\mathcal{U}^{(0)}\subseteq\mathcal{U}$.

0: Feasible set $\mathcal{X}$ is a polyhedron intersected with
$\mathbb{R}^{n-k}\times\mathbb{Z}^{k}$ for some $k\in\\{0,\ldots,n\\}$.

0: $\mathcal{U}$ finite or $\mathcal{U}$ a polytope and $f_{i}(x,\cdot)$,
$i=1,2,\dots,p$ continuous and quasi-convex.

0: (dom), (ideal) hold for $P(\mathcal{U})$ and for $P(\mathcal{U}^{\prime})$
for any finite subset $\mathcal{U}^{\prime}\subseteq\mathcal{U}$.

Set $k\coloneqq 0$.

repeat

Set $\mathcal{U}^{(k+1)}\coloneqq\mathcal{U}^{(k)}$.

Call dichotomic search (Algorithm 3.1) for $\textup{BRO}(\mathcal{U}^{k})$ to
determine representative set for extreme supported efficient solutions
$X^{(k)\ast}$ and representative set for extreme supported nondominated points
$Y^{(k)\ast}$.

for all $x^{\ast}\in X^{\ast}$ do

for all $i=1,2$ do

Determine one
$\xi^{\ast}\in\operatorname*{arg\,max}_{\mathcal{U}}f_{i}(x^{\ast},\xi)$.

Add $\xi^{\ast}$ to $\mathcal{U}^{(k+1)}$.

end for

end for

$k\coloneqq k+1$

until $f^{\mathcal{U}}(x^{\ast})=f^{\mathcal{U}^{(k-1)}}(x^{\ast})$ for all
$x^{\ast}\in X^{(k-1)\ast}$.

return $X^{(k-1)\ast}$: representative set of extreme supported efficient
solutions of $P(\mathcal{U})$.

return $Y^{(k-1)\ast}$: set of extreme supported nondominated points of
$P(\mathcal{U})$.

return $\mathcal{U}^{\textup{FINAL}}\coloneqq\mathcal{U}^{k}$: set of worst-
case scenarios.

Algorithm 5.1 Robust optimizer’s approach (ROA)

Optimization

Pessimization

Note that Algorithm 5.1 is just Algorithm 4.2 with the optimization step
performed by dichtomic search (Algorithm 3.1). Consequently, the requirements
correspond to those of Algorithm 4.2 and Algorithm 3.1 as formulated in Lemma
15 and Lemma 7, respectively. This is stated in the following lemma.

######  Lemma 17.

Let $\textup{BRO}(\mathcal{U})$ be given.

  1. (i)

Let $\mathcal{U}$ be finite. Then Algorithm 5.1 returns a representative set
of extreme supported efficient solutions to (BRO) in at most $|\mathcal{U}|$
iterations.

  2. (ii)

Let $\mathcal{U}$ be a polytope or finite and
$f_{i}(x,\cdot)\colon\operatorname*{conv}(\mathcal{U})\to\mathbb{R}$,
$i=1,2,\dots,p$, be continuous and quasi-convex. Then Algorithm 5.1 returns a
representative set of extreme supported efficient solutions to (BRO), in at
most $k$ iterations (where $k$ is the number of extreme points of
$\mathcal{U}$) if we choose an algorithm for the pessimization problem which
always finds an extreme point of $\mathcal{U}$.

###### Proof.

By Corollary 3, $\textup{BRO}(\mathcal{U})$ satisfies (dom) and (ideal).
Algorithm 5.1 is the same as Algorithm 4.2, but for $p=2$ and with dichotomic
search (Algorithm 3.1) specified in the optimization step. Lemma 7 justifies
that dichotomic search works correctly for BRO. Consequently, we may use
dichotomic search in line 4 of Algorithm 4.2. Under (dom) and (ideal) for
$\textup{BRO}(\mathcal{U})$ and $\textup{BRO}(\mathcal{U}^{\prime})$ for all
finite sets $\mathcal{U}^{\prime}\subseteq\mathcal{U}$ Lemma 15 gives us
correctness of Algorithm 4.2 and hence also of Algorithm 5.1. ∎

Note that if Algorithm 5.1 is stopped before the stopping criterion in line 12
is met, the set $\\{f^{\mathcal{U}}(k-1)(x):x\in\mathcal{X}^{(k-1)\ast}\\}$
and $\\{f^{\mathcal{U}}(x):x\in X^{(k-1)\ast}\\}$ provide lower and upper
bounds with respect to the upper setless order, as we have shown in Lemma 9.
Using convex combinations of subsequent points in these sets like we did in
Lemma 16 for $Y^{\ast}$, we obtain bounds on the region in which the Pareto
frontier $Y^{\ast}$ will lie. In this sense, Algorithm 5.1 can be used as an
approximation algorithm for (BRO).

###  5.2 A multiobjective optimizer’s approach

The multiobjective optimizer’s approach is based on the idea of applying
dichotomic search (Algorithm 3.1) as introduced in Section 3.1 directly to
$P(\mathcal{U})$. In each iteration of dichotomic search, we have to solve the
scalarized weighted-sum problem

$\displaystyle P(\mathcal{U},\lambda)$
$\displaystyle\min_{x\in\mathcal{X}}\lambda_{1}f_{1}^{\mathcal{U}}(x)+\lambda_{2}f_{2}^{\mathcal{U}}(x)+\dots+\lambda_{p}f_{p}^{\mathcal{U}}(x)$
(32)

for $p=2$ and given weights $\lambda\in\mathbb{R}_{\succeq 0}$. In order to do
this, we utilize optimization-pessimization for single-objective robust
optimization as reviewed in Section 4.1: We solve a sequence of problems
$P(\mathcal{U}^{0},\lambda),P(\mathcal{U}^{1},\lambda),\dots,P(\mathcal{U}^{k},\lambda)$
until it is guaranteed that $P(\mathcal{U}^{k},\lambda)$ and
$P(\mathcal{U},\lambda)$ share a representative set of extreme supported
minmax robust efficient solutions. As in Section 4 we exploit the fact, that
for finite sets $\mathcal{U}^{\prime}$ a problem
$P(\mathcal{U}^{\prime},\lambda)$ is easier to solve than
$P(\mathcal{U},\lambda)$ as it can be written as a problem with finitely many
constraints. For solving the scalarization we assumed an oracle in Algorithm
3.1. Now we want to be more specific. We first reformulate problem (32) such
that we can apply optimization-pessimization (see Section 4.1) for its
solution. This is done in the next lemma.

######  Lemma 18.

Let $\lambda\in\mathbb{R}^{2}_{\succeq 0}$ be fixed. Then
$P(\mathcal{U},\lambda)$ can be transformed to

$\displaystyle\bar{P}(\mathcal{U},\lambda)$
$\displaystyle\min_{x\in\mathcal{X}}\sup_{\bar{\xi}\in\bar{\mathcal{U}}}\bar{f}_{\lambda}(x,\bar{\xi})\textup{,}$
(33)

i.e., a problem of type $\textup{P}^{\textup{single}}$ as introduced in (2),
for $\bar{\mathcal{U}}\coloneqq\bigtimes_{i=1,2,\dots,p}\mathcal{U}$,
$\bar{\xi}\coloneqq(\xi_{1},\xi_{2},\dots,\xi_{p})$ and
$\bar{f}_{\lambda}(x,\bar{\xi})\coloneqq\sum_{i=1}^{p}\lambda_{i}f_{i}(x,\xi_{i})$.

###### Proof.

We reformulate (32) as follows:

$\displaystyle\min_{x\in\mathcal{X}}\left\\{\lambda_{1}f_{1}^{\mathcal{U}}(x)+\lambda_{2}f_{2}^{\mathcal{U}}(x)+\dots+\lambda_{p}f_{p}^{\mathcal{U}}(x)\right\\}$
$\displaystyle=\min_{x\in\mathcal{X}}\left\\{\sum_{i=1}^{p}\lambda_{i}\sup_{\xi\in\mathcal{U}}f_{i}(x,\xi)\right\\}$
$\displaystyle=\min_{x\in\mathcal{X}}\sup_{(\xi_{1},\xi_{2},\dots,\xi_{p})\in\mathcal{U}^{p}}\left\\{\sum_{i=1}^{p}\lambda_{i}f_{i}(x,\xi_{i})\right\\}$
$\displaystyle=\min_{x\in\mathcal{X}}\sup_{\bar{\xi}\in\bar{\mathcal{U}}}\bar{f}_{\lambda}(x,\bar{\xi})\text{.}$

∎

Lemma 18 shows that $P(\mathcal{U},\lambda)$ can be solved by solving a
single-objective robust optimization problem
$\bar{P}(\bar{\mathcal{U}},\lambda)$, i.e., of type $P^{\textup{single}}$, as
has been introduced in (2).

Algorithm 5.2 describes a _basic version_ of the multiobjective optimizer’s
approach. Its correctness is shown in the following lemma.

0: Biobjective mixed-integer linear robust optimization problem (BRO).

0: Finite initial set $\mathcal{U}^{(0)}\subseteq\mathcal{U}$.

0: Feasible set $\mathcal{X}$ is a polyhedron intersected with
$\mathbb{R}^{n-k}\times\mathbb{Z}^{k}$ for some $k\in\\{0,\ldots,n\\}$.

0: $\mathcal{U}$ finite or $\mathcal{U}$ a polytope and $f_{i}(x,\cdot)$,
$i=1,2,\dots,p$ continuous and quasi-convex.

0: (dom), (ideal) hold for $P(\mathcal{U})$ and for $P(\mathcal{U}^{\prime})$
for any finite subset $\mathcal{U}^{\prime}\subseteq\mathcal{U}$.

Initialize $\mathcal{L}\coloneqq\emptyset$ {$\mathcal{L}$ will contain list of
tuple images $(y^{l},y^{r})$ satisfying
$y^{l}_{1}<y^{r}_{1},y^{l}_{2}>y^{r}_{2}$}

Call optimization-pessimization (Algorithm 4.1) on
$\min_{x\in\mathcal{X}}f^{\mathcal{U}}_{1}(x)$ with initial set
$\mathcal{U}^{(0)}$ to determine $\varepsilon_{1}$,
$\mathcal{U}^{\text{FINAL}}$, and $\xi^{\textup{WC}}$.

Call optimization-pessimization (Algorithm 4.1) on
$\min_{x\in\mathcal{X}}\\{f^{\mathcal{U}}_{2}(x)\colon\max_{\xi\in\mathcal{U}}f_{1}(x,\xi)\leq\varepsilon_{1}\\}$
with initial set $\mathcal{U}^{\text{FINAL}}$ to determine optimal solution
$x^{L}$.

Set $y^{L}\coloneqq f^{\mathcal{U}}(x^{L})$.

Call optimization-pessimization (Algorithm 4.1) on
$\min_{x\in\mathcal{X}}f^{\mathcal{U}}_{2}(x)$ with initial set
$\mathcal{U}^{(0)}$ to determine $\varepsilon_{2}$,
$\mathcal{U}^{\text{FINAL}}$, and $\xi^{\textup{WC}}$.

Call optimization-pessimization (Algorithm 4.1) on
$\min_{x\in\mathcal{X}}\\{f^{\mathcal{U}}_{1}(x)\colon\max_{\xi\in\mathcal{U}}f_{2}(x,\xi)\leq\varepsilon_{2}\\}$
with initial set $\mathcal{U}^{\text{FINAL}}$ to determine optimal solution
$x^{R}$..

Set $y^{R}\coloneqq f^{\mathcal{U}}(x^{R})$.

if $y^{L}=y^{R}$ then

STOP. Only one nondominated image found.

return $Y^{\ast}=\\{y^{L}\\},X^{\ast}=\\{x^{L}\\}$.

else

$Y^{\ast}=\\{y^{L},y^{R}\\},X^{\ast}=\\{x^{L},x^{R}\\},\mathcal{L}=\\{(y^{L},y^{R})\\}$.

end if

while $L\not=\emptyset$ do

Remove element $(y^{l},y^{r})$ from $\mathcal{L}$.

Compute $\lambda\coloneqq(y^{l}_{2}-y^{r}_{2},y^{r}_{1}-y^{l}_{1})$.

Call optimization-pessimization (Algorithm 4.1) on
$\min_{x\in\mathcal{X}}\bar{f_{\lambda}}(x)$ with initial set
$\mathcal{U}^{(0)}$ to determine optimal solution $x^{\ast}$.

Set $y^{\ast}\coloneqq\bar{f_{\lambda}}(x^{\ast})$.

if $\lambda^{T}y^{\ast}\not=\lambda^{T}y^{l}$ then

Add $y^{\ast}$ to $Y^{\ast}$, add $x^{\ast}$ to $X^{\ast}$.

Add $(y^{l},y^{\ast}),(y^{\ast},y^{r})$ to $\mathcal{L}$

end if

end while

return $X^{\ast}$: representative set of extreme supported efficient solutions
of $P(\mathcal{U})$.

return $Y^{\ast}$: set of extreme supported nondominated points of
$P(\mathcal{U})$.

Algorithm 5.2 Multiobjective optimizer’s approach (MOA)

Determine lexicographic solutions

Solve weighted-sum problem $\bar{P}(\mathcal{U},\lambda)$

######  Lemma 19.

Let $\textup{BRO}(\mathcal{U})$ be given. Then Algorithm 5.2 returns a
representative set of extreme supported efficient solutions to (BRO) after a
finite number of iterations.

###### Proof.

Algorithm 5.2 is dichotomic search (Algorithm 3.1), where we specified the
algorithm for steps 2-3, 5-6, 17-18, namely by solving
$\textup{BRO}(\mathcal{U},\lambda)$ by optimization-pessimization (Algorithm
4.1) in each iteration. Since $\textup{BRO}(\mathcal{U})$ meets the
requirements of Lemma 6 (in case $\mathcal{U}$ is finite) or Lemma 7 (in case
$\mathcal{U}$ is a polytope), Algorithm 3.1 returns a representative set of
extreme supported efficient solutions and a set of extreme supported
nondominated solutions after finitely many iterations.

It remains to show that lines 2-3, 5-6 and 17-18 in Algorithm 5.2 are correct
specifications of the same lines of Algorithm 3.1.

For lines 2 and 5 this is straightforward as the problems

$\min_{x\in\mathcal{X}}f_{i}^{\mathcal{U}}(x),$ (34)

$i=1,2$, are single-objective robust optimization problems. Since
$\mathcal{U}$ is a polytope or finite and
$f_{i}(x,\cdot)\colon\mathcal{U}\to\mathbb{R}$, $i=1,2$, are continuous and
quasi-convex, Lemma 8 can be applied and optimization-pessimization (Algorithm
4.1) solves (34).

The problems in lines 3 and 6 are also of type (34) only with one additional
constraint, i.e., with feasible set is

$\mathcal{X}^{\prime}_{j}\coloneqq\\{x\in\mathcal{X}:\max_{\xi\in\mathcal{U}}f_{j}(x,\xi)\leq\varepsilon_{j}\\},j=2,1.$

In lines 17-18 of Algorithm 3.1 the problem $P(\mathcal{U},\lambda)$ is to be
solved for some $\lambda\in\mathbb{R}_{\succeq 0}$. By Lemma 18 this can be
done by solving $\bar{P}(\mathcal{U},\lambda)$ instead which is done in lines
17-18 of Algorithm 5.2. Since continuity and quasi-convexity of $\bar{f}$ are
inherited from continuity and quasi-convexity of $f_{1}$ and $f_{2}$, Lemma 15
can be applied and optimization-pessimization returns a robust solution to
$P(\mathcal{U},\lambda)$. ∎

#### Warm start modifications.

In the basic version of Algorithm 5.2 the cutting plane method is initialized
with $\mathcal{U}^{\text{(0)}}$ in lines 2,5 and 17. A possible modification
of Algorithm 5.2 is to start the cutting plane method with a larger set
$\mathcal{U}^{\prime}$ that includes some additional scenarios that have been
generated in previous iterations but that is still guaranteed to be finite.
This way, previously generated cutting planes are not forgotten. Specifically,
we propose two modifications:

  * •

Variant 1 (MOA-ws1): We initialize optimization-pessimization with all
previously generated scenarios. To this end, we modify lines 5 and 17 such
that the cutting plane method is initialized with
$\mathcal{U}^{\text{FINAL}}$. This way, $\mathcal{U}^{\text{FINAL}}$ grows
monotonically.

  * •

Variant 2 (MOA-ws2): We initialize the cutting plane method with those
scenarios that turned out to be worst-case scenarios for a previously found
solution optimal $x$. After lines 2-3, 5-6, and 17-18 the worst-case scenarios
$\xi^{\text{WC}}$ for $x^{L}$, $x^{R}$, and $x^{\ast}$, respectively, are
added to $\mathcal{U}^{\text{(0)}}$ and the set grows monotonically, but is
much smaller than the set in Variant 1.

As Lemmas 18 and 19 above only assume finiteness of the initial uncertainty
set their validity is not affected by these modifications.

###  5.3 A multiobjective optimizer’s approach for bilinear problems

In this section, we confine ourselves to a special class of problems:
biobjective mixed-integer linear robust optimization problems (BRO) which
satisfy not only (BRO-1), (BRO-2), and (BRO-3) as before, but also the
following additional properties:

  * •

the uncertainty set $\mathcal{U}$ is as a polytope
$\mathcal{U}=\\{\xi\in\mathbb{R}^{m}\colon C\xi\leq d\\}$ for a matrix
$C\in\mathbb{R}^{m^{\prime}\times m}$ and a vector
$d\in\mathbb{R}^{m^{\prime}}$, and

  * •

the functions $f_{1},f_{2}\colon\mathcal{X}\times\mathcal{U}\to\mathbb{R}$ are
not only linear in $x$ for every fixed $\xi\in\mathcal{U}$ as required in
(BRO-3), but also linear in $\xi$ for each $x$, i.e., they are _bilinear_
functions.

The following lemma shows that under these assumptions a biobjective mixed-
integer linear _minmax_ optimization problem can be reformulated as a
biobjective mixed-integer linear _minimization_ problem.

######  Lemma 20.

We consider the uncertain problem

$\displaystyle P(\mathcal{U})$
$\displaystyle\min_{x\in\mathcal{X}}f^{\mathcal{U}}(x)\textup{.}$ (6
revisited)

Let the uncertainty set be a non-empty polytope
$\mathcal{U}=\\{\xi\in\mathbb{R}^{m}\colon C\xi\leq d\\}$, with
$C\in\mathbb{R}^{m^{\prime}\times m}$, $d\in\mathbb{R}^{m^{\prime}}$, and let
the functions $f_{i}(x,\xi)$, $i=1,2,\dots,p$, be linear in $\xi$ for each
$x$, i.e.,

$f_{i}(x,\xi)\coloneqq\left[\hat{c_{i}}(x)\right]^{t}\xi$

for functions $\hat{c_{i}}\colon\mathcal{X}\to\mathbb{R}^{m}$,
$i=1,2,\dots,p$.

Let $\lambda\in\mathbb{R}_{\succeq}^{p}$. Then a solution
$x^{\ast}\in\mathcal{X}$ is optimal for the scalarized problem

$\displaystyle P(\mathcal{U},\lambda)$
$\displaystyle\min_{x\in\mathcal{X}}\lambda^{t}f^{\mathcal{U}}(x)$ (32
revisited)

if and only if there exist
$\pi^{(1)\ast},\dots,\pi^{(p)\ast}\in\mathbb{R}^{m^{\prime}}$ such that
$(x^{\ast},\pi^{(1)\ast},\dots,\pi^{(p)\ast})$ is optimal for

$\displaystyle D(\mathcal{U},\lambda)$
$\displaystyle\min_{x\in\mathcal{X},\pi^{(1)},\dots,\pi^{(p)}\in\mathbb{R}^{m^{\prime}}}\left\\{d^{t}\sum_{i=1}^{p}\lambda_{i}\pi^{(i)}\colon
C^{t}\pi^{(i)}=\hat{c_{i}}(x),\pi^{(i)}\geq 0,i=1,2,\dots,p\right\\}$

More precisely, let $x$ be fixed and let $(\pi^{(1)\ast},\dots,\pi^{(p)\ast})$
be an optimal solution to

$\min_{\pi^{(1)},\dots,\pi^{(p)}\in\mathbb{R}^{m^{\prime}}}\left\\{d^{t}\sum_{i=1}^{p}\lambda_{i}\pi^{(i)}\colon
C^{t}\pi^{(i)}=\hat{c_{i}}(x),\pi^{(i)}\geq 0,i=1,2,\dots,p\right\\}$

with optimal objective function value $z$. Then
$z=\lambda^{t}f^{\mathcal{U}}(x)$ and for all $i=1,2,\dots,p$ with
$\lambda_{i}>0$

$\displaystyle
d^{t}\pi^{(i)\ast}=\max_{\xi\in\mathcal{U}}\left[\hat{c_{i}}(x)\right]^{t}\xi\textup{.}$
(35)

###### Proof.

First note that $D(\mathcal{U},\lambda)$ is equivalent to

$\hskip
28.45274pt\min_{x\in\mathcal{X}}\min_{\pi^{(1)},\dots,\pi^{(p)}\in\mathbb{R}^{m^{\prime}}}\left\\{d^{t}\sum_{i=1}^{p}\lambda_{i}\pi^{(i)}\colon
C^{t}\pi^{(i)}=\hat{c_{i}}(x),\pi^{(i)}\geq 0,i=1,2,\dots,p\right\\}$

which can be interpreted as optimization problem

$\displaystyle\bar{D}(\mathcal{U},\lambda)$
$\displaystyle\min_{x\in\mathcal{X}}g_{\lambda}(x)$

with

$g_{\text{$\lambda$}}(x)\coloneqq\min_{\pi^{(1)},\dots,\pi^{(p)}\in\mathbb{R}^{m^{\prime}}}\left\\{d^{t}\sum_{i=1}^{p}\lambda_{i}\pi^{(i)}\colon
C^{t}\pi^{(i)}=\hat{c_{i}}(x),\pi^{(i)}\geq
0,i=1,2,\dots,p\right\\}\textup{.}$

We now need to show that the objective function and the feasible set of
$P(\mathcal{U},\lambda)$ and $\bar{D}(\mathcal{U},\lambda)$ coincide.
Specifically, we show

$\lambda^{t}f^{\mathcal{U}}(x)=g_{\lambda}(x)$

for all $x\in\mathcal{X}$.

We first note that $\mathcal{U}$ is a compact set, hence for any fixed
$x\in\mathcal{X}$ and any $i=1,2,\dots,p$ the linear program

$\max\left\\{\left[\hat{c_{i}}(x)\right]^{t}\xi\colon\xi\in\mathcal{U}\right\\}$

has an optimal solution. Using that $\mathcal{U}=\\{\xi\in\mathbb{R}^{m}\colon
C\xi\leq d\\}$ we hence get from linear programming duality for
$i=1,2,\dots,p$ and fixed $x\in\mathcal{X}$ that

$\displaystyle\max\left\\{\left[\hat{c_{i}}(x)\right]^{t}\xi\colon C\xi\leq
d,\xi\in\mathbb{R}^{m}\right\\}=\min\left\\{d^{t}\pi^{(i)}\colon
C^{t}\pi^{(i)}=\hat{c_{i}}(x),\pi^{(i)}\geq
0,\pi^{(i)}\in\mathbb{R}^{m^{\prime}}\right\\},$ (36)

i.e., for any fixed $x\in\mathcal{X}$ and $i=1,\ldots,p$, an optimal solution
$\pi^{(i)\ast}$ to the right hand side satisfies

$d^{t}\pi^{(i)\ast}=\max_{\xi\in\mathcal{U}}\left[\hat{c_{i}}(x)\right]^{t}\xi$

which shows (35). We can now derive

$\displaystyle\lambda^{t}f^{\mathcal{U}}(x)$
$\displaystyle=\sum_{i=1}^{p}\lambda_{i}\underbrace{\max_{\xi\in\mathbb{R}^{m}}\left\\{\left[\hat{c_{i}}(x)\right]^{t}\xi\colon
C\xi\leq d\right\\}}_{=f_{i}^{\mathcal{U}}(x)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:DualityMinIsMax+}}}{{=}}\sum_{i=1}^{p}\lambda_{i}\min_{\pi^{(i)}\in\mathbb{R}^{m^{\prime}}}\left\\{d^{t}\pi^{(i)}\colon
C^{t}\pi=\hat{c_{i}}(x),\pi^{(i)}\geq 0\right\\}$
$\displaystyle=\min_{\pi^{(1)},\dots,\pi^{(p)}\in\mathbb{R}^{m^{\prime}}}\left\\{d^{t}\sum_{i=1}^{p}\lambda_{i}\pi^{(i)}\colon
C^{t}\pi^{(i)}=\hat{c_{i}}(x),\pi^{(i)}\geq 0\right\\}\text{,}$

where the last step puts the single optimization problems together into a
bigger (still separable) problem. Thus, for any fixed $x$ the objective values
of $P(\mathcal{U},\lambda)$ and $\bar{D}(\mathcal{U},\lambda)$ coincide and
hence $x$ is optimal to $P(\mathcal{U},\lambda)$ if and only if it is optimal
to $\bar{D}(\mathcal{U},\lambda)$. ∎

As in Section 5.2, we apply dichotomic search to $P(\mathcal{U})$ and solve
$P(\mathcal{U},\lambda)$ for different weights
$\lambda\in\mathbb{R}^{p}_{\succeq}$. However, unlike in Section 5.2 we do not
solve $P(\mathcal{U},\lambda)$ with an iterative approach, but adopt the other
approach described by [GYd15]: reformulation of $P(\mathcal{U},\lambda)$. More
specifically, we weaponize Lemma 20 and choose to solve

$\displaystyle D(\mathcal{U},\lambda)$ $\displaystyle
z^{\ast}(\mathcal{U},\lambda)\coloneqq\min_{x\in\mathcal{X},\pi^{(1)},\dots,\pi^{(p)}\in\mathbb{R}^{m^{\prime}}}\left\\{d^{t}\sum_{i=1}^{p}\lambda_{i}\pi^{(i)}\colon
C^{t}\pi^{(i)}=\hat{c_{i}}(x),\pi^{(i)}\geq 0,i=1,2,\dots,p\right\\}$

instead of $P(\mathcal{U},\lambda)$.

This leads to Algorithm 5.3. The following lemma shows correctness.

0: Biobjective mixed-integer linear robust optimization problem (BRO).

0: Finite initial set $\mathcal{U}^{(0)}\subseteq\mathcal{U}$.

0: Feasible set $\mathcal{X}$ is a polyhedron intersected with
$\mathbb{R}^{n-k}\times\mathbb{Z}^{k}$ for some $k\in\\{0,\ldots,n\\}$.

0: $\mathcal{U}$ a polytope and $f_{i}(x,\cdot)$, $i=1,2,\dots,p$ continuous
and quasi-convex.

0: (dom), (ideal) hold for $P(\mathcal{U})$ and for $P(\mathcal{U}^{\prime})$
for any finite subset $\mathcal{U}^{\prime}\subseteq\mathcal{U}$.

0: $f(x,\cdot)\colon\mathcal{U}\to\mathbb{R}^{p}$ linear

Initialize $\mathcal{L}\coloneqq\emptyset$ {$\mathcal{L}$ will contain list of
tuple images $(y^{l},y^{r})$ satisfying
$y^{l}_{1}<y^{r}_{1},y^{l}_{2}>y^{r}_{2}$}

Determine optimal objective value $\varepsilon_{1}$ of $D(\mathcal{U},(1,0))$

Determine $x^{L}\in\operatorname*{arg\,min}_{\mathcal{X}}\\{g_{(0,1)}(x)\colon
g_{(1,0)}(x)\leq\varepsilon_{1}\\}$

Set $y^{L}\coloneqq(\varepsilon_{1},g_{(0,1)}(x^{L}))^{t}$

Determine optimal objective value $\varepsilon_{2}$ of $D(\mathcal{U},(0,1))$

Determine $x^{R}\in\operatorname*{arg\,min}_{\mathcal{X}}\\{g_{(1,0)}(x)\colon
g_{(0,1)}(x)\leq\varepsilon_{2}\\}$

Set $y^{R}\coloneqq(g_{(1,0)}(x^{L}),\varepsilon_{2})^{t}$

if $y^{L}=y^{R}$ then

STOP. Only one nondominated image found

return $Y^{\ast}=\\{y^{L}\\},X^{\ast}=\\{x^{L}\\}$

else

$Y^{\ast}=\\{y^{L},y^{R}\\},X^{\ast}=\\{x^{L},x^{R}\\},\mathcal{L}=\\{(y^{L},y^{R})\\}$

end if

while $L\not=\emptyset$ do

Remove element $(y^{l},y^{r})$ from $\mathcal{L}$

Compute $\lambda\coloneqq(y^{l}_{2}-y^{r}_{2},y^{r}_{1}-y^{l}_{1})$.

Find one optimal solution $(x^{\ast},\pi^{(1)},\dots,\pi^{(k)})$ for
$D(\mathcal{U},\lambda)$.

Set $y_{i}^{\ast}=d^{t}\pi^{(i)\ast}$ for $i=1,2$.

if $\lambda^{T}y^{\ast}\not=\lambda^{T}y^{l}$ then

Add $y^{\ast}$ to $Y^{\ast}$, add $x^{\ast}$ to $X^{\ast}$.

Add $(y^{l},y^{\ast}),(y^{\ast},y^{r})$ to $\mathcal{L}$

end if

end while

return $X^{\ast}$: representative set of extreme supported efficient solutions
of $P(\mathcal{U})$.

return $Y^{\ast}$: set of extreme supported nondominated points of
$P(\mathcal{U})$.  Determine lexicographic solutions Solve
$D(\mathcal{U},\lambda)$

Algorithm 5.3 Multiobjective optimizer’s approach with dualization (DA)

######  Lemma 21.

Let $\textup{BRO}(\mathcal{U})$ with an nonempty polytope explicitly stated as
$\mathcal{U}=\\{\xi\in\mathbb{R}^{m}\colon C\xi\leq d\\}$ for a matrix
$C\in\mathbb{R}^{m^{\prime}\times m}$ and a vector
$d\in\mathbb{R}^{m^{\prime}}$ as uncertainty set and bilinear functions
$f_{1},f_{2}\colon\mathcal{X}\times\mathcal{U}\to\mathbb{R}$ be given. Then
Algorithm 5.3 solves (BRO).

###### Proof.

The assumptions of Lemma 7 are satisfied since (BRO-1) and (BRO-3) hold and
$\mathcal{U}$ is a polytope. Hence dichotomic search can be applied to
$\min_{x\in\mathcal{X}}f^{\mathcal{U}}(x)$. It remains to be shown that
$P(\mathcal{U},\lambda)$ is solved correctly throughout the algorithm. Lemma
20 shows that robust solutions of $P(\mathcal{U},\lambda)$ can be determined
by solving $D(\mathcal{U},\lambda)$ (lines 2, 5 17) and the corresponding
point on the Pareto front can be computed by $y_{i}^{\ast}=d^{t}\pi^{(i)\ast}$
(see line 16). ∎

##  6 Numerical results

We implemented Algorithms 5.1, 5.2 and 5.3 and conducted computational
experiments.

#### Structure of the problems.

We restricted ourselves to a certain class of biobjective optimization
problems: The objective functions
$f_{i}\colon\mathcal{X}\times\mathcal{U}\to\mathbb{R}^{2}$, $i=1,2$, were
assumed to be bilinear, and the feasible set and uncertainty set were
polytopes or discrete sets. More specifically, we considered problems

$\displaystyle P(\mathcal{U})$
$\displaystyle\left\\{\min_{x\in\mathcal{X}}\begin{pmatrix}\max_{\xi\in\mathcal{U}}\xi^{t}M_{1}x\\\
\max_{\xi\in\mathcal{U}}\xi^{t}M_{2}x\end{pmatrix}\right\\}_{\xi\in\mathcal{U}}$

with

$\displaystyle\mathcal{X}$ $\displaystyle=\\{x\in\mathbb{R}^{n}\colon
L^{x}\leq x_{i}\leq U^{x},Ax\leq b\\}\textup{ or }$ $\displaystyle\mathcal{X}$
$\displaystyle=\\{x\in\mathbb{Z}^{n}\colon L^{x}\leq x_{i}\leq U^{x},Ax\leq
b\\},$ $\displaystyle\mathcal{U}$ $\displaystyle=\\{\xi\in\mathbb{R}^{m}\colon
L^{\xi}\leq\xi_{i}\leq U^{\xi},C\xi\leq d\\}\textup{ or }$
$\displaystyle\mathcal{U}$ $\displaystyle=\\{\xi\in\mathbb{Z}^{m}\colon
L^{\xi}\leq\xi_{i}\leq U^{\xi},C\xi\leq d\\}.$

The lower and upper bounds $L^{x},U^{x},L^{\xi},U^{\xi}$ are added to ensure
that $\mathcal{X}$ and $\mathcal{U}$ are subsets of the boxes
$[L^{x},U^{x}]^{n}$ and $[L^{\xi},U^{\xi}]^{m}$, respectively, and, thus, are
bounded as it is required. We chose $L^{x}=1,U^{x}=200,L^{\xi}=-100$ and
$U^{\xi}=100$. By doing so we avoid problems where $0_{n}\in\mathcal{X}$ and
$0_{m}\in\operatorname*{int}(\mathcal{U})$, since this would imply that $x=0$
is a trivial minimizer of $f_{i}^{\mathcal{U}}(x)=\max_{\xi\in\mathcal{U}}\xi
M_{i}x$, $i=1,2$.

#### Generating instances

We created 100 instances of $\textup{BRO}(\mathcal{U})$ with
$A\in\mathbb{Z}^{30\times 5}$ and $C\in\mathbb{Z}^{30\times 5}$. To obtain
instances with smaller number of constraints, as used in our experiments, we
removed constraints from these initial instances. This makes it easier to draw
conclusions when comparing algorithm performance for different values of
$n^{\prime}$ and $m^{\prime}$. The entries of the matrices
$A\in\mathbb{Z}^{n^{\prime}\times n}$ and $C\in\mathbb{Z}^{m^{\prime}\times
m}$ as well as the entries of $M_{1},M_{2}\in\mathbb{Z}^{m\times n}$
determining the objective function are randomly and independently generated
uniformly distributed integers in $\\{-100,-99,\dots,99,100\\}$.

Equally, $\tilde{b}_{i}$, $i=1,2,\dots,n^{\prime}$ and $\tilde{d}_{j}$,
$j=1,2,\dots,m^{\prime}$ are randomly generated uniformly distributed integers
in $\\{50,51,\dots,99,100\\}$. We then set
$\bar{x}\coloneqq(100,100,\dots,100)^{t}\in\mathbb{Z}^{n}$ and
$\bar{\xi}\coloneqq(0,0,\dots,0)^{t}\in\mathbb{Z}^{m}$. Let $A_{i}$,
$i=1,2,\dots,n^{\prime}$ and $C_{j}$, $j=1,2,\dots,m^{\prime}$ denote the the
columns of $A$ and $C$. By setting the right hand-side coefficients
$b_{i}\coloneqq A_{i}^{t}x_{0}+\tilde{b}_{i}\left\|A_{i}\right\|_{2}$ for
$i=1,2,\dots,n^{\prime}$ and $d_{j}\coloneqq
C_{j}^{t}\xi_{0}+\tilde{d}_{j}\left\|C_{j}\right\|_{2}$ for
$j=1,2,\dots,m^{\prime}$, we guarantee that the spheres
$\\{x\in\mathbb{R}^{n}\colon\left\|x-\bar{x}\right\|_{2}\leq 50\\}$ and
$\\{\xi\in\mathbb{R}^{m}\colon\left\|\xi-\bar{\xi}\right\|_{2}\leq 50\\}$ are
included in $\mathcal{X}$ and $\mathcal{U}$, respectively. See [CV14] for more
on this.

#### Implementation

We used C++ to implement our algorithms. Whenever a linear or integer
optimization problem has to be solved, Gurobi 2.3 is called (with default
settings). We use Gurobi’s capacity to provide solution that are known to be
basic solutions. The implementations were tested on a computer with 16 GB RAM,
AMD Ryzen 5 PRO 2500U, 2.00 GHz.

###  6.1 Evaluation of the algorithms

In this section we evaluate the performance of the algorithms for instances of
different types (polytopal and discrete sets $\mathcal{X}$ and $\mathcal{U}$)
and different sizes by varying the number of considered constraints
$n^{\prime}$ and $m^{\prime}$, respectively.

#### Discrete feasible set and discrete uncertainty set

First, let us consider problems with a discrete feasible set and a discrete
uncertainty set. For such instances, the robust optimizer’s approach (ROA,
Algorithm 5.1) and the multiobjective optimizer’s approach (MOA, Algorithm
5.2) in its baseline version and with its two warm-start modifications are
available. The dualization approach (DA, Algorithm 5.3) cannot solve such
instances as it requires a polytope as uncertainty set.

Figure 3 shows the average running time of our algorithms. Each data point is
the average over 100 instances with $n^{\prime}$ constraints on the feasible
set. The number of variables for the feasible set $n$, the number of variables
for the uncertainty set $m$ and the number of constraints for the uncertainty
set $m^{\prime}$ are all fixed and set at 5.

Figure 3: Average running time of our four algorithms for 100 instances as a
function of $n^{\prime}$ with $n=m=m^{\prime}=5$ fixed, $\mathcal{X}$ and
$\mathcal{U}$ discrete (the lines for MOA-ws1 and MOA-ws2 overlap and are hard
to see)

Independently of $n^{\prime}$, the robust optimizer’s approach – where the
uncertainty set $\mathcal{U}^{(k)}$ increases monotonously – is faster than
the baseline version of the multiobjective optimizer’s approach. However, the
warm start modifications to the latter method turn out to be significant
improvements over the baseline version: with those the multiobjective
optimizer’s approach performs faster. We see a clear increase in running time
when going from 5 to 10 constraints for all tested methods, but above that
point an increasing number number of constraints does not seem to make the
problem much harder to solve.

Figure 4 shows how the number of constraints in the definition of the
uncertainty set $\mathcal{U}$ influences the running time.

Figure 4: Average running time of our four algorithms for 100 instances as a
function of $m^{\prime}$ with $n=m=n^{\prime}=5$ fixed, $\mathcal{X}$ and
$\mathcal{U}$ discrete

We observe the same pattern: The modified warm-start versions of MOA are by
far the fastest algorithms; ROA is still faster than the baseline version of
MOA. Clearly, the problem gets harder the more constraints are necessary to
describe $\mathcal{U}$. This leads us to conclude that the difficulty of the
problem is rooted much more in the complexity of $\mathcal{U}$ than in the one
of $\mathcal{X}$.

#### Discrete feasible set and polytopal uncertainty set

Now let us turn to problems with a polytope as uncertainty set. On those
instances all of the algorithms we introduced can be used. This includes the
dualization approach (DA), which is the only algorithm that does not use
optimization-pessimization but instead solves the scalarized problem
$P(\mathcal{U},\lambda)$ for each weight $\lambda$ directly (via the means of
dualization of the inner problem).

Figures 5 and 6 show the average running time of our algorithms on the same
instances as in Figures 3 and 4 – just with the integrality constraint for
$\mathcal{U}$ dropped.

Figure 5: Average running time of our five algorithms for 100 instances as a
function of $n^{\prime}$ with $n=m=m^{\prime}=5$ fixed, $\mathcal{X}$
discrete, $\mathcal{U}$ polytope Figure 6: Average running time of our five
algorithms for 100 instances as a function of $m^{\prime}$ with
$n=m=n^{\prime}=5$ fixed, $\mathcal{X}$ discrete, $\mathcal{U}$ polytope

Our experiments show that for such instances DA is effective, but not
noticeably better than the modified versions of MOA. The ranking of the other
algorithms is essentially the same as before: The modified warm-start versions
of MOA outperform ROA which is still faster than MOA’s baseline version.
Dropping the integrality constraint reduced the overall running time of all
algorithms by about factor two. This is while the number of extreme supported
nondominated points stayed roughly the same.

The apparent ranking of the proposed algorithms raises the question of whether
this applies only on average over a larger number of instances, or if it also
applies to each individual instance. For this we turn to Figure 7. In this
figure we display the objective values for the 5 different algorithms on the
first 10 of the tested 100 instances. Including all tested instances here does
not change the discussed findings, but decreases visibility, which is why we
included only the results of ten instances.

Figure 7: Running time of our five algorithms for 10 instances with
$n=n^{\prime}=m=5,m^{\prime}=30$, $\mathcal{X}$ discrete, $\mathcal{U}$
polytope

Each of the ten columns in Figure 7 represents one instance (with
$n=m=n^{\prime}=5,m^{\prime}=30$) on which we tested the algorithms. We can
see that for all instances either DA or the warm-start modifications of MOA
perform best and either ROA or the baseline version of MOA perform worst. The
ranking of the algorithms is not the same for all instances.

To get a deeper understanding of this we turn to Figure 8.

Figure 8: Running time vs. number of worst-case scenarios added for 10
instances with $n=n^{\prime}=m=5,m^{\prime}=30$, $\mathcal{X}$ discrete,
$\mathcal{U}$ polytope

For the ROA and all three versions of MOA it shows the running time plotted
against the number of times we add a worst-case scenario during the execution
of the algorithms. The strong correlation indicates that the number of
pessimization steps decisively determines the overall time required. The two
algorithms where the uncertainty set $\mathcal{U}^{(k)}$ grows monotonously,
namely MOA-ws1 and ROA, have similarly high costs per added scenario. This can
be explained by the fact that the resulting robust optimization problems are
harder to solve due to the number of scenarios in $\mathcal{U}^{(k)}$. Vice
versa, MOA and MOA-ws2 both “forget” scenarios. Consequently, they need to
(re)add more scenarios, but the optimization problems are simpler. For them
the ratio between runtime and added scenario is lower. This also explains why
the warm-start modifications pay off: Apparently, the additional cost of
starting with a larger scenario set $\mathcal{U}^{(k)}$ is more than offset by
less frequent need to execute of the pessimization step.

#### Evaluation for polytopal feasible sets

Additionally, we tested the algorithms on instances with feasible sets
$\mathcal{X}$ that are polytopes. In this case DA is faster. Apart from that,
the observations do not deviate significantly from the ones discussed in the
previous paragraphs except that if $\mathcal{U}$ is a polytope too, DA is
faster than MOA-ws1 and MOA-ws2 as can be seen in Figure 9.

Figure 9: Average running time of our five algorithms for 100 instances as a
function of $m^{\prime}$ with $n=m=n^{\prime}=5$ fixed, $\mathcal{X}$ and
$\mathcal{U}$ polytopes

#### The algorithms as approximation algorithms

Lastly, we want to investigate how soon the algorithms provide a reasonable
approximation of the Pareto front. For this we turn to Algorithm 5.1, which in
the $k$-th iteration determines (via dichotomic search) all extreme supported
nondominated points of $BRO(\mathcal{U}^{k})$ and then determines the worst-
case outcomes of those points under $\mathcal{U}$. Figure 10 shows for an
instance with $n=m=n^{\prime}=5,m^{\prime}=30$ and $\mathcal{X}$,
$\mathcal{U}$ both continuous, the lower and upper bound determined in the
second and fourth iteration and the robust solutions determined in the final
7th iteration. We can see that our method provides a good approximation to the
Pareto front early on.

Figure 10: Lower bound and upper bound determined in the second, fourth
iteration and in the final (7th) iteration in an instance with
$n=m=10,n^{\prime}=m^{\prime}=20$ and $\mathcal{X}$, $\mathcal{U}$ continuous

##  7 Conclusions and further research

In this paper, we have shown how biobjective mixed-integer linear optimization
problems, where both objective functions are the maximum of a set of linear
objective functions, can be solved. While we framed this as a method for
_robust_ biobjective optimization – specifically to determine _point-based
minmax robust efficient_ solutions for biobjective mixed-integer linear robust
optimization problems –, our methods are not limited to such problems. They
can be applied to any biobjective optimization problem of the described
structure.

Our solution method combines a well-known approach from biobjective
optimization, namely dichotomic search, with approaches used in robust
optimization, namely optimization-pessimization and reformulation. In our
numerical experiments, it has be shown that all our approaches are sensible
for some problems. We illustrate which approach is most suitable for which
situation: The robust optimizer’s approach provides a good approximation of
the set of extreme supported efficient solutions already early on; the warm-
start modifications improve the multiobjective optimizer’s approach such that
it is fastest on instances where $\mathcal{U}$ is discrete. If $\mathcal{X}$
and $\mathcal{U}$ are polytopes, the dualization approach is the fastest.

Many avenues for further research exist that use the framework that we
developed: First, other and more advanced solution methods for multiobjective
optimization can be used. More specifically, dichotomic search can be replaced
by any other enumeration method for extreme nondominated points (such as the
one proposed in [BM15]). That way, a method similar to the one proposed in
this paper can be used for problems with more than two objectives. Similarly,
solution methods for specific problems such as the multiobjective knapsack or
the multiobjective TSP (see [Vis+98, Ehr05]) can be combined with
optimization-pessimization to find robust solutions of these problems.

Second, extension to other robustness concepts for multiobjective
optimization, such as set-based minmax robust efficiency, would be desirable.
We plan to adapt the presented algorithms to the concept of regret robust
efficiency (see [GW22]).

## Acknowledgments

Fabian Chlumsky-Harttmann was supported by the DFG Research Grant “Robust
Multi-Objective Optimization: Analysis and Approaches”.

## References

  * [ABV09] Hassene Aissi, Cristina Bazgan and Daniel Vanderpooten  “Min–max and min–max regret versions of combinatorial optimization problems: A survey”  In _European Journal of Operational Research_ 197.2, 2009, pp. 427–438
  * [AN79] Y. P. Aneja and K. P. K. Nair  “Bicriteria Transportation Problem”  In _Management Science_ 25.1, 1979, pp. 73–78
  * [Ant+20] Tadeusz Antczak, Yogendra Pandey, Vinay Singh and Shashi Kant Mishra  “On approximate efficiency for nonsmooth robust vector optimization problems”  In _Acta Mathematica Scientia_ 40.3 Springer, 2020, pp. 887–902
  * [Ass+08] Tiravat Assavapokee, Matthew J Realff, Jane C Ammons and I-Hsuan Hong  “Scenario relaxation algorithm for finite scenario-based min–max regret and min–max relative regret robust optimization”  In _Computers & operations research_ 35.6 Elsevier, 2008, pp. 2093–2102
  * [BDL16] Dimitris Bertsimas, Iain Dunning and Miles Lubin  “Reformulation versus cutting-planes for robust optimization”  In _Computational Management Science_ 13.2 Springer, 2016, pp. 195–217
  * [BF17] R. Bokrantz and A. Fredriksson  “Necessary and sufficient conditions for Pareto efficiency in robust multiobjective optimization”  In _European Journal of Operational Research_ 262.2, 2017, pp. 682–692
  * [BM15] Fritz Bökler and Petra Mutzel  “Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems”  In _Algorithms - ESA 2015_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2015, pp. 288–299
  * [BNA13] Mathias Bürger, Giuseppe Notarstefano and Frank Allgöwer  “A polyhedral approximation framework for convex and robust distributed optimization”  In _IEEE Transactions on Automatic Control_ 59.2 IEEE, 2013, pp. 384–395
  * [BS19] Marco Botte and Anita Schöbel  “Dominance for multi-objective robust optimization concepts”  In _European Journal of Operational Research_ 273.2, 2019, pp. 430–440
  * [BTEN09] A. Ben-Tal, L. El Ghaoui and A.S. Nemirovski  “Robust Optimization”, Princeton Series in Applied Mathematics  Princeton University Press, 2009
  * [BV04] Stephen P Boyd and Lieven Vandenberghe  “Convex optimization”  Cambridge university press, 2004
  * [Bie07] Daniel Bienstock  “Histogram models for robust portfolio optimization”  In _Journal of computational finance_ 11.1 RISK PUBLICATIONS, 2007, pp. 1
  * [Bit80] Gabriel R. Bitran  “Linear Multiple Objective Problems with Interval Coefficients”  In _Management Science_ 26, 1980, pp. 694–706
  * [CV14] Karthekeyan Chandrasekaran and Santosh S Vempala  “Integer feasibility of random polytopes: random integer programs”  In _Proceedings of the 5th conference on Innovations in theoretical computer science_ , 2014, pp. 449–458
  * [Chu20] Thai Doan Chuong  “Robust Optimality and Duality in Multiobjective Optimization Problems under Data Uncertainty”  In _SIAM Journal on Optimization_ 30.2, 2020, pp. 1501–1526
  * [Coh78] J.L. Cohon  “Multiobjective Programming and Planning”  Academic Press, 1978
  * [EIS14] M. Ehrgott, J. Ide and A. Schöbel  “Minmax Robustness for Multi-objective Optimization Problems”  In _European Journal of Operational Research_ 239, 2014, pp. 17–31
  * [EKS17] G. Eichfelder, C. Krüger and A. Schöbel  “Decision uncertainty in multiobjective optimization” online first  In _Journal of Global Optimization_ , 2017, pp. 1–26
  * [ES20] A. Engau and D. Sigler  “Pareto Solutions in Multicriteria Optimization under Uncertainty”  In _European Journal of Operational Research_ 281.2 Elsevier, 2020, pp. 357–368
  * [Ehr05] M. Ehrgott  “Multicriteria Optimization”  Springer Nature, 2005
  * [GS16] M. Goerigk and A. Schöbel  “Algorithm Engineering in Robust Optimization”  In _Algorithm Engineering: Selected Results and Surveys_ 9220, LNCS State of the Art, 2016, pp. 245–279
  * [GW22] Patrick Groetzner and Ralf Werner  “Multiobjective optimization under uncertainty: A multiobjective robust (relative) regret approach”  In _European Journal of Operational Research_ 296.1, 2022, pp. 101–115
  * [GYd15] Bram L. Gorissen, Yanıkoğlu and Dick den Hertog  “A practical guide to robust optimization”  In _Omega_ 53, 2015, pp. 124–137
  * [Gob+15] M.A. Goberna, V. Jeyakumar, G. Li and J. Vicente-Pérez  “Robust solutions to multi-objective linear programs with uncertain data”  In _European Journal of Operational Research_ 242, 2015, pp. 730–743
  * [HNS13] F. Hassanzadeh, H. Nemati and M. Sun  “Robust Optimization for Multiobjective Programming Problems with Imprecise Information”  In _Procedia Computer Science_ 17, 2013, pp. 357 –364
  * [HNS14] Farhad Hassanzadeh, Hamid Nemati and Minghe Sun  “Robust optimization for interactive multiobjective programming with imprecise information applied to R&D project portfolio selection”  In _European Journal of Operational Research_ 238.1 Elsevier, 2014, pp. 41–53
  * [Hen86] Mordechai I Henig  “The domination property in multicriteria optimization”  In _Journal of Mathematical Analysis and Applications_ 114.1, 1986, pp. 7–16
  * [IS16] J. Ide and A. Schöbel  “Robustness for uncertain multi-objective optimization: A survey and analysis of different concepts”  In _OR Spectrum_ 38.1, 2016, pp. 235–271
  * [IS96] Masahiro Inuiguchi and Masatoshi Sakawa  “Possible and necessary efficiency in possibilistic multiobjective linear programming problems and possible efficiency test” Fuzzy Multiple Criteria Decision Making  In _Fuzzy Sets and Systems_ 78.2, 1996, pp. 231 –241
  * [Ide+14] J. Ide, E. Köbis, D. Kuroiwa, A. Schöbel and C. Tammer  “The relationship between multi-objective robustness concepts and set valued optimization”  In _Fixed Point Theory and Applications_ 2014.83, 2014
  * [KD69] RL Kruse and JJ Deely  “Joint continuity of monotonic functions”  In _The American Mathematical Monthly_ 76.1 Taylor & Francis, 1969, pp. 74–76
  * [KL12] D. Kuroiwa and G. M. Lee  “On Robust Multiobjective Optimization”  In _Vietnam Journal of Mathematics_ 40.2&3, 2012, pp. 305–317
  * [Kha+09] Leonid Khachiyan, Endre Boros, Konrad Borys, Vladimir Gurvich and Khaled Elbassioni  “Generating all vertices of a polyhedron is hard”  In _Twentieth Anniversary Volume: Discrete & Computational Geometry_ Springer, 2009, pp. 1–17
  * [Krü+23] Corinna Krüger, Anita Schöbel, Lena Fritzen and Margaret M Wiecek  “The point-based robustness gap for uncertain multiobjective optimization”  In _Optimization_ Taylor & Francis, 2023, pp. 1–35
  * [Kuh+16] K. Kuhn, A. Raith, M. Schmidt and A. Schöbel  “Bicriteria robust optimization”  In _European Journal of Operational Research_ 252, 2016, pp. 418–431
  * [MB09] Almir Mutapcic and Stephen Boyd  “Cutting-set methods for robust convex optimization with pessimizing oracles”  In _Optimization Methods and Software_ 24.3 Taylor & Francis, 2009, pp. 381–406
  * [Mon06] Roberto Montemanni  “A Benders decomposition approach for the robust spanning tree problem with interval data”  In _European Journal of Operational Research_ 174.3 Elsevier, 2006, pp. 1479–1490
  * [ÖK10] Özgür Özpeynirci and Murat Köksalan  “An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs”  In _Management Science_ 56.12 INFORMS, 2010, pp. 2302–2315
  * [PKL19] Anthony Przybylski, Kathrin Klamroth and Renaud Lacour  “A simple and efficient dichotomic search algorithm for multi-objective mixed integer linear programs”, 2019  arXiv:1911.08937 [math.OC]
  * [PS20] Julius Pätzold and Anita Schöbel  “Approximate cutting plane approaches for exact solutions to robust optimization problems”  In _European Journal of Operational Research_ 284.1, 2020, pp. 20–30
  * [RY13] S. Rivaz and M.A. Yaghoobi  “Minimax regret solution to multiobjective linear programming problems with interval objective functions coefficients”  In _Central European Journal of Operations Research_ 21.3 Springer, 2013, pp. 625–649
  * [Rai+18] Andrea Raith, Marie Schmidt, Anita Schöbel and Lisa Thom  “Extensions of labeling algorithms for multi-objective uncertain shortest path problems”  In _Networks_ 72.1 Wiley Online Library, 2018, pp. 84–127
  * [Rai+18a] Andrea Raith, Marie Schmidt, Anita Schöbel and Lisa Thom  “Multi-objective minmax robust combinatorial optimization with cardinality-constrained uncertainty”  In _European Journal of Operational Research_ 267.2 Elsevier, 2018, pp. 628–642
  * [Ree94] Rembert Reemtsen  “Some outer approximation methods for semi-infinite optimization problems”  In _Journal of Computational and Applied Mathematics_ 53.1 Elsevier, 1994, pp. 87–108
  * [SAG11] Sauleh Siddiqui, Shapour Azarm and Steven Gabriel  “A modified Benders decomposition method for efficient robust optimization under interval uncertainty”  In _Structural and Multidisciplinary Optimization_ 44 Springer, 2011, pp. 259–275
  * [SZK21] Anita Schöbel and Yue Zhou-Kangas  “The price of multiobjective robustness: Analyzing solution sets to uncertain multiobjective problems”  In _European Journal of Operational Research_ 291.2, 2021, pp. 782–793