# Machine Learning for $K$-adaptability
in Two-stage Robust Optimization

Esther Julien
Delft University of Technology
<EMAIL_ADDRESS>
&Krzysztof Postek
Deft University of Technology
<EMAIL_ADDRESS>
&Ş. İlker Birbil
University of Amsterdam
<EMAIL_ADDRESS>
###### Abstract

Two-stage robust optimization problems constitute one of the hardest
optimization problem classes. One of the solution approaches to this class of
problems is $K$-adaptability. This approach simultaneously seeks the best
partitioning of the uncertainty set of scenarios into $K$ subsets, and
optimizes decisions corresponding to each of these subsets. In general case,
it is solved using the $K$-adaptability branch-and-bound algorithm, which
requires exploration of exponentially-growing solution trees. To accelerate
finding high-quality solutions in such trees, we propose a machine learning-
based node selection strategy. In particular, we construct a feature
engineering scheme based on general two-stage robust optimization insights
that allows us to train our machine learning tool on a database of resolved
B&B trees, and to apply it as-is to problems of different sizes and/or types.
We experimentally show that using our learned node selection strategy
outperforms a vanilla, random node selection strategy when tested on problems
of the same type as the training problems, also in case the $K$-value or the
problem size differs from the training ones.

_Keywords_ node selection; clustering; two-stage robust optimization;
$K$-adaptability; machine learning; tree search

##  1 Introduction

Many optimization problems are affected by data uncertainty caused by errors
in the forecast, implementation, or measurement. Robust optimization (RO) is
one of the key paradigms to solve such problems, where the goal is to find an
optimal solution among the ones that remain feasible for all data realizations
within an _uncertainty set_ (Ben-Tal et al., 2009). This set includes all
_reasonable_ data outcomes.

A specific class of RO problems comprises two-stage robust optimization (2SRO)
problems in which some decisions are implemented _before_ the uncertain data
is known (here-and-now decisions), and other decisions are implemented _after_
the data is revealed (wait-and-see decisions). Such a problem can be
formulated as

$\min_{\boldsymbol{x}\in\mathcal{X}}\quad\max_{\boldsymbol{z}\in\mathcal{Z}}\quad\min_{\boldsymbol{y}\in\mathcal{Y}}\big{\\{}\boldsymbol{c}(\boldsymbol{z})^{\intercal}\boldsymbol{x}+\boldsymbol{d}(\boldsymbol{z})^{\intercal}\boldsymbol{y}\mathrel{\mathop{\mathchar
58\relax}}\boldsymbol{T}(\boldsymbol{z})\boldsymbol{x}+\boldsymbol{W}(\boldsymbol{z})\boldsymbol{y}\leq\boldsymbol{h}(\boldsymbol{z}),\quad\forall\boldsymbol{z}\in\mathcal{Z}\big{\\}},$
(1)

where $\boldsymbol{x}\in\mathcal{X}\subseteq\mathbb{R}^{N_{x}}$ and
$\boldsymbol{y}\in\mathcal{Y}\subseteq\mathbb{R}^{N_{y}}$ are the here-and-now
and wait-and-see decisions, respectively, and $\boldsymbol{z}$ is the vector
of initially unknown data belonging to the uncertainty set
$\mathcal{Z}\subseteq\mathbb{R}^{N_{z}}$. Solving problem (1) is difficult in
general, since $\mathcal{Z}$ might include an infinite number of scenarios,
and hence different values of $\boldsymbol{y}$ might be optimal for different
realizations of $\boldsymbol{z}$. In fact, finding optimal $\boldsymbol{x}$ is
an NP-hard problem (Guslitzer, 2002). To address this difficulty, several
approaches have been proposed. The first one is to use so-called decision
rules which explicitly formulate the second-stage decision $\boldsymbol{y}$ as
a function of $\boldsymbol{z}$, and hence the function parameters become
first-stage decisions next to $\boldsymbol{x}$; see Ben-Tal et al. (2004).
Another approach is to partition $\mathcal{Z}$ into subsets and to assign a
separate copy of $\boldsymbol{y}$ to each of the subsets. The partitioning is
then iteratively refined, and the decisions become increasingly _customized_
to the outcomes of $\boldsymbol{z}$.

In this paper, we consider a third approach to (1) known as $K$-adaptability.
There, at most $K$ possible wait-and-see decisions
$\boldsymbol{y}_{1},\ldots,\boldsymbol{y}_{K}$ are allowed to be constructed,
and the decision maker must select one of those. The values of the possible
$\boldsymbol{y}_{k}$’s become the first-stage variables, and the problem boils
down to

$\min_{\boldsymbol{x}\in\mathcal{X},\boldsymbol{y}\in\mathcal{Y}^{K}}\max_{\boldsymbol{z}\in\mathcal{Z}}\quad\min_{k\in\mathcal{K}}\big{\\{}\boldsymbol{c}(\boldsymbol{z})^{\intercal}\boldsymbol{x}+\boldsymbol{d}(\boldsymbol{z})^{\intercal}\boldsymbol{y}_{k}\mathrel{\mathop{\mathchar
58\relax}}\boldsymbol{T}(\boldsymbol{z})\boldsymbol{x}+\boldsymbol{W}(\boldsymbol{z})\boldsymbol{y}_{k}\leq\boldsymbol{h}(\boldsymbol{z}),\quad\forall\boldsymbol{z}\in\mathcal{Z}_{k}\big{\\}},$
(2)

where $\mathcal{K}=\\{1,\ldots,K\\}$ and
$\mathcal{Y}^{K}=\bigtimes_{k=1}^{K}{\mathcal{Y}}$. Although the solution
space of (2) is finite-dimensional, it remains an NP-hard problem. For certain
cases, (2) can be equivalently rewritten as a mixed integer linear programming
(MILP) model (Hanasusanto et al., 2015).

The above formulation requires that for given $\boldsymbol{x}\in\mathcal{X}$
and $\boldsymbol{z}\in\mathcal{Z}$, there is at least one decision
$\boldsymbol{y}_{k}$, $k\in\mathcal{K}$ satisfying
$\boldsymbol{T}(\boldsymbol{z})\boldsymbol{x}+\boldsymbol{W}(\boldsymbol{z})\boldsymbol{y}_{k}\leq\boldsymbol{h}(\boldsymbol{z})$,
and among those one (or more) minimizing the objective. Looking at (2) from
the point of view $\boldsymbol{y}_{k}$, we can say that for each
$\boldsymbol{y}_{k}$, we can identify a subset $\mathcal{Z}_{k}$ of
$\mathcal{Z}$ for which a given $\boldsymbol{y}_{k}$ is optimal. The union of
sets $\mathcal{Z}_{k}$, $k\in\mathcal{K}$ is equal to $\mathcal{Z}$ although
they need not be mutually disjoint (but a mutually disjoint partition of
$\mathcal{Z}$ can be constructed). Consequently, solving (2) involves
implicitly (i) clustering $\mathcal{Z}$, and (ii) optimizing the per-cluster
decision so that the objective function corresponding to _the most difficult
cluster_ is minimized. Such a simultaneous clustering and per-cluster
optimization also occurs, for example in retail. A line of $K$ products is to
be designed to attract the largest possible group of customers. The customers
are the clustered into $K$ groups, and the nature of the products is guided by
the cluster characteristics.

In this manuscript, we focus on the general $K$-adaptability case for which
the only existing solution approach is the $K$-adaptability branch-and-bound
($K$-B&B) algorithm of Subramanyam et al. (2020). This approach, as opposed to
the top-down partitioning of $\mathcal{Z}$ of Bertsimas and Dunning (2016) or
Postek and den Hertog (2016), proceeds by gradually building up discrete
subsets $\bar{\mathcal{Z}}_{k}$ of scenarios. In most practical cases, a
solution to (2), where $\boldsymbol{y}_{1},\ldots,\boldsymbol{y}_{K}$ are
feasible for large $\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{K}$, is
also feasible to the original problem. The problem, however, lies in knowing
which scenarios should be grouped together. In other words, a decision needs
to be made on which scenarios of $\mathcal{Z}$ should be responded to with the
same decision. How well this question is answered, determines the
(sub)optimality of $\boldsymbol{y}_{1},\ldots,\boldsymbol{y}_{K}$. In
Subramanyam et al. (2020), a search tree is used to determine the best
collection (see Section 2 for details). However, this approach suffers from
exponential growth.

We introduce a method for learning the best strategy to explore this tree. In
particular, we learn which nodes to evaluate next in depth-first search
_dives_ to obtain good solutions faster. These predictions are made using a
supervised machine learning (ML) model. Due to the supervised nature, some
_oracle_ is required to be imitated. In design of this oracle, we are partly
inspired by Monte Carlo tree search (MCTS) (Browne et al., 2012), which is
often used for exploring large trees. Namely, the training data is obtained by
exploring $K$-B&B trees via an adaptation of MCTS (see Section 3.4). The
scores given to the nodes in the MCTS-like exploration are stored and used as
labels in our training data.

In the field of solving MILPs, learning node selection to speed up exploring
the B&B tree has been done, _e.g._ , by He et al. (2014). Here, a node
selection policy is designed by imitating an oracle. This oracle is
constructed using the optimal solutions of various MILP data sets. More
recently, Khalil et al. (2022a) used a graph neural network to learn node
selection. For an overview on ML for learning branching policies in B&B, see
Bengio et al. (2020). There has also been done a vast amount of research on
applying MCTS directly to solving combinatorial problems. In Sabharwal et al.
(2012) a special case of MCTS called Upper Confidence bounds for Trees (UCT),
is used for designing a node selection strategy to explore B&B trees (for
MIPs). In Khalil et al. (2022b) MCTS is used to find the best backdoor (i.e.,
a subset of variables used for branching) for solving MIPs. Loth et al. (2013)
have used MCTS for enhancing constraint programming solvers, which naturally
use a search tree for solving combinatorial problems. For an elaborate
overview on modifications and applications of MCTS, we refer to Świechowski et
al. (2022).

The remainder of the paper is structured as follows. In Section 2 we describe
the inner workings of the $K$-adaptability branch-and-bound to set the stage
for our contribution. In Section 3 we outline our ML methodology along with
the data generation procedure. Section 4 discusses the results of a numerical
study, and Section 5 concludes with some remarks on future works.

##  2 Preliminaries

It is instructive to conceptualize a solution to (2) as a solution to a nested
clustering and optimization-for-clusters methodology. As already mentioned in
Section 1, a feasible solution to (2) can be used to construct a partition of
the uncertainty set into subsets $\mathcal{Z}_{1},\ldots,\mathcal{Z}_{K}$ such
that $\bigcup_{k=1}^{K}\mathcal{Z}_{k}=\mathcal{Z}$. Here, decision
$\boldsymbol{y}_{k}$ is applied in the second time stage if
$\boldsymbol{z}\in\mathcal{Z}_{k}$. The decision framework associated with a
given solution is illustrated in Figure 1.

Figure 1: A framework of the $K$-adaptability problem, where we split the
uncertainty set (red box) in $K=2$ parts. Here, $\boldsymbol{x}$ represents
the first-stage decisions, and $\boldsymbol{y}_{1}$ with $\boldsymbol{y}_{2}$
those of the second-stage.

For such a _fixed partition_ the corresponding optimization problem becomes

$\displaystyle\min_{\boldsymbol{x}\in\mathcal{X},\boldsymbol{y}\in\mathcal{Y}^{K}}$
$\displaystyle\max_{k\in\mathcal{K}}\max_{\boldsymbol{z}\in\mathcal{Z}_{k}}\left\\{\boldsymbol{c}(\boldsymbol{z})^{\intercal}\boldsymbol{x}+\boldsymbol{d}(\boldsymbol{z})^{\intercal}\boldsymbol{y}_{k}\right\\}$
(3) s.t.
$\displaystyle\boldsymbol{T}(\boldsymbol{z})\boldsymbol{x}+\boldsymbol{W}(\boldsymbol{z})\boldsymbol{y}_{k}\leq\boldsymbol{h}(\boldsymbol{z}),\quad\forall\boldsymbol{z}\in\mathcal{Z}_{k},\forall
k\in\mathcal{K}.$

The optimal solution to (2) also corresponds to an optimal partitioning of
$\mathcal{Z}$, and the optimal decisions of (3) with that partitioning.
Finding an optimal partition and the corresponding decisions has been shown to
be NP-hard by Bertsimas and Caramanis (2010). For that reason, Subramanyam et
al. (2020) have proposed the $K$-B&B algorithm. There, the idea is to
gradually build up a collection of finite subsets
$\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{K}$, such that for each
$k\in\mathcal{K}$ an optimal solution to (3) with
$\mathcal{Z}_{k}=\bar{\mathcal{Z}}_{k}$ is also an optimal solution to (2).

The algorithm follows a master-subproblem approach. The master problem solves
(2) with $K$ finite subsets of scenarios. The subproblem finds the scenario
for which the current master solution is not robust. The number $K$ of
possible assignments of this new scenario to one of the existing subsets gives
rise to using a search tree. Each tree node corresponds to a partition of all
scenarios found so far into $K$ subsets. The goal is to find the node with the
best partition. An illustration of the search tree is given in Figure 2. The
tree grows exponentially and thus only (very) small-scale problems can be
solved in reasonable time. The method we propose in the next section learns a
good node selection strategy with the goal of converging to the optimal
solution much faster than $K$-B&B.

Figure 2: Search tree for $K$-adaptability branch-and-bound ($K=2$).

####  Master problem.

This problem solves the $K$-adaptability problem (2) with respect to the
currently found scenarios grouped into
$\bar{\mathcal{Z}}_{k}\subset\mathcal{Z}$ for all $k\in\mathcal{K}$. For a
collection $\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{K}$, the problem
formulation is defined as follows:

$\displaystyle\min_{\theta\in\mathbb{R},\boldsymbol{x}\in\mathcal{X},\boldsymbol{y}\in\mathcal{Y}^{K}}$
$\displaystyle\theta$ (4) s.t.
$\displaystyle\boldsymbol{c}(\boldsymbol{z})^{\intercal}\boldsymbol{x}+\boldsymbol{d}(\boldsymbol{z})^{\intercal}\boldsymbol{y}_{k}\leq\theta,$
$\displaystyle\forall\boldsymbol{z}\in\bar{\mathcal{Z}}_{k},\forall
k\in\mathcal{K},$
$\displaystyle\boldsymbol{T}(\boldsymbol{z})\boldsymbol{x}+\boldsymbol{W}(\boldsymbol{z})\boldsymbol{y}_{k}\leq\boldsymbol{h}(\boldsymbol{z}),\quad\quad\quad$
$\displaystyle\forall\boldsymbol{z}\in\bar{\mathcal{Z}}_{k},\forall
k\in\mathcal{K},$

where $\theta$ is the current estimate of the objective function value. We
denote the optimal solution of (4) by the triplet
$(\theta^{*},\boldsymbol{x}^{*},\boldsymbol{y}^{*})$.

####  Subproblem.

The subproblem aims to find a scenario $\boldsymbol{z}$ for which the current
master solution is infeasible. That is, a scenario is found such that for each
$k$, at least one of the following is true:

  * •

the current estimate of $\theta^{*}$ is too low, i.e.,
$\boldsymbol{c}(\boldsymbol{z})^{\intercal}\boldsymbol{x}+\boldsymbol{d}(\boldsymbol{z})^{\intercal}\boldsymbol{y}_{k}>\theta^{\ast}$;

  * •

at least one of the original constraints is violated, i.e.,
$\boldsymbol{T}(\boldsymbol{z})\boldsymbol{x}^{\ast}+\boldsymbol{W}(\boldsymbol{z})\boldsymbol{y}_{k}^{\ast}>\boldsymbol{h}(\boldsymbol{z})$.

If no such scenario exists, we define the solution
$(\theta^{*},\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ as a robust solution.
When such a scenario $\boldsymbol{z}^{*}$ does exist, the solution is not
robust and the newly-found scenario is assigned to one of the sets
$\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{K}$.

######  Definition 2.1.

A solution
$(\theta^{*},\boldsymbol{x}^{*},\boldsymbol{y}_{1}^{*},\ldots,\boldsymbol{y}_{K}^{*})$
to (4) is robust if

$\forall\boldsymbol{z}\in\mathcal{Z},\exists
k\in\mathcal{K}\mathrel{\mathop{\mathchar 58\relax}}\
\boldsymbol{T}(\boldsymbol{z})\boldsymbol{x}^{\ast}+\boldsymbol{W}(\boldsymbol{z})\boldsymbol{y}_{k}^{\ast}\leq\boldsymbol{h}(\boldsymbol{z}),\
\boldsymbol{c}(\boldsymbol{z})^{\intercal}\boldsymbol{x}^{\ast}+\boldsymbol{d}(\boldsymbol{z})^{\intercal}\boldsymbol{y}_{k}^{\ast}\leq\theta^{\ast}.$

######  Example 2.1.

Consider the following master problem

$\displaystyle\min_{\theta,\boldsymbol{x},\boldsymbol{y}}\quad$
$\displaystyle\theta$ s.t.
$\displaystyle\theta\in\mathbb{R},\boldsymbol{x}\in\\{0,1\\}^{2},\boldsymbol{y}\in\\{0,1\\}^{2},$
$\displaystyle\boldsymbol{z}^{\intercal}\boldsymbol{x}+[3z_{1},2z_{2}]\boldsymbol{y}_{k}\leq\theta,$
$\displaystyle\forall\boldsymbol{z}\in\bar{\mathcal{Z}}_{k},\forall
k\in\mathcal{K},$
$\displaystyle\boldsymbol{y}_{k}\geq\boldsymbol{1}-\boldsymbol{z},$
$\displaystyle\forall\boldsymbol{z}\in\bar{\mathcal{Z}}_{k},\forall
k\in\mathcal{K},$
$\displaystyle\boldsymbol{x}+\boldsymbol{y}_{k}\geq\boldsymbol{1},$
$\displaystyle\forall k\in\mathcal{K},$

where $\boldsymbol{z}\in\\{-1,0,1\\}^{2}$ and $\mathcal{K}=\\{1,2\\}$. We look
at three solutions for different groupings of
$\boldsymbol{z}_{1}=[0,0]^{\intercal}$,
$\boldsymbol{z}_{2}=[1,1]^{\intercal}$, and
$\boldsymbol{z}_{3}=[1,0]^{\intercal}$. One of them is not robust, and the
other ones are but have a different objective value due to the partition. The
first partition we consider is
$\bar{\mathcal{Z}}_{1}=\\{\boldsymbol{z}_{1}\\},\
\bar{\mathcal{Z}}_{2}=\\{\boldsymbol{z}_{2}\\}$. The corresponding solution is
$\theta^{*}=2$, $\boldsymbol{x}^{*}=[1,1]^{\intercal}$,
$\boldsymbol{y}^{*}_{1}=[1,1]^{\intercal}$, and
$\boldsymbol{y}^{*}_{2}=[0,0]^{\intercal}$. This solution is not robust, since
for $\boldsymbol{z}_{3}=[1,0]^{\intercal}$ the following constraint is
violated for all $k\in\mathcal{K}$:

$\boldsymbol{y}_{1}\ngeq\boldsymbol{1}-\boldsymbol{z}_{3}\iff\begin{bmatrix}1\\\
1\\\ \end{bmatrix}\ngeq\begin{bmatrix}1\\\ 1\\\
\end{bmatrix}-\begin{bmatrix}1\\\ 0\\\
\end{bmatrix},\qquad\boldsymbol{y}_{2}\ngeq\boldsymbol{1}-\boldsymbol{z}_{3}\iff\begin{bmatrix}0\\\
0\\\ \end{bmatrix}\ngeq\begin{bmatrix}1\\\ 1\\\
\end{bmatrix}-\begin{bmatrix}1\\\ 0\\\ \end{bmatrix}.\\\ $

Next, consider
$\bar{\mathcal{Z}}_{1}=\\{\boldsymbol{z}_{1},\boldsymbol{z}_{3}\\},\
\bar{\mathcal{Z}}_{2}=\\{\boldsymbol{z}_{2}\\}$, with solution $\theta^{*}=4$,
$\boldsymbol{x}^{*}=[0,1]^{\intercal}$,
$\boldsymbol{y}^{*}_{1}=[1,1]^{\intercal}$,
$\boldsymbol{y}^{*}_{2}=[1,0]^{\intercal}$. There is no $\boldsymbol{z}$ that
violates this solution, which makes it robust. The third partition is
$\bar{\mathcal{Z}}_{1}=\\{\boldsymbol{z}_{1}\\},\
\bar{\mathcal{Z}}_{2}=\\{\boldsymbol{z}_{2},\boldsymbol{z}_{3}\\}$, with
solution $\theta^{*}=3$, $\boldsymbol{x}^{*}=[1,0]^{\intercal}$,
$\boldsymbol{y}^{*}_{1}=[1,1]^{\intercal}$, and
$\boldsymbol{y}^{*}_{2}=[0,1]^{\intercal}$. This solution is also robust.
Their objective values are 3 and 4, which shows that different partitions can
significantly influence solution quality.

Mathematically, we formulate the subproblem using the big-$M$ reformulation:

$\displaystyle\max_{\zeta,\boldsymbol{z},\gamma}\quad$ $\displaystyle\zeta$
(5) s.t.
$\displaystyle\zeta\in\mathbb{R},\quad\boldsymbol{z}\in\mathcal{Z},\quad\gamma_{kl}\in\\{0,1\\},\quad(k,l)\in\mathcal{K}\times\mathcal{L},$
$\displaystyle\sum_{l\in\mathcal{L}}\gamma_{kl}=1,$ $\displaystyle\forall
k\in\mathcal{K},$
$\displaystyle\zeta+M(\gamma_{k0}-1)\leq\boldsymbol{c}(\boldsymbol{z})^{\intercal}\boldsymbol{x}^{*}+\boldsymbol{d}(\boldsymbol{z})^{\intercal}\boldsymbol{y}^{*}_{k}-\theta^{*},\qquad$
$\displaystyle\forall k\in\mathcal{K},$
$\displaystyle\zeta+M(\gamma_{kl}-1)\leq\boldsymbol{t}_{l}(\boldsymbol{z})^{\intercal}\boldsymbol{x}^{*}+\boldsymbol{w}_{l}(\boldsymbol{z})^{\intercal}\boldsymbol{y}^{*}_{k}-h_{l}(\boldsymbol{z}),$
$\displaystyle\forall l\in\mathcal{L},\forall k\in\mathcal{K},$

where $M$ is some big scalar and $\mathcal{L}$ is the index set of
constraints. When $\zeta\leq 0$, we have not found any violating scenario, and
the master solution is robust. Otherwise, the found $\boldsymbol{z}^{*}$ is
added to one of $\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{K}$. Then,
the master problem is re-solved, so that a new solution ($\theta^{*}$,
$\boldsymbol{x}^{*}$, $\boldsymbol{y}^{*}$), which is guaranteed to be
feasible for $\boldsymbol{z}^{*}$ as well, is found.

Throughout the process, the key issue is to which of
$\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{K}$ to assign
$\boldsymbol{z}^{*}$. As this cannot be determined in advance, all options
have to be considered. Figure 2 illustrates that from each tree node we create
$K$ child nodes, each corresponding to adding $\boldsymbol{z}^{\ast}$ to the
$k$-th subset:

$\tau^{k}=\\{\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{k}\cup\\{\boldsymbol{z}^{*}\\},\ldots,\bar{\mathcal{Z}}_{K}\\},\quad\forall
k\in\mathcal{K},$

where $\tau^{k}$ is the partition corresponding to the $k$-th child node of
node $\tau$. If a node is found such that $\theta^{*}$ is greater than or
equal to the value of another robust solution, then this branch can be pruned
as the objective value of the master problem cannot improve if more scenarios
are added.

The pseudocode of $K$-B&B is given in Algorithm 2 in the Appendix. The tree
becomes very deep for 2SRO problems where many scenarios are needed for a
robust solution. Moreover, the tree becomes wider when $K$ increases. Due to
these issues, solving the problem to optimality becomes computationally
intractable in general. Our goal is to investigate if ML can be used to make
informed decisions regarding the assignment of newly found
$\boldsymbol{z}^{*}$ to the discrete subsets, so that a smaller search tree
has to be explored in a shorter time before a high-quality robust solution is
found.

##  3 ML methodology

We propose a method that enhances the node selection strategy of the $K$-B&B
algorithm. It relies on four steps:

  1. 1.

Decision on what and how we want to predict: Section 3.1.

  2. 2.

Feature engineering: Section 3.2.

  3. 3.

Label construction: Section 3.3.

  4. 4.

Using partial $K$-B&B trees for training data generation: Section 3.4.

All these steps are combined into the $K$-B&B-NodeSelection algorithm (Section
3.5).

###  3.1 Learning setup

As there is no clearly well-performing node selection strategy for $K$-B&B, we
cannot simply try to imitate one. Instead, we investigate what choices a good
strategy would make. We will focus on learning how to make informed decisions
about the order of inspecting the children of a given node. The scope of our
approach is illustrated with rounded-square boxes in Figure 3.

Figure 3: The scope of node selection

To rank the child nodes in the order they ideally be explored, one of the ways
is to have a certain form of child node information whether selecting this
node is _good_ or _bad_. In other words, how likely is a node to guide us
towards a high-quality robust solution fast. Indeed, this shall be exactly the
quantity that we predict with our model. To train such a model, we will
construct a dataset consisting of the following input-output pairs:

  * •

Input: feature vector $F$ of the decision to insert a scenario to a subset
(Section 3.2)

  * •

Output: $[0,1]$ label that informs how good a given insertion was, based on an
ex-post constructed strategy; ‘what would have been the best node selection
strategy, had we known the entire tree?’ (Section 3.3).

We gather this data by creating a proxy for an oracle (see Section 3.4). Once
the predictive model is trained, we can apply it to the search tree where in
each iteration we predict for all $K$ child nodes a score $\mu$, in the
interval $[0,1]$. The child node with the highest score is explored first (see
Figure 4).

Figure 4: Node selection with ML predictions. Node selections are decided by
the prediction of the function $\mu$ with input features $F_{n}^{k}$, where
$n$ is the node from which a selection is made and $k$ relates to its $k$-th
child node.

Formally, the working order of the trained method shall be as follows:

  1. 1.

Process node.  Solve master and subproblem in current node $n$. If prune
conditions hold, then select a new node. Otherwise, continue to Step 2.

  2. 2.

Compute features.  For each one of the $K$ child nodes, generate a vector of
features $F^{1}_{n},\ldots,F^{K}_{n}$ (see Section 3.2 for details).

  3. 3.

Predict.  For each child node $k$, predict the goodness score
$\mu(F^{k}_{n})$.

  4. 4.

Node selection.  Select the child node with the highest score.

It is desirable for an ML tool to be applicable to data that is different from
the one which it is trained on. In the context of an ML model constructed to
solve optimization problems, this means the potential to use a given trained
method on various optimization problems of various sizes, with different
values of $K$. Indeed, we shall demonstrate the generality of our method.
First, we note that each parent-child node pair corresponds to one data point,
and hence, training on a problem with a certain $K$ does not prevent us from
using it for different $K$. Next, we construct our training dataset so that
the model becomes independent of (i) the instance size, and (ii) the type of
objective function and constraints. This will be explained in Section 3.2.

###  3.2 Feature engineering

If we take a look at a single rounded box in Figure 3, the ML model we are
about to train is going to give a goodness score which will depend on the
parent node and the scenario. Therefore, we need to design features which we
group into (i) state features that describe the master problem and the
subproblem solved in the parent node, (ii) scenario features that describe the
assignment of a newly-found scenarios to one of the subsets
$\bar{\mathcal{Z}}_{k}$. In what follows, we present the feature list:

  1. 1.

State features. This input describes the parent node $n$, i.e., the current
state of the algorithm. Different states might benefit from different
strategies. Hence, information on the current node might increase the
prediction performance. This also means that all the child nodes have the same
state features: $\boldsymbol{s}_{n}^{k}=\boldsymbol{s}_{n}$ for all
$k\in\mathcal{K}$. To scale the features, we always initialize a tree search
with a so-called _initial run_. This is a dive with random child-node
selections, where we stop until robustness is reached. The following values
are taken from this initial run:

     * •

$\theta^{0}$: objective of the robust solution found in the initial run.

     * •

$\zeta^{0}$: the violation of the root node.

     * •

$\kappa^{0}$: depth reached in the initial run.

In the experiments, multiple initial runs are done. The averages of
$\theta^{0}$, $\zeta^{0}$, and $\kappa^{0}$ over the dives are then used for
scaling.

  2. 2.

Scenario features. Intuitively, scenarios contained in the same group should
have similar characteristics. Therefore, the features for each node are
constructed in the following way: each newly found scenario
$\boldsymbol{z}^{*}$ is assigned a set of characteristics, or attributes.
Based on the attributes of the new scenario, and the attributes of the
scenarios already grouped into the $K$ subsets, we formulate the input of one
data point. Some of the scenario attributes can be directly determined from
the master problem. Others are extracted from easily solvable optimization
problem: the deterministic problem and the static problem. The deterministic
problem is a version of the problem where $\boldsymbol{z}^{*}$ the only
scenario. For the static problem, we first solve for a single $\boldsymbol{y}$
(no adaptability) for all $\boldsymbol{z}\in\mathcal{Z}$. Then, for the
obtained $\boldsymbol{x}^{*}$ and for a given $\boldsymbol{z}^{*}$, we solve
for the best $\boldsymbol{y}$.

As our goal is to use the model also on different problems, we engineer the
features to keep them independent from the problem size or type. In Tables
1-2, we give an outline of the two feature types that we construct. For a
detailed description of how they are computed, we refer the reader to Appendix
A.

Table 1: State features. $\theta^{0}$, $\zeta^{0}$, and $\kappa^{0}$ are as defined above. $\theta^{p}$ is the objective value of the parent node, $\zeta^{p}$ is the violation of the parent node, and $\kappa$ is the depth of the current node. Num. | State feature name |  Description | Calculation
---|---|---|---
1 | Objective |  Relative objective values of this node to the first robust solution | $\theta/\theta^{0}$
2 | Objective difference |  Difference of objective w.r.t. the parent node | $\theta/\theta^{p}$
3 | Violation |  Relative violation with respect to the first violation found | $\zeta/\zeta^{0}$
4 | Violation difference |  Difference of violation w.r.t. the parent node | $\zeta/\zeta^{p}$
5 | Depth |  Relative depth of this node to the depth of the fist robust solution | $\kappa/\kappa^{0}$
Table 2: Attributes assigned to scenario $\boldsymbol{z}^{*}$. | Num. | Attribute name |  Description
---|---|---|---
| 1 | Scenario values |  Vector of scenario values $\boldsymbol{z}^{*}$
Master problem | 2 | Constraint distance |  A measure for the change of the feasibility region when $z^{*}$ is added to a subset. We look at the distance between the constraints already in the master problem, and the one to be added.
3 | Scenario distance |  With this attribute we measure how far away $\boldsymbol{z}^{*}$ is from not being a violating scenario, for each of the $k$ subsets. This is done by looking at the constraints in the space of $\mathcal{Z}$, given the current solutions $\boldsymbol{x}$ and $\boldsymbol{y}^{k}$.
| 4 | Constraint slacks |  The slack values of the uncertain constraint per subset decisions.
Deterministic problem | 5 | Objective function value |  The objective function value of the deterministic problem
6 | First-stage decisions |  First-stage decisions of deterministic problem
| 7 | Second-stage decisions |  Second-stage decisions of deterministic problem
Static problem | 8 | Objective function value |  The objective function value of the static problem
9 | second-stage decisions |  Second-stage decisions of static problem

The state features in Table 1 are readily problem-independent. However, this
is not the case for the scenario attributes in Table 2. They are, for example,
dependent on the instance size. Moreover, in node selection, we place the new
scenario to a group of other scenarios. Therefore, additional features are
constructed to describe the relation of the new scenario to the current
scenarios, computed as the _attribute distance_ :

$\delta^{k}_{f}=\frac{\lVert\boldsymbol{a}^{k,\boldsymbol{z}^{*}}_{f}-\frac{1}{|\bar{\mathcal{Z}}_{k}|}\sum_{\boldsymbol{z}\in\bar{\mathcal{Z}}_{k}}{\boldsymbol{a}_{f}^{k,\boldsymbol{z}}}\rVert_{2}}{|\boldsymbol{a}^{k,\boldsymbol{z}^{*}}_{f}|},\qquad\forall
k\in\mathcal{K},\forall f\in\\{1,\ldots,9\\},$ (6)

where $\delta_{f}^{k}$ is the attribute distance of the new scenario
$\boldsymbol{z}^{*}$ to subset $\bar{\mathcal{Z}}_{k}$ and
$\boldsymbol{a}_{f}^{k,\boldsymbol{z}}$ is the data vector related to the
$f$-th attribute (of Table 2) for the $k$-th child node. Then, the _scenario
feature_ vector of the $k$-th child node is defined as
$\boldsymbol{d}^{k}_{n}=[\delta^{k}_{1},\ldots,\delta^{k}_{9}]^{\intercal}$.
The dimension of $\boldsymbol{a}^{k,\boldsymbol{z}}_{f}$ depends on $f$. For
instance, for attribute 1 (scenario values),
$\dim(\boldsymbol{a}_{\boldsymbol{z}}^{1})=\dim(\boldsymbol{z})$. For
attribute 4 (constraint slacks), the dimension depends on the number of
uncertain constraints in the problem. By using (6), the features per data
point are independent of the instance size and the problem-specific
properties. Then, the input of the ML model for the $k$-th child of node $n$
is given by
$F^{k}_{n}=[\boldsymbol{s}_{n}\quad\boldsymbol{d}_{n}^{k}]^{\intercal}$.

In Figure 5 we outline the feature generation procedure. Steps 2 and 5
indicate how new attributes need to be generated for every child node. In
practice many attributes are the same for all subsets, and the attributes that
do differ are the master problem-based ones, which are easily computed.

Figure 5: Example of a feature generation procedure for node $n$ and its two
child nodes.

###  3.3 Label construction

To learn how to assign a new scenario to one of the subsets
$\bar{\mathcal{Z}}_{k}$, we need another piece of the input-output pairs in
our database – labels that would indicate how good, ex post, it was to perform
a given assignment, i.e., how likely a given assignment is to lead the search
strategy towards a _good solution_. We shall assume that given a $K$-B&B tree,
a good solution is a robust solution with objective that belongs to the best
$\alpha\%$ of the found robust solutions. We will now introduce a notion of
scenario-to-set assignments and illustrate a method of constructing labels
$q$.

We define $p_{\nu}$ – the probability of node $\nu$ leading to a good robust
solution. If this node is selected, one of a finite, possibly large, number of
_leaves_ (i.e., terminal nodes) is reached with depth-first search. Then,
taking $g_{\nu}$ to be the number of good solutions and $M_{\nu}$ as the
number of leaves under node $\nu$, we define $p_{\nu}=g_{\nu}/M_{\nu}$ as the
fraction of leaves with a good robust solution. We define a node $\nu$ as good
if the probability $p_{\nu}$ of it leading to a good robust solution is higher
than some threshold $\epsilon$. This is computed by the quality value
$q_{\nu}=\boldsymbol{1}_{\\{p_{\nu}\geq\epsilon\\}}$.

######  Example 3.1.

Consider the tree in Figure 6. For three nodes in the search tree, its subtree
(consisting of all its successors) and leaves (coloured nodes) are shown. Red
coloured nodes represent bad and green nodes represent good robust solutions.
Then, if we pick $\epsilon=\frac{1}{5}$ as threshold, the corresponding
success probabilities $p_{\nu}$ and the quality values of the three nodes are:

$p_{1}=\frac{1}{4},\ p_{2}=0,\ p_{3}=\frac{2}{5},\
q_{1}=\boldsymbol{1}_{\\{p_{1}\geq\frac{1}{5}\\}}=1,\
q_{2}=\boldsymbol{1}_{\\{p_{2}\geq\frac{1}{5}\\}}=0,\
q_{3}=\boldsymbol{1}_{\\{p_{3}\geq\frac{1}{5}\\}}=1.$

The first and third the nodes would have been good node selections, whereas
the second selection would have been a bad one.

Figure 6: Example of a tree where three nodes are considered. The coloured
nodes are leaves; green and red nodes are good and bad robust solutions,
respectively.

In practice, we do not know for a node $\nu$ how many underlying leaves are
good and bad. This is the reason that in this method we will predict $q_{\nu}$
with a model $\mu$. We will also call this model the strategy model (or
function) since it guides us in making node selections.

###  3.4 Training data generation

Our goal is to learn a supervised ML model $\mu(F_{\nu})=\hat{q}_{\nu}$, where
$\mu$ is the strategy function, $F_{\nu}$ the input features, and
$\hat{q}_{\nu}$ the prediction of the quality of moving to node $\nu$. To
train this model, we first need to generate training data. Given a single
tree, the difficulty of generating data does not lie in the input, but in the
output: an expert is needed to determine the correct values of $\hat{q}_{\nu}$
for its nodes. Consider the following; if nodes of the entire tree are
_processed_ (i.e., solving the master problem and the subproblem), we could
easily find the paths from the root to good solutions. Then, all the nodes in
these paths would get the values $\hat{q}_{\nu}=1$, and all others
$\hat{q}_{\nu}=0$. Or equivalently, the success probabilities would be set to
$p_{\nu}>\epsilon$. Since the trees grow exponentially, this approach is not
practical.

As already mentioned in the introduction, a popular method for exploring
intractable decision trees is Monte Carlo tree search (MCTS) (Browne et al.,
2012). By randomly running deep in the tree, we can gather information on the
search space. In our method, we use the idea of random runs to mimic an
expert, and hence, label the data points. Generating training data is done as
follows (see Figure 7):

  1. 1.

Get instance.  Generate an instance of a 2SRO problem.

  2. 2.

Initial run.  One (or multiple) dives are executed to gather feature
information.

  3. 3.

Initialize search tree.  Process all nodes up to a predetermined level $L$ of
the tree. Generate features for each of the explored nodes.

  4. 4.

Downward pass.  Per node $\nu\in\\{1,\ldots,N_{L}\\}$ of the $L$-th layer
($N_{l}$ is the number of nodes of the $l$-th layer), perform dives for a
total of $R$ times.

  5. 5.

Probability of bottom nodes.  Set probability $p_{L,\nu}$ of each node
$\nu\in\\{1,\ldots,N_{L}\\}$ in layer $L$ as $p_{L,\nu}=\frac{g_{\nu}}{R}$
where $g_{\nu}\in\\{0,\ldots,R\\}$ is the number of good solutions from the
samples of the $\nu$-th node in layer $L$.

  6. 6.

Upward pass.  Propagate the probabilities $p_{l,\nu}$ upwards through the
tree, for all nodes $\nu\in\\{1,\ldots,N_{l}\\}$, for all levels
$l\in\\{L-1,\ldots,2\\}$, as follows:

$\displaystyle p_{l,\nu}$ $\displaystyle=\mathbb{P}(\text{at least one child
node is successful})$ $\displaystyle=1-\mathbb{P}(\text{no successful child
nodes})$ $\displaystyle=1-\prod_{k\in\mathcal{K}}(1-p^{k}_{l,\nu}),$

where $p^{k}_{l,\nu}$ is the $k$-th child of node $\nu$ of layer $l$ (while
this child node is in the ($l+1$)-th level). Note that
$p^{k}_{l,\nu}=p_{l+1,\nu^{\prime}}$ for some $\nu\in\\{1,\ldots,N_{l}\\}$ and
$\nu^{\prime}\in\\{1,\ldots,N_{l+1}\\}$.

  7. 7.

Label nodes:  Determine the label $\hat{q}_{l,\nu}$ for nodes
$\nu\in\\{1,\ldots,N_{l}\\}$ for levels $l\in\\{2,\ldots,L\\}$.

Figure 7: Downward and upward pass for generating training data. The blue
layer represents the $L$-th layer in the tree from which random runs are made.

The advantage of this structure is that both bad and good decisions are well
represented in the dataset. However, it only consists of input-output pairs of
the top $L$ levels. This is not necessarily a disadvantage as good decisions
at start can be expected to be more important. The above generation method is
applied per instance, thus it can be parallelized, like Step 4.

###  3.5 Complete node selection algorithm

We now combine all the steps above into one algorithm which is, essentially, a
variant of $K$-B&B enhanced with: (i) node selection, (ii) feature
engineering, and (iii) training data generation (see Algorithm 1). Our
$K$-B&B-NodeSelection algorithm has two preprocessing steps:

  1. 1.

StrategyModel (Procedure 3 in the Appendix): Generate the data applying 1-4,
and train the ML model.

  2. 2.

InitialRun (Procedure 4 in the Appendix): Start with a random dive through the
tree to obtain $\theta^{0},\zeta^{0}$, and $\kappa^{0}$ used to scale the
features (see Table 1).

Input : Test instance $\mathcal{P}^{test}(N^{test})$, train instances
$\mathcal{P}_{1}^{train}(N^{train}),\ldots,\mathcal{P}_{I}^{train}(N^{train})$

number of partitions for training $K^{train}$ testing $K^{test}$, level for
training $L^{train}$ and testing

$L^{test}$, quality threshold $\epsilon$, number of random dives per node $R$

Output : Objective value $\theta$, first-stage decisions $\boldsymbol{x}$,
second-stage decisions
$\boldsymbol{y}=\\{\boldsymbol{y}_{1},\ldots,\boldsymbol{y}_{K}\\}$,

subsets with scenarios $\bar{\mathcal{Z}}_{k}$ for all $k\in\\{1,\ldots,K\\}$

Initialization : Incumbent partition: $\tau^{i}\mathrel{\mathop{\mathchar
58\relax}}=\\{\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{K}\\}$, where
$\bar{\mathcal{Z}}_{k}=\emptyset$ for all $k\in\mathcal{K}$,

set containing all node partitions yet to explore:
$\mathcal{N}\mathrel{\mathop{\mathchar 58\relax}}=\\{\tau^{i}\\}$,

initial incumbent solution:
$(\theta^{i},\boldsymbol{x}^{i},\boldsymbol{y}^{i})\mathrel{\mathop{\mathchar
58\relax}}=(\infty,\emptyset,\emptyset)$

// Preprocessing

$\textit{model}\leftarrow\textsc{StrategyModel}(\mathcal{P}_{1}^{train}(N^{train}),\ldots,\mathcal{P}_{I}^{train}(N^{train}),K^{train},L^{train},\epsilon,R)$

// using Procedure 3

$\textit{scaling
info}\leftarrow\textsc{InitialRun}(\mathcal{P}^{test}(N^{test}),K^{test})$

// using Procedure 4

// Tree search

1 while  _$\mathcal{N}$ not empty_ do

2 if  _no solution yet or previous node pruned_ then

3 Select a random node with partition
$\tau=\\{\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{K}\\}$ from
$\mathcal{N}$, then $\mathcal{N}\leftarrow\mathcal{N}\setminus\\{\tau\\}$

4 else

5 $\tau\mathrel{\mathop{\mathchar
58\relax}}=\\{\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{k^{*}}\cup\\{\boldsymbol{z}^{*}\\},\ldots,\bar{\mathcal{Z}}_{K}\\}$

6 end if

7 $(\theta^{*},\boldsymbol{x}^{*},\boldsymbol{y}^{*})\leftarrow\textit{master
problem}(\tau)$

8 if  _$\theta^{*} >\theta^{i}$_ then

9 Prune tree since current objective is worse than best solution found,
continue to line 1.

10

11 end if

12
$(\boldsymbol{z}^{*},\zeta^{*})\leftarrow\textit{subproblem}(\theta^{*},\boldsymbol{x}^{*},\boldsymbol{y}^{*})$

13 if  _$\zeta^{*} >0$_ then

14 Solution not robust. Create $K$ new branches.

15 if  _current level is more than $L^{test}$_ then

16 $k^{*}\leftarrow\textit{random uniform sample}([1,K])$

17

18 else

19 Create feature vectors for $K$ child nodes.

$(D_{1},\ldots,D_{K})\leftarrow\textit{generate features}(\textit{scaling
info},\theta,\zeta)$

// using steps of Section 3.2

20 $k^{*}\leftarrow\textit{predict node
qualities}(D_{1},\ldots,D_{K},\textit{model})$

21 end if

22 Make $K$ new branches, of which the $k^{*}$-th is selected.

23 for  _$k\in\\{1,\ldots,K\\}\setminus\\{k^{*}\\}$_ do

24 $\tau^{k}\mathrel{\mathop{\mathchar
58\relax}}=\\{\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{k}\cup\\{\boldsymbol{z}^{*}\\},\ldots,\bar{\mathcal{Z}}_{K}\\}$

25 $\mathcal{N}\leftarrow\mathcal{N}\cup\\{\tau^{k}\\}$

26 end for

27

28 else

29 Current solution robust, prune tree.

30
$(\theta^{i},\boldsymbol{x}^{i},\boldsymbol{y}^{i},\tau^{i})\leftarrow(\theta^{*},\boldsymbol{x}^{*},\boldsymbol{y}^{*},\tau)$

31 end if

32

33 end while

return _$(\theta^{i},\boldsymbol{x}^{i},\boldsymbol{y}^{i},\tau^{i})$_

Algorithm 1 $K$-B&B-NodeSelection

##  4 Experiments

We now investigate if it is possible to learn a node selection strategy that
generalizes (i) to other problem sizes, (ii) to different values of $K$, and
(iii) to various problems. We answer this question by a detailed study of two
problems: capital budgeting (with loans) and shortest path (Subramanyam et
al., 2020), whose formulations are given in Appendix C. This section is set up
as follows: First, the effectiveness of the original $K$-B&B is tested on the
problems. Then, we compare $K$-B&B to $K$-B&B-NodeSelection. We shall observe
that the results obtained with our approach are very promising.

For solving the MILPs, Gurobi 9.1.1 (Gurobi Optimization, 2020) is used. All
computations of generating training data, $K$-B&B, and $K$-B&B-NodeSelection
are performed on an Intel Xeon Gold 6130 CPU @ 2.1 GHz with 96 GB RAM.
Training of the ML model is executed on an Intel Core i7-10610U CPU @ 1.8 GHz
with 16 GB RAM. Our implementation along with the scripts to reproduce our
results are availabel online 111The Python code can be found at
https://github.com/estherjulien/KAdaptNS.

###  4.1 Performance of $K$-B&B

In our experiments, we investigate the potential of improving the node
selection strategy with ML. For that reason, it is important to identify
problems on which such an improvement matters, i.e., where different
partitions give varying outcomes and are nontrivial. To identify such
problems, we run $K$-B&B on several problems. Compared to the algorithm in
Subramanyam et al. (2020), we made some minor changes in $K$-B&B:

  * •

Instead of breadth-first search, depth-first dives are performed with random
node selection.

  * •

In the starting node selection step (Step 2, Algorithm 2), a random node is
taken from $\mathcal{N}$ instead of the first one.

The quantity we are interested in is the relative change in the objective
function value (OFV) – the OFV of the first robust solution divided by the
best one after 30 minutes. The higher the value, the more potential for a
smart node selection strategy.

First, we consider the capital budgeting and the shortest path problems, only
mentioned now and formally described later, for which the results are in
Figure 8. We observed that the objective function values of the capital
budgeting instances are changing more than those of shortest path (in which
nodes of a graph are located on a 2D plane). This is why we implemented
another instance type for shortest path: graph with nodes located on a 3D
sphere (See Appendix C.2). The OFV differences for these instances are still
smaller than those of capital budgeting, but more than for the ‘normal’ type.
Therefore, further experiments on shortest path were conducted with the sphere
instances alone.

(a)

(b)

(c)

Figure 8: Objective function value (OFV) difference (in $\%$) for capital
budgeting and shortest path with ‘normal’ and ‘sphere’ instances, within 30
minutes using $K$-B&B. For each problem type, experiments were done for 100
instances per $K\in\\{2,\ldots,6\\}$ and instance size. The $75\%$ confidence
interval (CI) is also given as shaded strips along the curves.

Another problem on which we ran $K$-B&B was the knapsack problem parameterized
by the combination of the capacity ($c$), the number of items ($N_{ks}$), and
the maximum deviation of the profit of items (i.e., the uncertainty parameter
$\gamma$). For this problem, we considered instances of a similar size as the
earlier problems, fixing $K=4$ and $N_{ks}=100$, and tested $K$-B&B on 16
instances for all combinations of $c\in\\{0.05,0.15,0.35,0.5\\}$ and
$\gamma\in\\{0.05,0.15,0.35,0.5\\}$. The OFV differences (in percentages) are
given in Table 3, where it is visible that different partitions barely play a
role. Any random robust solution seems to be performing well. Thus, node
selection will most likely not enhance $K$-B&B for knapsack and will therefore
not be tested.

Table 3: The OFV difference (in $\%$) of the knapsack problem, within 30 minutes, for different values of the capacity ($c$) and uncertainty ($\gamma$) parameters. $K=4$ and $N=100$ are fixed. $c$ |  | $\gamma$
---|---|---
|  | 0.05 | 0.15 | 0.35 | 0.5
0.05 |  | 0.002 | 0.086 | 0.000 | 0.000
0.15 |  | 0.002 | 0.011 | 0.040 | 0.000
0.35 |  | 0.001 | 0.001 | 0.019 | 0.038
0.5 |  | 0.001 | 0.003 | 0.012 | 0.027

Solving problem instances with $K$-B&B takes a long time, where we have to
think in the range of multiple hours until optimality is proven. This also
holds for small size instances. After having studied the convergence over
runtime, we have fixed the time limit to 30 minutes for all the problem
instances. For capital budgeting with $(N,K)=(10,2)$ all instances could be
solved within 30 minutes. For the same instance size and $K=3$, $25$ out of
$100$ are solved, only one for $K=4$, and none for larger $K$. For the 3D
shortest path problem with the smallest instance size and $K=2$, only six
instances are solved.

###  4.2 Experimental setup $K$-B&B-NodeSelection

In our experiments, we also investigate what would be a good node selection
strategy in $K$-B&B that would perform well after it is trained on a selection
of problems and then applied to other problems. Naturally, we are interested
in generalization of trained tools to different instance sizes, $K$, and
problem types. To this end, we have performed an ablation-study described in
Table 4, where each row informs about the similarity of the testing problem
instances, compared to the training ones.

Table 4: Different types of experiments (EXP), where the instance size $N$, $K$, and the problem itself can be different for training and testing. Type | Instance size $N$ | $K$ | Problem
---|---|---|---
EXP1 | Same | Same | Same
EXP2 | Same | Different | Same
EXP3 | Different | Same | Same
EXP4 | Different | Different | Same
EXP5 | Different | Same | Different
EXP6 | Different | Different | Different

The problems we study are the capital budgeting problem with loans (See C.1)
and the shortest path problem on a sphere (See C.2). We now describe the
design choices we made regarding the ML model and data generation. As our
focus lies in how ML is used for optimization and not in differences between
ML models, we select a frequently-used model: random forest of scikit-learn
(Pedregosa et al., 2011) with default settings. We note that the training
times do not exceed a couple of minutes for different data sets.

As for the data generation process, it is governed by StrategyModel (Procedure
3), driven by the following parameters: $I$ (number of training instances),
$L^{train}$ (depth level used in training data), and $R$ (number of dives per
node). In these experiments, we instead made them depend on $T$ – the total
duration in hours, and $\iota$ – the time per training instance in minutes.
First, we set $I=60T/\iota$. Selection of the right $L^{train}$ value is more
challenging since for some problem instances the master problem takes a lot
more time or deep trees are needed. Therefore, to get sufficiently many random
dives for each node in $L^{train}$ within the time limit $\iota$, we make
$L^{train}$ depend negatively on the total duration of the initial run
(InitialRun, Procedure 4). This means that if a random dive takes a long time,
the number of starting nodes should be lower, and therefore, the value of
$L^{train}$ should also decrease. Finally, the number of dives per node ($R$)
depends on how many nodes we have in level $L^{train}$ and the time we have
for the instance ($\iota$).

First, the experiments of EXP1-EXP4 are run on the capital budgeting and
shortest path problem. Then, the experiments where the training and testing
problems are mixed, are conducted (EXP5 and EXP6). We only discuss a
representative selection of the results in the main body, referring the reader
to the Appendix for a complete overview. Finally, we discuss the feature
importance scores we obtained with our random forests.

###  4.3 Capital budgeting

The capital budgeting problem is a 2SRO problem where investments in a total
of $N_{cb}$ projects can be made in two time periods. In the first period, the
cost and revenue of these projects are uncertain. In the second period, these
values are known but an extra penalty needs to be paid for postponement. The
MILP formulation of capital budgeting has uncertain objective function, fixed
number of uncertain constraint, and the dimension of $\mathcal{Z}$ is fixed to
4 for all instance sizes. For the full description, see Section C.1. Recall
that $K$-B&B-NodeSelection takes more parameters than the ones being tested in
the ablation study: $L^{test}$ (level up to where node selection is
performed), $\epsilon$ (node quality threshold), and $T$ and $\iota$ for
generating training data. These parameters will be tuned in the first part of
the experiments.

#### Parameter tuning (with EXP1).

For this type of experiments, we use the same $K$ and $N$ for testing and
training, applied to the smallest instance size: $N_{cb}=10$, but for all
$K\in\\{2,3,4,5,6\\}$. For different values of $K$, we noticed that different
hyperparameters for generating training data were performing well. In Appendix
D.1, we tuned the parameter $\iota$ (minutes spend per training instance)
based on the number of data points obtained in total, together with some other
information. The testing accuracy scores for different data sets we trained
on, range between 0.92-0.99 (see Table 6 in the Appendix).

We next tune the values of $L^{test}$ (level up to which node selection is
performed) and $\epsilon$ (quality threshold) using the sets
$L^{test}\in\\{5,10,20,30,40,50\\}$ and
$\epsilon\in\\{0.05,0.1,0.2,0.3,0.4\\}$. Since there are 30 combinations per
$K$ value, we only considered $K=6$. The results are shown in Figure 9, where
using a low value for $\epsilon$ and high $L^{test}$ gives the best results
for both values of $K$. In fact, when a node $n$ has success probability
$p_{n}$ larger than zero, this is already considered a good quality node. For
further experiments of capital budgeting, we fix $\epsilon=0.05$. Since high
values of $L^{test}$ outperform lower ones, we also consider the possibility
of applying the strategy always ($L^{test}=\infty$), with fixed
$\epsilon=0.05$. This option is analyzed in Appendix D.1. We noticed that
choosing $L^{test}=\infty$ performs well for $K=6$ but for lower values of
$K$, choosing $L^{test}=40$ gives even better solutions. Therefore, we
continue with $L^{test}=40$.

Figure 9: Results of $K$-B&B with random dives and $K$-B&B-NodeSelection with
combinations of $K$, $L^{test}$ and $\epsilon$. The plots show the average
relative objective value over runtime of 100 instances for the capital
budgeting problem, for $N=10$.

Another important parameter is the number of hours spend on generating
training data ($T$). In Figure 10, results are shown for $T\in\\{1,2,5,10\\}$
and $K\in\\{3,4,5,6\\}$. Note that only for $K=3$ higher values of $T$ result
in a better performance of $K$-B&B-NodeSelection. For the other values of $K$
the performance is similar, or even worse, for higher values of $T$ compared
to lower ones. For further experiments, we shall use $T=2$.

Figure 10: Results of $K$-B&B with random dives and $K$-B&B-NodeSelection with
combinations of $K$ and $T$. The plots show the average objective over runtime
of 100 instances for the capital budgeting problem, for $N=10$.

EXP1 and EXP2 results. For EXP1, the results for
$K^{train}=K^{test}\in\\{3,4,5\\}$ are shown in Figure 11 in the Appendix. As
in Figure 8, the shaded strips around the solid curves show the confidence
interval. We can see that $K$-B&B-NodeSelection outperforms $K$-B&B for all
$K$. Moreover, the convergence is steeper: good solutions are found earlier.
For $K\in\\{4,5\\}$ the final solution is also better when node selection is
guided by ML predictions. Then for EXP2, where we also apply ML models that
are trained with $K^{train}\neq K^{test}$, we see the performance of
$K$-B&B-NodeSelection improving when $K^{train}$ increases. This indicates
that data obtained with higher values of $K^{train}$ are more informative than
those with lower values. See Figure 12 for an illustration with $K^{test}=5$
and $K^{train}\in\\{4,5,6\\}$.

Figure 11: EXP1 results for $K^{train}=K^{test}\in\\{3,4,5\\}$ Figure 12: EXP2
results for $K^{test}=5$ and $K^{train}\in\\{4,5,6\\}$.

EXP3 and EXP4 results. In Figure 13, we depict the results for experiments
with same $K$ but different instance sizes. There, $K$-B&B-NodeSelection
performs better, but the confidence interval of $N^{test}=30$ is larger than
that of $N^{test}=10$. This suggests that testing on higher values of $N$
gives rise to a higher risk. Testing on higher instance sizes for different
values of $K$ (Figure 14) has a similar effect as before: higher values of
$K^{train}$ result in a better performance, although marginally for some
parameter combinations.

Figure 13: EXP3 results for $K^{train}=K^{test}\in\\{3,4,5\\}$ and
$N^{test}\in\\{20,30\\}$. Figure 14: EXP4 results for $K^{test}=5$,
$K^{train}\in\\{4,5,6\\}$, and $N^{test}\in\\{20,30\\}$.

###  4.4 Shortest path on a sphere

The shortest path problem can be described as a 2SRO problem where we make the
planning of a route from source to target, for which the lengths of the
$N_{sp}$ arcs are uncertain. This problem only has second-stage decisions and
uncertain objective. The dimension of the uncertainty set grows with the
number of arcs in the graph. For the full description, see Section C.2. Since
there is only a second-stage, some attributes disappear for this problem:
‘Deterministic first-stage’ (attribute 6), and the static objective problem-
related attributes (8 and 9). Hence, we are left with six attributes for this
problem.

#### Parameter tuning (with EXP1).

As we did for the capital budgeting problem, we first tune the parameter
$\iota$. The details of this parameter tuning are given in Appendix D.2. The
testing accuracy scores for different data sets we trained on is lower than
for capital budgeting; between 0.88-0.97 (see Figure 6). Since the
distribution of the probability success values $p_{n}$ is very similar as for
the capital budgeting problem (see Figure 26), the quality threshold is set to
$\epsilon=0.05$. In Figure 15, the level is tested again with
$L^{test}\in\\{5,10,20,40,\infty\\}$. Here we see that especially for smaller
values of $K$, a higher level of $L^{test}$ outperforms others. Therefore, we
choose $L^{test}=\infty$ for the remainder of the experiments.

Figure 15: Results of $K$-B&B with random dives and $K$-B&B-NodeSelection with
combinations of $K$ and $T$. The plots show the average objective over runtime
of 100 instances for the shortest path problem, for $N=20$.

Also note that when $K$ grows, the performances of $K$-B&B and
$K$-B&B-NodeSelection are very similar. For the shortest path problem, we
noticed that more training data points led to a substantial performance gain.
See Figure 16 for these results. Therefore, for EXP1-EXP4, we choose $T$ for
each $K$ separately. For an overview of which parameters are chosen per $K$;
see Table 9 in the Appendix.

Figure 16: Results of $K$-B&B with random dives and $K$-B&B-NodeSelection with
combinations of $K$ and $T$. The plots show the average objective over runtime
of 100 instances for the shortest path problem, for $N=20$.

EXP1 and EXP2 results. As is visible from Figure 17, even though no better
solutions are found (probably because the optimal solution is found early on),
it is still noticeable that $K$-B&B-NodeSelection converges faster than
$K$-B&B. This phenomenon is thus consistent over the two problems. The
convergence of $K$-B&B over different values of $K^{test}$ differs
significantly (e.g compare $K^{test}$ is 3 to 5). The convergence of
$K$-B&B-NodeSelection is however quite stable across different values of
$K^{test}$. Then, for EXP2, in Figure 18, we see that for $K^{test}=4$,
$K^{train}=6$ performs best. This also holds for other values of $K^{test}$,
just as it did for the capital budgeting problem.

Figure 17: EXP1 results for $K^{train}=K^{test}\in\\{3,4,5\\}$. Figure 18:
EXP2 results for $K^{test}=4$ and $K^{train}\in\\{3,4,6\\}$.

EXP3 and EXP4 results. We see in Figure 19 that the two algorithms behave very
similar. The confidence interval of $K$-B&B-NodeSelection also grows with
$N^{test}$. However, this does not necessarily mean that testing and training
on different sizes is not stable: the CI of $K$-B&B is also bigger. Moreover,
the CI is mostly in the region below one, which indicates that we mainly have
well performing outliers. In Figure 20, we see that for $N^{test}=40$,
$K^{train}=6$ also performs best, but not necessarily for the biggest instance
size.

Figure 19: EXP3 results for $K^{train}=K^{test}\in\\{3,4,5\\}$ and
$N^{test}\in\\{40,60\\}$. Figure 20: EXP4 results for $K^{test}=4$,
$K^{train}\in\\{3,4,6\\}$, and $N^{test}\in\\{40,60\\}$.

###  4.5 Training and testing on different problems

In this section we run EXP5 and EXP6, where we apply the node selection
strategy to a different problem than it has been trained on. Note that the
shortest path problem does not have first-stage decisions. This results in the
features being a bit different than for the capital budgeting problem.
Therefore, to create a model that can be trained by shortest path data, and
used for the capital budgeting problem, the first-stage-related attributes are
not constructed while running $K$-B&B-NodeSelection. Full results of these
experiments is given in Figure 29 in the Appendix.

Figure 21(a) shows the results of EXP5 for the capital budgeting problem . We
can see that the performances of the two algorithms are very close. Recall
that $K^{train}=6$ previously resulted in (one of) the best solutions. Then,
when we look at some of the solutions of EXP6 with $K^{train}=6$ (see Figure
21(b)), we see this is not the case here.

(a)

(b)

Figure 21: EXP5 results of capital budgeting for
$K^{test}=K^{train}\in\\{3,4,5\\}$ and EXP6 results for $K^{train}=6$ and
$K^{test}\in\\{3,4,5\\}$.

Now we show the results of the shortest path problem that uses a ML model
trained on capital budgeting data. Due to the mismatch of features, we delete
the three first-stage-related features not used by shortest path from the
capital budgeting data. We can still use the generated capital budgeting data.
For all combinations of $K^{train}$ and $K^{test}$, see Figure 30. For an
illustration of EXP5, see Figure 22(a). These plots illustrate that for two
out of three values of $K^{test}$, $K$-B&B-NodeSelection outperforms $K$-B&B,
even though it is trained on data of another problem. More interesting is the
following: the performance of different values of $K^{test}$ with
$K^{train}=6$ gives very good results. They are as good as the ones trained on
shortest path data. For an illustration of this, see Figure 22(b).

(a)

(b)

Figure 22: EXP5 results of shortest path for
$K^{test}=K^{train}\in\\{3,4,5\\}$ and EXP6 results for $K^{train}=6$ and
$K^{test}\in\\{3,4,5\\}$.

###  4.6 Feature importances

A trained random forest model allows us to compute feature importance scores,
given in Figure 23 for $K^{train}\in\\{2,3,4,5,6\\}$. We observe that
relatively highest importance corresponds to the ’Objective’ feature (a state
feature), with the importances of the other features (both state and scenario
ones), being of similar magnitude – because of that, we cannot draw many
conclusions about the relative importances of the remaining features.

(a)

(b)

Figure 23: Feature importance of random forest for each value of $K^{train}$.

##  5 Conclusion and future work

We introduce an ML-based method to improve the $K$-B&B algorithm (Subramanyam
et al., 2020) for solving 2SRO optimization problems. $K$-B&B uses a search
tree to optimally partition the uncertainty set into $K$ parts and we propose
to use a supervised ML model that learns the best node selection strategy to
explore such trees faster.

For this, we designed a procedure for generating training data and formulated
the ML features based on our knowledge of 2SRO so that they are independent of
the size, the value of $K$, and the type of problems on which the ML tool is
trained. We experimentally show that our method outperforms $K$-B&B on the
problems we test on. We see that when a problem is trained on a smaller
instance size, and then applied to the same problem type with bigger
instances, our method still outperforms $K$-B&B, although being less stable.
Training and testing on entirely different problem types resulted in mixed
results.

As $K$-B&B has a tree search structure, we believe that our work can be used
to tackle other problems solved by a similar tree search structure, wherever
expert knowledge can be used to construct meaningful problem size-independent
features.

## References

  * Ben-Tal et al. [2004] Aharon Ben-Tal, Alexander Goryashko, Elana Guslitzer, and Arkadi Nemirovski.  Adjustable robust solutions of uncertain linear programs.  _Mathematical Programming_ , 99(2):351–376, 2004\.
  * Ben-Tal et al. [2009] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski.  _Robust Optimization_ , volume 28.  Princeton University Press, 2009.
  * Bengio et al. [2020] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost.  Machine learning for combinatorial optimization: a methodological tour d’horizon.  _European Journal of Operational Research_ , 2020.
  * Bertsimas and Caramanis [2010] Dimitris Bertsimas and Constantine Caramanis.  Finite adaptability in multistage linear optimization.  _IEEE Transactions on Automatic Control_ , 55(12):2751–2766, 2010.
  * Bertsimas and Dunning [2016] Dimitris Bertsimas and Iain Dunning.  Multistage robust mixed-integer optimization with adaptive partitions.  _Operations Research_ , 64(4):980–998, 2016.
  * Browne et al. [2012] Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton.  A survey of monte carlo tree search methods.  _IEEE Transactions on Computational Intelligence and AI in games_ , 4(1):1–43, 2012.
  * Buchheim and Kurtz [2017] Christoph Buchheim and Jannis Kurtz.  Min–max–min robust combinatorial optimization.  _Mathematical Programming_ , 163(1):1–23, 2017\.
  * Gurobi Optimization [2020] LLC Gurobi Optimization.  Gurobi optimizer reference manual, 2020.  URL http://www.gurobi.com.
  * Guslitzer [2002] Elana Guslitzer.  Uncertainty-immunized solutions in linear programming.  Master’s thesis, Technion, Israeli Institute of Technology, 2002.
  * Hanasusanto et al. [2015] Grani A Hanasusanto, Daniel Kuhn, and Wolfram Wiesemann.  K-adaptability in two-stage robust binary programming.  _Operations Research_ , 63(4):877–891, 2015.
  * He et al. [2014] He He, Hal Daume III, and Jason M Eisner.  Learning to search in branch and bound algorithms.  _Advances in neural information processing systems_ , 27:3293–3301, 2014.
  * Khalil et al. [2022a] Elias B Khalil, Christopher Morris, and Andrea Lodi.  Mip-gnn: A data-driven framework for guiding combinatorial solvers.  _Update_ , 2:x3, 2022a.
  * Khalil et al. [2022b] Elias B Khalil, Pashootan Vaezipoor, and Bistra Dilkina.  Finding backdoors to integer programs: A monte carlo tree search framework.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pages 3786–3795, 2022b.
  * Loth et al. [2013] Manuel Loth, Michele Sebag, Youssef Hamadi, and Marc Schoenauer.  Bandit-based search for constraint programming.  In _International Conference on Principles and Practice of Constraint Programming_ , pages 464–480. Springer, 2013.
  * Pedregosa et al. [2011] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011\.
  * Postek and den Hertog [2016] Krzysztof Postek and Dick den Hertog.  Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set.  _INFORMS Journal on Computing_ , 28(3):553–574, 2016.
  * Sabharwal et al. [2012] Ashish Sabharwal, Horst Samulowitz, and Chandra Reddy.  Guiding combinatorial optimization with uct.  In _International conference on integration of artificial intelligence (AI) and operations research (OR) techniques in constraint programming_ , pages 356–361. Springer, 2012.
  * Subramanyam et al. [2020] Anirudh Subramanyam, Chrysanthos E Gounaris, and Wolfram Wiesemann.  K-adaptability in two-stage mixed-integer robust optimization.  _Mathematical Programming Computation_ , 12(2):193–224, 2020.
  * Świechowski et al. [2022] Maciej Świechowski, Konrad Godlewski, Bartosz Sawicki, and Jacek Mańdziuk.  Monte carlo tree search: A review of recent modifications and applications.  _Artificial Intelligence Review_ , pages 1–66, 2022.

##  Appendix A Attribute descriptions

Each scenario gets its own set of attributes. In total there are nine types:
one is the scenario vector $\boldsymbol{z}$ itself
($\boldsymbol{a}_{1}^{\boldsymbol{z}}=\boldsymbol{z}$), three are determined
by the solutions of the master problem, three are extracted from solving the
deterministic problem, and two are taken from solving the static problem.

####  Master problem-based attributes.

For these attributes, only little additional computation is needed. This is
due to the fact that the values we use can be taken from the current solution
of the master problem. Attributes 2-4 in Table 2 share this property:

  * 2.

Constraint distance.  For the first attribute of the ‘master-problem’ type, we
look at the constraints generated by the new scenario $\boldsymbol{z}^{*}$. We
call these constraints the ‘$\boldsymbol{z}^{*}$-constraints’. When a
constraint is added to a problem, the resulting feasible region will always be
as large as, or smaller than, the feasible region we had before. When the
feasible region is large, the objective value we find is often better than for
smaller feasible regions (the optimal value found in the large region may be
cut off in the small region). Each subset
$\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{K}$ consists of its own set
of scenarios, which translates to its own set of constraints in the master
problem. These are the ‘$\bar{\mathcal{Z}}_{k}$-constraints’, for all
$k\in\mathcal{K}$. These $\bar{\mathcal{Z}}_{k}$-constraints form a
feasibility region for the decision pair
($\boldsymbol{x},\boldsymbol{y}_{k}$). Ideally, we would calculate the volume
of the feasible region whenever the $\boldsymbol{z}^{*}$-constraints are added
to the existing feasible regions. However, obtaining this result is
computationally intractable. Therefore we only look at the distance between
the constraints. We generate the cosine similarity between the
$\boldsymbol{z}^{*}$-constraints and the $\bar{\mathcal{Z}}_{k}$-constraints,
for each subset separately. When the cosine similarity is high, the distance
between the constraints is low. Then, the attribute of the $k$-th child node
$\boldsymbol{a}^{k,\boldsymbol{z}^{*}}_{2}$ is the cosine similarity of the
$\boldsymbol{z}^{*}$-constraints and the $\bar{\mathcal{Z}}_{k}$-constraints:

$a^{k,\boldsymbol{z}^{*}}_{2,c}=\max_{\boldsymbol{z}\in\bar{\mathcal{Z}}_{k}}\quad\frac{\gamma_{c}(\boldsymbol{z}^{*})\cdot\gamma_{c}(\boldsymbol{z})}{\lVert\gamma_{c}(\boldsymbol{z}^{*})\rVert\lVert\gamma_{c}(\boldsymbol{z})\rVert},\qquad\forall
c\in\\{1,\ldots,C\\},\quad\forall k\in\mathcal{K},$

where $a^{k,\boldsymbol{z}^{*}}_{2,c}\in[-1,1]$ and
$\gamma_{c}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{Z}\rightarrow\mathcal{X}\times\mathcal{Y}$ is a function of
the left-hand-side of constraint $c\in\\{1,\ldots,C\\}$ with input scenario
$\boldsymbol{z}$. The first- and second-stage decisions are variable. Finally,
the attribute of the $k$-th child node is formulated as
$\boldsymbol{a}^{k,\boldsymbol{z}^{*}}_{2}=[a^{k,\boldsymbol{z}^{*}}_{2,1},\ldots,a^{k,\boldsymbol{z}^{*}}_{2,C}]$.
Thus, the length of $\boldsymbol{a}^{k,\boldsymbol{z}^{*}}_{2}$ is equal to
the number of uncertain constraints of the MILP formulation of the problem.

  * 3.

Scenario distance.  Per subset, we wish to know how far away the new scenario
$\boldsymbol{z}^{*}$ is from _not_ being a violating scenario. We suspect that
if the distance is small rather than large, the current solution will not
change much. Thus, will not become much worse. This attribute first takes the
current solutions of the master problem. Then, for the $k$-th subset it
determines the distance between each of the following planes (boundaries of
constraints of Eq. (4)) and the new scenario
$\boldsymbol{z}^{*}\in\mathcal{Z}$:

$\displaystyle
c(\boldsymbol{z})^{\intercal}\boldsymbol{x}^{*}+d(\boldsymbol{z})^{\intercal}\boldsymbol{y}^{*}_{k}-\theta^{*}=0,$
(7) $\displaystyle
T_{c}(\boldsymbol{z})\boldsymbol{x}^{*}+W_{c}(\boldsymbol{z})\boldsymbol{y}^{*}_{k}-h_{c}(\boldsymbol{z})=0,\quad$
$\displaystyle\forall c\in\\{2,\ldots,C\\}.$

Hence, we need to determine the distance between a plane and a point, for each
constraint $c\in\\{1,\ldots,C\\}$, where $c=1$ corresponds to the objective
function. The point-to-plane distance of the $c$-th plane for subset $k$ is
calculated by projecting $\boldsymbol{z}^{*}$ on the normal vector of the
plane as follows:

$\chi^{k}_{c}=\frac{|\boldsymbol{\rho}_{c}(\boldsymbol{x}^{*},\boldsymbol{y}^{k})^{\intercal}\boldsymbol{z}^{*}|}{\lVert\boldsymbol{\rho}_{c}(\boldsymbol{x}^{*},\boldsymbol{y}^{k})\rVert},$

where $\boldsymbol{\rho}_{c}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{X}\times\mathcal{Y}\rightarrow\mathcal{Z}$ is a vector of
coefficients of constraint $c$ of Eq. (LABEL:eq:att_3_planes). To compare the
point-to-plane distance of the $K$ subsets, we scale over the sum of the
distance of the subsets. Then, the attribute is given as:

$a^{k,\boldsymbol{z}^{*}}_{3,c}=\frac{\chi^{k}_{c}}{\sum_{k^{{}^{\prime}}\in\mathcal{K}}\chi^{k^{{}^{\prime}}}_{c}},\quad\forall
c\in\\{1,\ldots,C\\},\quad\forall k\in\mathcal{K}.$

  * 4.

Constraint slacks.  This attribute takes the slack values of the uncertain
constraints of the master problem for the new scenario $\boldsymbol{z}^{*}$
with fixed first- and second-stage decisions $\boldsymbol{x}^{*}$ and
$\boldsymbol{y}^{*}$. For the $k$-th subset and the constraints
$c\in\\{1,\ldots,C\\}$, with $c=1$ the objective constraint, we get:

$\displaystyle s_{1}^{k}$
$\displaystyle=|c(\boldsymbol{z}^{*})^{\intercal}\boldsymbol{x}^{*}+d(\boldsymbol{z}^{*})^{\intercal}\boldsymbol{y}^{*}_{k}-\theta^{*}|,$
$\displaystyle s_{c}^{k}$
$\displaystyle=|T_{c}(\boldsymbol{z}^{*})\boldsymbol{x}^{*}+W_{c}(\boldsymbol{z}^{*})\boldsymbol{y}^{*}_{k}-h_{c}(\boldsymbol{z}^{*})|,$
$\displaystyle\forall c\in\\{2,\ldots,C\\}.$

Similarly as with the previous attribute, we compare the slack values of the
subsets by scaling over the sum of the slacks of all subsets:

$a^{k,\boldsymbol{z}^{*}}_{4,c}=\frac{s^{k}_{c}}{\sum_{k^{{}^{\prime}}\in\mathcal{K}}s^{k^{{}^{\prime}}}_{c}},\quad\forall
c\in\\{1,\ldots,C\\},\quad\forall k\in\mathcal{K}.$

####  Deterministic problem-based attributes.

This problem solves the two-stage robust optimization problem for where the
newly found scenario $\boldsymbol{z}^{*}$ is the only scenario considered. We
call this a deterministic problem, since we no longer deal with uncertainty.
The problem is formulated as follows:

$\displaystyle\min_{\theta^{n},\boldsymbol{x}^{n},\boldsymbol{y}^{n}}$
$\displaystyle\theta^{n}$ (8) s.t.
$\displaystyle\theta^{n}\in\mathbb{R},\boldsymbol{x}^{n}\in\mathcal{X},\boldsymbol{y}^{n}\in\mathcal{Y},$
$\displaystyle\boldsymbol{c}(\boldsymbol{z}^{*})^{\intercal}\boldsymbol{x}^{n}+\boldsymbol{d}(\boldsymbol{z}^{*})^{\intercal}\boldsymbol{y}^{n}\leq\theta^{n},$
$\displaystyle\boldsymbol{T}(\boldsymbol{z}^{*})\boldsymbol{x}^{n}+\boldsymbol{W}(\boldsymbol{z}^{*})\boldsymbol{y}^{n}\leq\boldsymbol{h}(\boldsymbol{z}^{*}).$

By solving this problem we obtain Attributes 5-7:

  * 5.

Deterministic objective function value $\theta^{n}$,

  * 6.

Deterministic first-stage decisions $\boldsymbol{x}^{n}$,

  * 7.

Deterministic second-stage decisions $\boldsymbol{y}^{n}$.

####  Static problem-based attributes.

A very simple method for approximately solving the two-stage robust
optimization problem is to first solve the first-stage decision for all
scenarios in the uncertainty set. Then, after a realization of uncertainty, we
combine this first-stage decision with the scenario to determine the second-
stage decision. This is an naive way of solving two-stage robust optimization,
thus not optimal for all scenarios. But, it could give us some information on
the approximate solutions to scenarios in the problem. Solving the static
problem consists of two steps: First, we obtain the static robust first-stage
decisions $\bar{\boldsymbol{x}}$ by solving

$\displaystyle\min_{\theta,\boldsymbol{x},\boldsymbol{y}}$
$\displaystyle\theta$ (9) s.t.
$\displaystyle\theta\in\mathbb{R},\boldsymbol{x}\in\mathcal{X},\boldsymbol{y}\in\mathcal{Y},$
$\displaystyle\boldsymbol{c}(\boldsymbol{z})^{\intercal}\boldsymbol{x}+\boldsymbol{d}(\boldsymbol{z})^{\intercal}\boldsymbol{y}\leq\theta,\qquad\qquad$
$\displaystyle\forall\boldsymbol{z}\in\mathcal{Z},$
$\displaystyle\boldsymbol{T}(\boldsymbol{z})\boldsymbol{x}+\boldsymbol{W}(\boldsymbol{z})\boldsymbol{y}\leq\boldsymbol{h}(\boldsymbol{z}),$
$\displaystyle\forall\boldsymbol{z}\in\mathcal{Z}.$

This is solved by replacing the uncertain constraints by robust counterparts,
see Ben-Tal et al. [2009]. Secondly, by fixing $\boldsymbol{x}$ to
$\bar{\boldsymbol{x}}$, we obtain the objective value $\theta^{s}$ and second-
stage decisions $\boldsymbol{y}^{s}$ by solving

$\displaystyle\min_{\theta^{s},\boldsymbol{y}^{s}}$ $\displaystyle\theta^{s}$
(10) s.t.
$\displaystyle\theta^{s}\in\mathbb{R},\boldsymbol{y}^{s}\in\mathcal{Y},$
$\displaystyle\boldsymbol{c}(\boldsymbol{z}^{*})^{\intercal}\bar{\boldsymbol{x}}+\boldsymbol{d}(\boldsymbol{z}^{*})^{\intercal}\boldsymbol{y}^{s}\leq\theta^{s},$
$\displaystyle\boldsymbol{T}(\boldsymbol{z}^{*})\bar{\boldsymbol{x}}+\boldsymbol{W}(\boldsymbol{z}^{*})\boldsymbol{y}^{s}\leq\boldsymbol{h}(\boldsymbol{z}^{*}).$

Note that problem (9) is solved only once in the algorithm, while problem (10)
needs to be solved for each scenario. By solving this problem we obtain
Attributes 8 and 9:

  1. 8.

Static objective function value $\theta^{s}$,

  2. 9.

Static second-stage decisions $\theta^{s}$

##  Appendix B Omitted pseudocodes

The $K$-adaptability branch-and-bound ($K$-B&B) algorithm, as presented in
Subramanyam et al. [2020], is given in Algorithm 2. In our implementation of
this algorithm, we apply a depth-first search strategy and select a random
node of $\mathcal{N}$ instead of the first one.

Input : Problem instance $\mathcal{P}(N)$ with size $N$,

number of partitions $K$

Output : Objective value $\theta$, first-stage decisions $\boldsymbol{x}$,
second-stage decisions
$\boldsymbol{y}=\\{\boldsymbol{y}_{1},\ldots,\boldsymbol{y}_{K}\\}$,

subsets with scenarios $\bar{\mathcal{Z}}_{k}$ for all $k\in\\{1,\ldots,K\\}$

Initialization : Incumbent partition: $\tau^{i}\mathrel{\mathop{\mathchar
58\relax}}=\\{\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{K}\\}$, where
$\bar{\mathcal{Z}}_{k}=\emptyset$ for all $k\in\mathcal{K}$,

set containing all node partitions yet to explore:
$\mathcal{N}\mathrel{\mathop{\mathchar 58\relax}}=\\{\tau^{i}\\}$,

incumbent solutions:
$(\theta^{i},\boldsymbol{x}^{i},\boldsymbol{y}^{i})\mathrel{\mathop{\mathchar
58\relax}}=(\infty,\emptyset,\emptyset)$

1 while  _$\mathcal{N}$ not empty_ do

2 Select the first node with partition
$\tau=\\{\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{K}\\}$ from
$\mathcal{N}$, then $\mathcal{N}\leftarrow\mathcal{N}\setminus\\{\tau\\}$

3

4 $(\theta^{*},\boldsymbol{x}^{*},\boldsymbol{y}^{*})\leftarrow\textit{master
problem}(\tau)$

5 if  _$\theta^{*} >\theta^{i}$_ then

6 Prune tree since current objective is worse than best solution found.

7 Continue to line 2.

8 end if

9
$(\boldsymbol{z}^{*},\zeta^{*})\leftarrow\textit{subproblem}(\theta^{*},\boldsymbol{x}^{*},\boldsymbol{y}^{*})$

10 if  _$\zeta^{*} >0$_ then

11 Solution not robust, create $K$ new branches.

12 for  _$k\in\\{1,\ldots,K\\}$_ do

13 $\tau^{k}\mathrel{\mathop{\mathchar
58\relax}}=\\{\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{k}\cup\\{\boldsymbol{z}^{*}\\},\ldots,\bar{\mathcal{Z}}_{K}\\}$

14 $\mathcal{N}\leftarrow\mathcal{N}\cup\\{\tau^{k}\\}$

15 end for

16

17 else

18 Current solution robust, prune tree.

19
$(\theta^{i},\boldsymbol{x}^{i},\boldsymbol{y}^{i},\tau^{i})\leftarrow(\theta^{*},\boldsymbol{x}^{*},\boldsymbol{y}^{*},\tau)$

20 end if

21

22 end while

return _$(\theta^{i},\boldsymbol{x}^{i},\boldsymbol{y}^{i},\tau^{i})$_

Algorithm 2 $K$-B&B

The steps for obtaining the ML model used for node selection consists of two
parts: (i) making training data and (ii) training the ML model. More details
on these steps are given in Procedure 3.

Input : Train instances
$\mathcal{P}_{1}^{train}(N^{train}),\ldots,\mathcal{P}_{I}^{train}(N^{train})$

number of partitions for training $K^{train}$,

level for training $L^{train}$,

quality threshold $\epsilon$,

$R$ for random dives per node

Output : Trained node selection strategy model.

// Get training data for $I$ instances

1 for  _$i\in\\{1,\ldots,I\\}$_ do

$(D,\boldsymbol{p})_{i}\leftarrow\textit{generate train
data}(\mathcal{P}^{train}_{i}(N^{train}),K^{train},L^{train},R)$

// using steps of Section 3.3

2 $\boldsymbol{q}_{i}\leftarrow\textit{quality}(\boldsymbol{p}_{i},\epsilon)$

3 end for

// Train node selection strategy model

4 Set $\textit{model}\leftarrow\textit{train ML
model}(\\{(D,\boldsymbol{q})_{1},\ldots,(D,\boldsymbol{q})_{I}\\})$

return _model_

Procedure 3 StrategyModel

For scaling some of the features (see Section 3.2), some information needs to
be gathered by some initial dives in the tree. The steps that are followed are
given in Procedure 4.

Input : Test instance $\mathcal{P}^{test}(N^{test})$,

number of partitions for testing $K^{test}$

Output : Objective value $\theta$, first-stage decisions $\boldsymbol{x}$,
second-stage decisions
$\boldsymbol{y}=\\{\boldsymbol{y}_{1},\ldots,\boldsymbol{y}_{K}\\}$,

Subsets with scenarios $\bar{\mathcal{Z}}_{k}$ for all $k\in\\{1,\ldots,K\\}$

Initialization : Incumbent partition: $\tau^{i}\mathrel{\mathop{\mathchar
58\relax}}=\\{\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{K}\\}$, where
$\bar{\mathcal{Z}}_{k}=\emptyset$ for all $k\in\mathcal{K}$,

1 Set $\tau=\tau^{i}$

2 while  _solution not robust_ do

3 $(\theta^{*},\boldsymbol{x}^{*},\boldsymbol{y}^{*})\leftarrow\textit{master
problem}(\tau)$

4
$(\boldsymbol{z}^{*},\zeta^{*})\leftarrow\textit{subproblem}(\theta^{*},\boldsymbol{x}^{*},\boldsymbol{y}^{*})$

5 if  _$\zeta^{*} >0$_ then

6 Solution not robust, random node selection.

7 $k^{{}^{\prime}}\leftarrow\textit{random uniform sample}([1,K])$

8 $\tau\mathrel{\mathop{\mathchar
58\relax}}=\\{\bar{\mathcal{Z}}_{1},\ldots,\bar{\mathcal{Z}}_{k^{{}^{\prime}}}\cup\\{\boldsymbol{z}^{*}\\},\ldots,\bar{\mathcal{Z}}_{K}\\}$

9

10 else

11 Robust solution found

12 $\textit{scaling info}\leftarrow(\theta^{0},\zeta^{0},\kappa^{0})$

13 end if

14

15 end while

return _scaling info_

Procedure 4 InitialRun

##  Appendix C Problem formulations

In the experiments, our method has been tested several problems. The
descriptions of these problems and their MILP formulations are given in this
section.

###  C.1 Capital budgeting with loans

We consider the capital budgeting with loans problem as defined in Subramanyam
et al. [2020], where a company wishes to invest in a subset of $N$ projects.
Each project $i$ has an uncertain cost $c_{i}(\boldsymbol{z})$ and an
uncertain profit $r_{i}(\boldsymbol{z})$, defined as

$c_{i}(\boldsymbol{z})=\big{(}1+\boldsymbol{\Phi}_{i}^{\intercal}\boldsymbol{z}/2\big{)}c_{i}^{0}\quad\text{and}\quad
r_{i}(\boldsymbol{z})=\big{(}1+\boldsymbol{\Psi}_{i}^{\intercal}\boldsymbol{z}/2\big{)}r_{i}^{0},\quad\forall
i\in\\{1,\ldots,N\\},$

where $c_{i}^{0}$ and $r_{i}^{0}$ represent the nominal cost and the nominal
profit of project $i$, respectively. $\boldsymbol{\Phi}_{i}^{\intercal}$ and
$\boldsymbol{\Psi}_{i}^{\intercal}$ represent the $i$-th row vectors of the
sensitivity matrices
$\boldsymbol{\Phi},\boldsymbol{\Psi}\in\mathbb{R}^{N\times N_{z}}$. The
realizations of the uncertain vector $\boldsymbol{z}$ belong to the
uncertainty set $\mathcal{Z}=[-1,1]^{N_{z}}$, where $N_{z}$ is the dimension
of the uncertainty set.

The company can invest in a project either before or after observing the risk
factor $\boldsymbol{z}$. In the latter case, the company generates only a
fraction $\eta$ of the profit, which reflects a penalty of postponement.
However, the cost remains the same as in the case of an early investment. The
company has a given budget $B$, which the company can increase by loaning from
the bank at a unit cost of $\lambda>0$, before the risk factors
$\boldsymbol{z}$ are observed. A loan after the observation occurs, has a unit
cost of $\mu\lambda$, with $\mu>1$. The objective of the capital budgeting
problem is to maximize the total revenue subject to the budget. This problem
can be formulated as an instance of the $K$-adaptability problem (2) as
follows:

$\displaystyle\max_{(x_{0},\boldsymbol{x})\in\mathcal{X},(y_{0},\boldsymbol{y})\in\mathcal{Y}^{K}}$
$\displaystyle\min_{\boldsymbol{z}\in\mathcal{Z}}\max_{k\in\mathcal{K}}\quad\theta$
s.t. $\displaystyle
r(\boldsymbol{z})^{\intercal}(\boldsymbol{x}+\eta\boldsymbol{y}_{k})-\lambda(x_{0}+\mu
y_{0}^{k})\geq\theta,$
$\displaystyle\forall\boldsymbol{z}\in\mathcal{Z}_{k},\forall
k\in\mathcal{K},$
$\displaystyle\boldsymbol{x}+\boldsymbol{y}_{k}\leq\boldsymbol{e},$
$\displaystyle\forall k\in\mathcal{K},$
$\displaystyle\boldsymbol{c(z)}^{\intercal}\boldsymbol{x}\leq B+x_{0},$
$\displaystyle\forall\boldsymbol{z}\in\mathcal{Z}_{k},\forall
k\in\mathcal{K},$
$\displaystyle\boldsymbol{c(z)}^{\intercal}(\boldsymbol{x}+\boldsymbol{y}_{k})\leq
B+x_{0}+y_{0}^{k},$
$\displaystyle\forall\boldsymbol{z}\in\mathcal{Z}_{k},\forall
k\in\mathcal{K},$

where $\mathcal{X}=\mathcal{Y}=\mathbb{R}_{+}\times\\{0,1\\}^{N}$,
$y_{0}=\\{y_{0}^{1},\ldots,y_{0}^{K}\\}$,
$\boldsymbol{y}=\\{\boldsymbol{y}_{1},\ldots,\boldsymbol{y}_{K}\\}$, $x_{0}$
and $y_{0}$ are the amounts of taken loan in the first- and second-stage,
respectively. Moreover, $x_{i}$ and $y_{i}$ are the binary variables that
indicate whether we invest in the $i$-th project in the first- and second-
stage, respectively. The constrains
$\boldsymbol{c(z)}^{\intercal}\boldsymbol{x}\leq B+x_{0}$ ensure that for the
first-stage, the expenditures are not more than the budget plus the loan taken
before the realization of uncertainty.

#### Test case.

Similarly as in Subramanyam et al. [2020], the uncertainty set dimension
$N_{z}$ is set to $N_{z}=4$. The nominal cost vector $\boldsymbol{c}^{0}$ is
chosen uniformly at random from the set $[0,10]^{N}$. Let
$\boldsymbol{r}^{0}=\boldsymbol{c}^{0}/5$,
$B=\boldsymbol{e}^{\intercal}\boldsymbol{c}^{0}/2$, and $\eta=0.8$. The rows
of the sensitivity matrices $\boldsymbol{\Phi}$ and $\boldsymbol{\Psi}$ are
sampled uniformly from the $i$-th row vector, which is sampled from
$[0,1]^{N_{z}}$, such that
$\boldsymbol{\Phi}_{i}^{\intercal}\boldsymbol{e}=\boldsymbol{\Psi}_{i}^{\intercal}\boldsymbol{e}=1$
for all $i\in\\{1,\ldots,N\\}$. This is also known as the unit simplex in
$\mathbb{R}^{N_{p}}$. For determining the cost of the loans, we set
$\lambda=0.12$ and $\mu=1.2$.

###  C.2 Shortest path

We consider the shortest path problem with uncertain arc weights as defined in
Subramanyam et al. [2020]. Let $G=(V,A)$ be a directed graph with nodes
$V=\\{1,...,N\\}$, arcs $A\subseteq V\times V$, and arc weights
$d_{ij}(\boldsymbol{\boldsymbol{z}})=(1+z_{ij}/2)d_{ij}^{0}$, $(i,j)\in A$.
Where $d_{ij}^{0}\in\mathbb{R}_{+}$ represents the nominal weight of the arc
$(i,j)\in A$ and $z_{ij}$ denotes the uncertain deviation from the nominal
weight. The uncertainty set is defined as

$\mathcal{Z}=\Big{\\{}\boldsymbol{z}\in[0,1]^{|A|}\mathrel{\mathop{\mathchar
58\relax}}\sum_{(i,j)\in A}z_{ij}\leq\Gamma\Big{\\}}.$

This uncertainty set imposes that at most $\Gamma$ arc weights may maximally
deviate from their nominal values. We need to find the shortest path from the
source node $s$, to the sink node $t$ before observing the realized arc
weights. This shortest problem can be formulated as an instance of the
$K$-adaptability problem

$\displaystyle\min_{\boldsymbol{y}\in\mathcal{Y}^{K}}\quad$
$\displaystyle\max_{\boldsymbol{z}\in\mathcal{Z}}\min_{k\in\mathcal{K}}\quad\theta$
s.t.
$\displaystyle\boldsymbol{d(\boldsymbol{z})}^{\intercal}\boldsymbol{y}_{k}\leq\theta,\qquad$
$\displaystyle\forall\boldsymbol{z}\in\mathcal{Z}_{k},\forall
k\in\mathcal{K},$ $\displaystyle\sum_{(j,l)\in A}y^{k}_{jl}-\sum_{(i,j)\in
A}y^{k}_{ij}\geq\boldsymbol{1}_{\\{j=s\\}}-\boldsymbol{1}_{\\{j=t\\}},$
$\displaystyle\forall j\in V,\forall k\in\mathcal{K},$
$\displaystyle\mathcal{Y}\subseteq\\{0,1\\}^{|A|}.$

Note that this problem contains only binary second-stage decisions and
uncertainty in the objective function. The $K$-B&B algorithm, will find $K$
shortest paths from $s$ to $t$. After $\boldsymbol{z}$ is observed, the path
$\boldsymbol{y}_{k}$ will be chosen if $\boldsymbol{z}\in\mathcal{Z}_{k}$.

#### Normal test case.

The coordinates in $\mathbb{R}^{2}$ for each vertex $i\in V$ are uniformly
chosen at random from the region $[0,10]^{2}$. The nominal weight of the arc
$(i,j)\in A$ is the Euclidean distance between node $i$ and $j$. The source
node $s$ and the sink node $t$ are defined to be the nodes with the maximum
nominal distance between them. The $\lfloor{0.9(N^{2}-N)}\rfloor$ arcs with
the highest nominal weight will be deleted to define the arc set $A$. The
budget of the uncertainty set $\Gamma$ is set to seven.

#### Sphere test case.

The instances of this type have nodes that are spread over a sphere. This is
done as follows. First, each node in the three-dimensional graph is sampled
from the standard normal distribution and then normalized. The distance
between node $i$ and $j$ is then derived by its spherical distance. To obtain
this, first the euclidean distance $d_{ij}$ between node $i$ and $j$ is
computed. Then, the arc sine of $d_{ij}/2$ is computed to get the spherical
distance. The $\lfloor{0.7(N^{2}-N)}\rfloor$ arcs with the highest nominal
weight will be deleted to define the arc set $A$. The budget of the
uncertainty $\Gamma$ is set to seven.

###  C.3 Knapsack

We consider the two-stage version of the knapsack problem where the profit per
item is uncertain. This formulation is based on that of Buchheim and Kurtz
[2017]. Let $N$ be the number of items,
$p_{i}(\boldsymbol{z})=(1-z_{i}/2)p^{0}_{i}$ the profit for item
$i\in\\{1,\ldots,N\\}$, where $p^{0}_{i}\in\mathbb{R}$ is the nominal profit
value, $z_{i}$ is the deviation, $\boldsymbol{w}\in\mathbb{R}^{N}$ is the
weight vector, and $C=c\sum_{i=1}^{N}w_{i}$ is the total capacity of the
knapsack with $c\in(0,1)$. The uncertainty set is defined as

$\mathcal{Z}=\Big{\\{}\boldsymbol{z}\in[0,1]^{N}\mathrel{\mathop{\mathchar
58\relax}}\sum_{i=1}^{N}z_{i}\leq\Gamma\Big{\\}},$

where $\Gamma=\gamma N$ and $\gamma\in(0,1)$. This problem can be formulated
as an instance of the $K$-adaptability problem

$\displaystyle\max_{\boldsymbol{y}\in\mathcal{Y}^{K}}\quad$
$\displaystyle\min_{\boldsymbol{z}\in\mathcal{Z}}\max_{k\in\mathcal{K}}\quad\theta$
s.t.
$\displaystyle\boldsymbol{p(\boldsymbol{z})}^{\intercal}\boldsymbol{y}_{k}\geq\theta,\qquad$
$\displaystyle\forall\boldsymbol{z}\in\mathcal{Z}_{k},\forall
k\in\mathcal{K},$
$\displaystyle\boldsymbol{w}^{\intercal}\boldsymbol{y}_{k}\leq C,$
$\displaystyle\forall k\in\mathcal{K},$
$\displaystyle\mathcal{Y}\subseteq\\{0,1\\}^{N},$

where $y_{i}$ is the decision of putting item $i$ in the knapsack.

#### Test case.

The weight $w_{i}$ of each item $i\in\\{1,\ldots,N\\}$ is uniformly chosen at
random from $[1,15]$ and the cost $c_{i}$ from $[100,150]$. The values of $c$
and $\gamma$ are selected in the experiments section of the paper.

##  Appendix D Parameter tuning

For both training the ML model (a random forest) and applying it to a problem,
we have defined multiple parameters in StrategyModel and
$K$-B&B-NodeSelection. The tuning of these parameters is explained in this
section.

###  D.1 Capital Budgeting

For each $K\in\\{2,\ldots,6\\}$ we have trained five random forests: each for
$\epsilon\in\\{0.05,0.1,0.2,0.3,0.4\\}$. We have first decided on the values
of $\iota$ for generating training data. Problems become more complex when $K$
grows, which results in more time needed per dive. For tuning these
parameters, we have generated training data by running the algorithm for two
hours. Thus, we have fixed the parameter $T$ to two. In Table 5, for each
combination of $K$ and $\iota\in\\{2,5,10,15\\}$ the following information is
shown: number of data points, number of searched instances $I$, and the
average of $L^{train}$ reached per instance.

Table 5: Generated training data info for combinations of $K$ and $\iota$. (num. data points, $I$, average $L^{train}$). $K$ |  |  $\iota$ (in minutes)
---|---|---
|  | 2 | 5 | 10 | 15
2 |  | (17284, 60, 9) | (7192, 24, 10) | - | -
3 |  | (37227, 60, 7) | (36510, 24, 8) | (34536, 12, 9) | (30510, 8, 9)
4 |  | (21572, 60, 5) | (21860, 24, 6) | (24312, 12, 7) | (17008, 8, 7)
5 |  | (22425, 60, 5) | (23830, 24, 5) | (22510, 12, 6) | (20040, 8, 6)
6 |  | (17820, 60, 4) | (17544, 24, 5) | (18834, 12, 5) | (17382, 8, 5)

We have then selected per $K$ a value of $\iota$ that has high values of the
number of data points, $I$ and $L^{train}$. Then, for each $\epsilon$ and $K$,
the dataset related to this value of $\iota$ has been trained. The accuracy of
these models are given in Table 6.

Table 6: Test accuracy of random forest for combinations of $K$ (with best $\iota$) and the threshold $\epsilon$. $K$ $(\iota)$ |  | $\epsilon$
---|---|---
|  | 0.05 | 0.1 | 0.2 | 0.3 | 0.4
2 (2) |  | 0.971 | 0.988 | 0.971 | 0.988 | 0.983
3 (5) |  | 0.929 | 0.959 | 0.959 | 0.967 | 0.981
4 (5) |  | 0.922 | 0.950 | 0.977 | 0.982 | 0.995
5 (5) |  | 0.958 | 0.937 | 0.967 | 0.975 | 0.992
6 (10) |  | 0.937 | 0.952 | 0.968 | 0.974 | 0.984

The table above shows that $\epsilon$ does not influence the accuracy of the
model. However, Figure 9 shows that the algorithm performs better when
$\epsilon$ is very small. If we look at the density of success probabilities
$p$ in Figure 24, we notice that the vast majority of data points have
$p_{n}\approx 0$. These two observations indicate that any value of $p_{n}$
slightly higher than zero is special, and the corresponding node is considered
as a good node to visit.

Figure 24: Density of the success probability $p_{n}$ for each value of
$K^{train}$.

In the experiments section of the paper we noticed that high values of
$L^{test}$ outperformed lower ones in the $K$-B&B-NodeSelection algorithm. In
Figure 25, we show the results for higher values of $L^{train}$ than the ones
shown in Figure 9 for a fixed $\epsilon=0.05$.

Figure 25: Results of $K$-B&B with random dives and $K$-B&B-NodeSelection with
combinations of $K$ and bigger values of $L^{test}$.

###  D.2 Shortest path on a sphere

For the shortest path problem we also want to decide on the parameter $\iota$
per $K\in\\{2,3,4,5,6\\}$. We noticed that the total number of scenarios
needed until a robust solution is found, is larger for shortest path than for
capital budgeting. Therefore, the duration per training instance should
increase. The range of the number of minutes is $\iota\in\\{5,10,15,20\\}$. In
Table 7, for each combination of $K$ and $\iota$ the number of data points,
instances, and training level $L^{train}$ is given. For now, $T=2$ is fixed.

Table 7: Generated training data info for combinations of $K$ and $\iota$. (num. data points, $I$, average $L^{train}$). $K$ |  |  $\iota$ (in minutes)
---|---|---
|  | 5 | 10 | 15 | 20
2 |  | (10802, 24, 8) | (8290, 12, 9) | (9160, 8, 10) | (8494, 6, 10)
3 |  | (8370, 24, 6) | (6726, 12, 6) | (9858, 8, 6) | (7506, 6, 7)
4 |  | (9884, 24, 5) | (8496, 12, 6) | (7916, 8, 6) | (15872, 6, 6)
5 |  | (13795, 24, 4) | (7415, 12, 5) | (12490, 8, 5) | (21110, 6, 6)
6 |  | (26346, 24, 5) | (10794, 12, 5) | (18948, 8, 5) | (25788, 6, 5)

We have then selected per $K$ a value of $\iota$ that has high values of the
number of data points, $I$ and $L^{train}$. Then, for each $\epsilon$ and $K$,
the dataset related to this value of $\iota$ has been trained. See Table 8 for
the accuracy of these models.

Table 8: Number of data points used for training and test accuracy of random forest for combinations of $K$ (with best $\iota$) and hours spent for generating training data $T$, given the threshold $\epsilon=0.05$. (num. data points, test accuracy). $K(\iota)$ |  | $T$
---|---|---
|  | 1 | 2 | 5 | 10
2 (15) |  | (6586, 0.955) | (9160, 0.946) | (16852, 0.923) | (35674, 0.947)
3 (15) |  | (4170, 0.952) | (9858, 0.939) | (28347, 0.919) | (47346, 0.937)
4 (20) |  | (2828, 0.931) | (15872, 0.969) | (37652, 0.966) | (69244, 0.932)
5 (20) |  | (4790, 0.875) | (21110, 0.972) | (47000, 0.93) | (77735, 0.91)
6 (15) |  | (13500, 0.948) | (18948, 0.916) | (54564, 0.945) | (91254, 0.955)

We noticed for the shortest path problem that more data points significantly
increased the performance of the ML model on the algorithm. An overview of the
chosen values of $\iota$ and $T$ (hours spend for getting training data) per
$K$ are given in Table 9.

Table 9: Chosen parameter combination for each $K$. The values of $\epsilon$ and $L^{test}$ are fixed to 0.05 and $\infty$, respectively. $K$ | $\iota$ | $T$
---|---|---
2 | 15 | 10
3 | 15 | 5
4 | 20 | 5
5 | 20 | 10
6 | 15 | 10

The density of the success probabilities for the data points of shortest path
are given in Figure 26. This is very similar as the density of capital
budgeting (see Figure 24).

Figure 26: Density of the success probability $p_{n}$ for each value of
$K^{train}$.

##  Appendix E Results

We have applied $K$-B&B-NodeSelection to multiple problems, where the training
and testing instance specifications also varied. In the main body, only a
subset of the experiments are shown. In this section, all of them are given.

###  E.1 Capital budgeting with loans

Figure 27: Comparison of results between $K$-B&B and $K$-B&B-NodeSelection for
100 instances of the capital budgeting problem. In the first plot, the results
of EXP1 and EXP2 are shown. In the second and third the results for EXP3 and
EXP4 are done, for $N^{test}$ equal to 20 and 30, respectively. The regions
with shaded colour around the curves denote its $75\%$ CI.

###  E.2 Shortest path

Figure 28: Comparison of results between $K$-B&B and $K$-B&B-NodeSelection for
100 instances of the shortest path problem on a sphere. In the first plot, the
results of EXP1 and EXP2 are shown. In the second and third the results for
EXP3 and EXP4 are done, for $N^{test}$ equal to 40 and 60, respectively. The
regions with shaded colour around the curves denote its $75\%$ CI.

###  E.3 Mixed problems

Figure 29: Results of the capital budgeting problem. The ML model that is used
is trained on shortest path data. Figure 30: Results of the shortest path
problem. The ML model that is used is trained on capital budgeting data.