<figure><img src="image_73.png" /><figcaption>Figure 4.33: Relation between anytime measure and feature values for training problem instances. GEPS, 2 objectives.</figcaption></figure>

<figure><img src="image_74.png" /><figcaption>Figure 4.34: Relation between anytime measure and feature values for training problem instances, for anytime measures greater than 99.9. GEPS, 2 objectives.</figcaption></figure>
<table><caption>Table 4.25: Spearman's correlation coefficient between the features and anytime measures of the training instances. GEPS, 2 objectives.</caption><thead><tr><th>F<sub>1</sub></th><th>F<sub>2</sub></th><th>F<sub>3</sub></th><th>F<sub>4</sub></th></tr></thead><tbody><tr><td>-0.385</td><td>0.131</td><td>0.798</td><td>-0.297</td></tr></tbody></table>

<table><caption>Table 4.26: Weights for the distance metric. GEPS, 2 objectives.</caption><thead><tr><th>ξ<sub>1</sub></th><th>ξ<sub>2</sub></th><th>ξ<sub>3</sub></th><th>ξ<sub>4</sub></th></tr></thead><tbody><tr><td>4.667</td><td>1.689</td><td>24.361</td><td>3.286</td></tr></tbody></table>

<table><caption>Table 4.27: MAE given by LOOCV on the training problem instances. GEPS, 2 objectives.</caption><thead><tr><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th></tr></thead><tbody><tr><td>0.080</td><td>0.082</td><td>0.077</td><td>0.075</td><td><strong>0.074</strong></td><td>0.075</td><td>0.076</td><td>0.078</td><td>0.078</td><td>0.078</td></tr></tbody></table>

Figure 4.35 gives the histogram of prediction errors on all testing problem instances. As expected, the errors are very small for almost every instance, with a few exceptions where anytime measure is significantly over-estimated.

<figure><img src="image_75.png" /><figcaption>Figure 4.35: Histogram of the prediction error in terms of anytime measure for testing problem instances. The red line corresponds to the median. GEPS, 2 objectives.</figcaption></figure>
<figure><img src="image_76.png" /><figcaption>Figure 4.36: True and predicted anytime performance for 20 randomly selected testing problem instances. GEPS, 2 objectives.</figcaption></figure>

Figure 4.36 gives the true and predicted anytime performance for 20 ran-
domly selected testing problem instances. The results for all testing problem
instances can be found in Appendix A.7. We see that, in every case the pre-
dicted anytime performance follows the true anytime trace, despite the fact
that these instances have slightly different anytime behavior, especially for
small CPU times. This shows that our model, does not only give small predic-
tion errors because the differences between the instances are small, but that it
can in fact predict anytime performance quite well.

Figure 4.37 and Table 4.28 show the true and predicted anytime measure
and anytime performance for the testing problem instances with the largest
prediction errors. We see that the first two instances have a significant error,
but also that these are the outliers that we expected at the beginning of this
section. Besides those two instances, the anytime performance of the other 8
instances is predicted quite accurately.
<figure><img src="image_77.png" /><figcaption>Figure 4.37: True and predicted anytime performance for testing problem instances that resulted in the largest prediction errors. GEPS, 2 objectives.</figcaption></figure>

<table><caption>Table 4.28: True and predicted anytime measure values for testing problem instances that resulted in the largest prediction errors. GEPS, 2 objectives.</caption><thead><tr><td>Instance</td><td>Predicted measure</td><td>True measure</td><td>Error</td></tr></thead><tbody><tr><td>424</td><td>99.98</td><td>92.69</td><td>7.29</td></tr><tr><td>395</td><td>99.79</td><td>98.26</td><td>1.53</td></tr><tr><td>30</td><td>99.66</td><td>99.98</td><td>-0.31</td></tr><tr><td>377</td><td>99.88</td><td>99.99</td><td>-0.10</td></tr><tr><td>496</td><td>99.97</td><td>99.89</td><td>0.08</td></tr><tr><td>472</td><td>99.94</td><td>99.88</td><td>0.06</td></tr><tr><td>285</td><td>99.94</td><td>99.99</td><td>-0.06</td></tr><tr><td>159</td><td>99.99</td><td>99.93</td><td>0.05</td></tr><tr><td>230</td><td>99.79</td><td>99.74</td><td>0.05</td></tr><tr><td>316</td><td>99.97</td><td>99.94</td><td>0.04</td></tr></tbody></table>
## 4.3 Discussion

In this chapter, we started by presenting three distinct frameworks for creating empirical models to predict the anytime behavior of algorithms on previously unseen problem instances, taking into account empirical anytime performance data collected a priori. Although our goal is to predict anytime performance for the task of algorithm selection, these empirical models can easily be applied to other tasks such as automated algorithm configuration and anytime performance monitoring.

We also performed an experimental study for a model implemented according to the first framework, in which we analyzed its performance for predicting the anytime behavior of the PLS, BHV-DP, and GEPS algorithms on MOBKP instances with 2, 3, and 5 objectives considering 4 simple instance features. The results were very good for PLS and GEPS algorithms on problem instances for all numbers of objectives considered, and for the BHV-DP algorithm on problem instances with 2 objectives. In particular, we were able to accurately predict the anytime measure and anytime behavior of almost all testing problem instances. The results for the BHV-DP algorithm on problem instances with 3 and 5 objectives were not as good, and there were a considerable number of instances where the model failed to predict the anytime measure and anytime behavior with enough precision. However, we consider that the issue is not with the model itself, but rather the number of training instances available considering the range of parameters that we considered for generating instances. As such, it would be relevant to consider a more thorough study for the prediction of anytime behavior for the BHV-DP algorithm on whether more instances could improve the quality of the prediction.

Nonetheless, we consider that the resulting models obtained in the experimental study can be used for the task of algorithm selection, since they can adequately predict the tendency in anytime behavior in most cases, which might be sufficient for many selection problems. Therefore, we will consider these models in the following chapter.

For the future, it would be relevant to perform a similar experimental study for models implemented according to the other frameworks, or even for different models following the first framework, e.g., considering a different learning technique to find similar instances or even to consider manually categorized instances a priori. Preliminary experiments for a model following the second framework, showed that it can accurately model and predict anytime behavior. However, one difficulty that arose was in choosing an appropriate growth curve to model the anytime behavior of the algorithms. During these preliminary
experiments we considered a Weibull growth curve, which worked reasonably well for many cases, especially for problem instances with 2 and 3 objectives. However, as the number of objectives grew we saw that perhaps a different growth curve was needed. Moreover, when taking into account within-group correlation and variance, we found that estimating the model parameters using the *Generalized Non-Linear Least Squares (GNLS)* required very good initial estimates, otherwise, the *GNLS* method often failed to find the model parameters. Still, this is something that would be interesting to explore further, as initial results were quite promising.

Finally, it would be interesting to consider the modeling of different problems and algorithms using these models. Other interesting topics include taking into account other instance features, and to analyze the impact of different instance features on prediction quality.
<figure><img src="image_78.png" /></figure>
# Chapter 5

## Offline Algorithm Selection

In this chapter, we consider the development of an automated offline algorithm selection methodology for selecting between MOO algorithms such that the anytime performance of the selected algorithm is optimal with respect to the anytime preferences of the DM. This methodology takes into account models of anytime performance to predict the anytime performance profile for a previously unseen problem instance. In the previous chapters we presented both a theoretical model and an empirical model. In this chapter we will only consider the later since we want to consider anytime performance in terms of CPU-time.

We assume that the anytime preferences of the DM are known at the time of selection, and given to the algorithm selection methodology. Moreover, we consider that the anytime preferences of a DM are given by a general utility function $U(t, q) \to \mathbb{R}_{\ge 0}$ that denotes how likely the chosen algorithm is to be interrupted at a particular time t and archive quality q. The offline algorithm selection problem is then defined as:

$$ \underset{a \in \mathcal{A}}{\operatorname{argmax}} M(a, \iota, U) \qquad (5.1) $$

where $\mathcal{A}$ denotes the set of available algorithms, $\iota$ denotes the previously unseen instance for which we want to select an algorithm, and $M(a, \iota, U) \to \mathbb{R}$ denotes a scalar measure of anytime performance for an algorithm a on instance $\iota$ with respect to a utility function U that, without loss of generality, is to be maximized. Note that, we cannot generally expect to have an exact anytime performance measure for a previously unseen instance. As such, we will consider approximating the anytime performance measure.

The remainder of this chapter is organized as follows. In Section 5.1, we give a performance measure to characterize the anytime performance of an algorithm as a scalar value. In Section 5.2, we give a general offline algorithm selection methodology based on the empirical models of the previous chapter.
In Section 5.3, we carry out an experimental study to analyze the quality of the proposed methodology for selecting between anytime algorithms to the MOBKP. The results indicate that our approach can very often select the best algorithm. Lastly, in Section 5.4 we summarize the findings of this chapter and discuss possible directions for future work.

## 5.1 Anytime Performance Measure

We start by defining a pre-order that denotes whether a performance profile is at least as good as another with respect to a utility function $U$ that denotes the anytime preferences of the DM.

**Definition 5.1** ($\ge_U$ pre-order). Given two performance profiles $P$ and $P'$, and a utility function $U(t, q) \to \mathbb{R}_{\ge 0}$, we define the relation $P \ge_U P'$ iff $P(t, q) \ge P'(t, q)$ holds for every $t$ and $q$ where $U(t, q) > 0$.

Note that, for two algorithms $a, b$ with performance profiles $P_a$ and $P_b$ respectively, a relation $P_a \ge_U P_b$ means that algorithm $a$ is equally likely or more likely than algorithm $b$ to return an archive with quality $q$ at time $t$ for every $t, q$ such that $U(t, q) > 0$. However, there may be problem instances and/or runs for which algorithm $b$ is able to achieve a better archive quality $q$ than algorithm $a$ at a given time $t$.

The following binary relations between two performance profiles $P$ and $P'$ result from the $\ge_U$ pre-order:

$$ P =_U P' \iff P \ge_U P' \land P' \ge_U P \quad (\text{Equivalence}) $$

$$ P >_U P' \iff P \ge_U P' \land P' \not\ge_U P \quad (\text{Superiority}) $$

$$ P \|_U P' \iff P \not\ge_U P' \land P' \not\ge_U P \quad (\text{Incomparability}) $$

It is desirable that a performance measure is order-preserving with respect to the $\ge_U$ pre-order. Moreover, it is relevant that it allows to distinguish between incomparable performance profiles, that is, the performance measure can give distinct values for incomparable performance profiles.

In the following we assume, without loss of generality, that the domain for time is given by $\mathbb{R}_{\ge 0}$, and that archive quality is given by a finite scalar value in $\mathbb{R}$ to be maximized that is less than or equal to $q_u$. Moreover, we consider that the positive values for our utility function $U$ are bounded by a finite upper bound on time $t_u$ and a finite lower bound on archive quality $q_\ell$, that is:

$$ U(t, q) \to \begin{cases} \mathbb{R}_{\ge 0} & \text{if } t \le t_u \land q \ge q_\ell \\ 0 & \text{otherwise} \end{cases} \quad (5.2) $$
Then, a performance measure for anytime performance taking into account the utility function $U$ is given by:

$$M(P, U) = \int_{q_l}^{q_u} \int_{0}^{t_u} U(t, q) P(t, q) dt dq \qquad (5.3)$$

We assume that $M(P, U)$ is well-defined, i.e., $U(t, q) P(t, q)$ is integrable on the interval given by the specified bounds of time and quality.

Similar measures can be derived for discrete time and/or quality domains [36]. Note that, López-Ibáñez and Stützle [51] considered the use of the weighted hypervolume for measuring anytime performance, which gives an equivalent measure for algorithms with monotonic behavior. However, considering our definition of a performance profile given in Chapter 2, then our measure gives a different result for algorithms with non-monotonic behavior.

In the following, we give the properties of our measure with respect to the $\ge_U$ pre-order described earlier.

**Proposition 5.1.** Performance measure $M(\cdot, U)$ is order preserving with respect to the $\ge_U$ pre-order, that is:

$$P \ge_U P' \implies M(P, U) \ge M(P', U) \qquad (5.4)$$

*Proof.* If $P \ge_U P'$, then the following implications hold:

$$U(t, q) > 0 \implies U(t, q)P(t, q) \ge U(t, q)P'(t, q) \qquad (5.5)$$

$$U(t, q) = 0 \implies U(t, q)P(t, q) = U(t, q)P'(t, q) \qquad (5.6)$$

Then if both $M(P, U)$ and $M(P', U)$ are well-defined, which we have assumed to be, then the above implies that $M(P, U) \ge M(P', U)$. $\square$

It can also be shown that our measure is strictly order-preserving, that is:

$$P >_U P' \implies M(P, U) > M(P', U)$$

$$P =_U P' \implies M(P, U) = M(P', U)$$

**Proposition 5.2.** Performance measure $M(\cdot, U)$ allows to distinguish between incomparable performance profiles, that is:

$$P \|_U P' \not\implies M(P, U) = M(P', U) \qquad (5.7)$$

*Proof.* Let $t_u = 1$, $q_l = 0$, $q_u = 1$, and:

$$U(t, q) \to \begin{cases} 1 & \text{if } 0 \le t \le 1 \land 0 \le q \le 1 \\ 0 & \text{otherwise} \end{cases} \qquad (5.8)$$
$$P(t, q) \rightarrow \begin{cases} 0.4 & \text{if } 0 \le t \le 0.5 \land 0 \le q \le 1 \\ 0.6 & \text{if } t > 0.5 \land 0 \le q \le 1 \end{cases} \qquad (5.9)$$

$$P'(t, q) \rightarrow \begin{cases} 0.3 & \text{if } 0 \le t \le 0.5 \land 0 \le q \le 1 \\ 0.9 & \text{if } t > 0.5 \land 0 \le q \le 1 \end{cases} \qquad (5.10)$$

Then $M(P, U) = 0.5$ and $M(P', U) = 0.6$, and it holds that $P \|_U P'$ and $M(P, U) \neq M(P', U)$. □

## 5.2 Anytime Algorithm Selection

As discussed in Section 2.5, existing selection methodologies can be divided into two categories, regression and classification approaches. However, existing methodologies fail to consider the anytime preferences of the DM at the time of selection. In this section, we consider how the anytime preferences can be included in an algorithm selection methodology.

Assuming static anytime preferences, i.e., that anytime preferences do not change between calls to the selection methodology, then a regression approach could learn to predict the anytime performance measure for the algorithms from a set of training instances, e.g., by running the algorithms against the training instances and computing the anytime performance measure for the given static anytime preferences. If the anytime preferences are instead given to the algorithm selection methodology then one alternative would be to train a similar model, but to compute the anytime performance measure against several training utility functions, which should represent the true utility functions that may appear during selection. If the set of expected utility functions is well known and if the type of the utility function is easily identifiable, then we can train multiple models, one for each type of utility function. If instead, the utility functions are not easily identifiable, we may consider using a set of features related to the utility function, e.g., the time and quality bounds. However, this is likely to quickly become infeasible as we move to consider more general utility functions, since we need to introduce more features and more training utility functions.

In a classification approach, similar issues can arise. However, these may be somewhat limited by the fact that the classification approach does not need to learn to predict the quality. For example, consider the comparison of two algorithms: a heuristic that quickly achieves a good solution but stops on a local optimum, versus an exact algorithm that slowly starts with worse solutions but eventually reaches the global optimum. Consider that, for each instance, there is a time point $t$ such that the exact algorithm is always better than the
heuristic after *t*. If the classification system learns to predict that after *t* the exact algorithms is always better, then for any utility function with a lower bound on time greater than *t* the exact approach is better, and there is no need to consider such utility functions, which may help reducing training times. However, a larger number of utility functions and/or features may still be required for the remaining cases.

The issues discussed above mostly stem from the fact that we are trying to incorporate the utility functions into the training phase. Therefore, we consider an alternative regression approach that first learns to predict the anytime performance profile for the instance that we are trying to select an algorithm for, and only takes into account the utility function when computing the anytime performance measure to perform the selection. More generally, we describe this selection approach as follows:

1. Given a set of algorithms $\mathcal{A}$ and a set of training instances learn to predict the performance profile of an algorithm $a \in \mathcal{A}$ for a previously unseen instance.

2. Given a previously unseen instance $\iota$, predict the approximate performance profile $\tilde{P}_{a,\iota}$ for each algorithm $a \in \mathcal{A}$.

3. Given a utility function $U$, select the algorithm that, without loss of generality, maximizes $M(\tilde{P}_{a,\iota}, U)$, i.e.:

$$ \underset{a \in \mathcal{A}}{\operatorname{argmax}} M(\tilde{P}_{a,\iota}, U) \qquad (5.11) $$

Note that, $M(\tilde{P}_{a,\iota}, U)$ is an approximation to $M(a, \iota, U)$.

Throughout this thesis we have already discussed everything that is required for this methodology. In particular, in Chapter 3 and Chapter 4, we proposed theoretical and empirical models to predict the anytime performance profile of an anytime algorithm for a previously unseen instance, and in Section 5.1 we proposed an anytime performance measure that takes a performance profile and utility function. In the next section, we implement an algorithm selection methodology using the empirical model developed in Chapter 4 for predicting anytime performance of anytime algorithms for MOBKP instances, and the anytime measure introduced in Section 5.1.

## 5.3 Experimental Study

In this section, we carry out an experimental study to analyze the quality of the algorithm selection approach proposed in the previous section. In particular,
we compare our proposed approach against a random approach that randomly selects the algorithm to use, and against approaches that always select the same algorithm. This section is organized as follows. In Section 5.3.1 we describe the experimental setup. In Section 5.3.2 we show and analyze the results.

## 5.3.1 Experimental Setup

We consider the same instances, algorithm configurations, and runs that were used for Section 4.2.4. In particular, we consider 500 instances for each number of objectives $m \in \{2, 3, 5\}$, with the following parameter sampling:

* $n \in \mathcal{U}(50, 150)$;

* $\rho_v \in \mathcal{U}(\frac{6}{\pi} \sin^{-1} \frac{1}{2(1-m)}, 1)$;

* $\rho_w \in \mathcal{U}(-1, 1)$;

* $\omega \in \mathcal{U}(0.3, 0.7)$.

For each instance, we record the anytime performance trace, in terms of CPU-time and hypervolume, for one run of the BHV-DP and PLS algorithms for $m \in \{2, 3, 5\}$ objectives, and the GEPS algorithm for $m = 2$ objectives. We consider a timeout of 100 seconds for algorithm execution. The algorithms are configured as follows:

* BHV-DP: ordering of the items following $O^{\min}$;

* PLS: default ordering of the items, initial empty solution $x = \{0, \dots, 0\}$, random selection of the next item to process;

* GEPS: Parameter $\ell = 100$ to build the theoretical model that guides this approach.

The C++ implementation for the algorithms is available at [33]. The code used to generate the problem instances, and to gather the performance traces of the algorithms, is available at [32].

We consider two selection scenarios with distinct utility functions. First, we consider a scenario where there is almost complete uncertainty in terms of when the algorithm will be interrupted, with the exception that it will be stopped before or at time $t_u$. Moreover, we consider that there is no anytime preference with regards to solution quality, and that solution quality is defined in the range $[0, 1]$. In this first scenario, the utility function is given by:

$$U_1(t, q) \rightarrow \begin{cases} 1 & \text{if } 0 \le t \le t_u \land 0 \le q \le 1 \\ 0 & \text{otherwise} \end{cases} \qquad (5.12)$$
The second scenario considers that a time $t^*$ is known such that the algorithm will be interrupted at exactly that time. Moreover, we consider that there is no anytime preference with regards to solution quality, and that solution quality is defined in the range [0, 1]. In this second scenario, the utility function is given by:

$$U_2(t, q) \rightarrow \begin{cases} 1 & \text{if } t = t^* \land 0 \le q \le 1 \\ 0 & \text{otherwise} \end{cases} \qquad (5.13)$$

For each scenario, we consider 200 values of $t_u$ and $t^*$ evenly distributed in the range [1e-4, 1e2] on a log scale.

For our proposed algorithm selection approach, we consider the empirical models that were trained in Section 4.2, i.e., which correspond to our implementation of the first empirical model (Section 4.1.1). Moreover, we consider the same split between testing and training instances that was used in Section 4.2, such that the same training instances are used to train the model, and the testing instances are used for testing our proposed approach. Lastly, if more than one algorithm maximizes the anytime performance measure, the approach selects one of them at random.

## 5.3.2 Results

The following sections show the results of algorithm selection using our proposed approach. In each section we present the results for both utility functions considering instances with a particular number of objectives. The code to reproduce the experiments is available at [32].

### 2 Objectives – 3 Algorithms

In this section, we analyze the automated selection between the PLS, BHV-DP, and GEPS algorithms for problem instances with 2 objectives.

Table 5.1 gives the accuracy, with respect to the ratio of correct algorithm selections, on the first selection scenario for five distinct selection approaches: our proposed approach, a random approach that randomly selects one of the algorithms, and three other approaches, each of which corresponds to the selection of a single algorithm at all times as indicated by its name in the table. This ratio takes into account selection problems for all 100 testing problem instances and 200 values of $t_u$. We see that our approach has an accuracy value equal to 0.97, which is the highest, and indicates that our approach can very often choose the best algorithm. The random approach has an accuracy value close to 1/3, which is to be expected since there are three algorithms for
<table><caption>Table 5.1: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the first scenario. 2 objectives, 3 algorithms.</caption><thead><tr><th>Proposed</th><th>Random</th><th>PLS</th><th>BHV-DP</th><th>GEPS</th></tr></thead><tbody><tr><td><strong>0.97</strong></td><td>0.33</td><td>0.07</td><td>0.01</td><td>0.92</td></tr></tbody></table>

selection. Always selecting the GEPS gives an accuracy equal to 0.92, whereas the other two algorithms have very low accuracy, which means that the GEPS is very often the best choice.

Figure 5.1 summarizes the accuracy for the first selection scenario over all testing instances for each setting of $t_u$. We see that after the first values of $t_u$, our approach always selects the GEPS algorithm, since it follows the line of the approach that always select the GEPS algorithm. Moreover, we see that for very small values of $t_u$, our proposed approach often selects the PLS algorithm, since it closely follows the line of the approach that always selects the PLS algorithm. Selecting the PLS algorithm is clearly a good choice for the first few values of $t_u$. However, as the values of $t_u$ increase slightly, i.e., for values

<figure><img src="image_79.png" /><figcaption>Figure 5.1: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the first scenario at each value of $t_u$. 2 objectives, 3 algorithms.</figcaption></figure>
<table><caption>Table 5.2: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the second scenario. 2 objectives, 3 algorithms.</caption><thead><tr><th>Proposed</th><th>Random</th><th>PLS</th><th>BHV-DP</th><th>GEPS</th></tr></thead><tbody><tr><td><strong>0.88</strong></td><td>0.40</td><td>0.06</td><td>0.41</td><td>0.72</td></tr></tbody></table>

$t_u \in [2.1e-4, 2.5e-4]$, our approach has an accuracy close to 0.5. Further analysis of the data revealed that our approach tends to wrongly select the GEPS algorithm for those values of $t_u$, when it should be selecting the BHV-DP or PLS algorithms instead. The full prediction results in Appendix A show that the prediction model for the GEPS algorithm often overestimates the solution quality obtained by the algorithm at such small CPU-time values. As such, to improve the accuracy of our proposed selection approach in this scenario we should focus on improving the prediction at small CPU-time values for the GEPS algorithm.

Table 5.2 gives the accuracy for the second selection scenario, i.e., with utility function $U_2$, and the same five distinct selection approaches. It summarizes the accuracy over the 100 testing instances and 200 values of $t^*$. We see that our approach got the highest accuracy with a value equal to 0.88, which is slightly worse than before, but still quite good. Note that, the random approach achieved a value slightly larger than 1/3. This happens because for values of $t^*$ close to 100, both the BHV-DP and the GEPS algorithms have found a solution with optimal solution quality value, and as such, choosing any of those algorithms is correct. We also see that always selecting the GEPS algorithm now has slightly worse accuracy, and always selecting the BHV-DP algorithm has improved significantly. This is due to the fact that the BHV-DP algorithm can always find the Pareto set within the 100 second timeout, as such, it will often be the best choice for larger values of $t^*$.

Figure 5.2 summarizes the accuracy for the second selection scenario over all testing instances for each setting of $t^*$. For very small values of $t^*$ the behavior is similar to that of the first scenario, that is, our approach can often select the PLS correctly for very small values of $t^*$, but then wrongly selects the GEPS algorithm for values of $t^*$ close to 2e-4, instead of the BHV-DP and PLS algorithms. However, what is different is the behavior for values of $t^*$ greater than 1e-2. For these values, the GEPS is not always the best choice like in the first scenario, and we see that the BHV-DP steadily becomes the best choice. In this case, we see that when two choice lies between two algorithms, our approach can often make the correct selection. However, the fact that
<figure><img src="image_80.png" /><figcaption>Figure 5.2: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the second scenario at each value of $t^*$. 2 objectives, 3 algorithms.</figcaption></figure>

accuracy is close to 0.75 at times, indicates that there is still some room for improvement. The prediction results for the **BHV-DP** and **GEPS** algorithms, which can be seen in Appendix A.4 and Appendix A.7 respectively, indicate that the issue is the prediction of anytime performance for the **BHV-DP** algorithm, which is sometimes not very accurate for CPU-time values greater than 1e-2. As such, to improve the selection in this case, we would primarily need to improve the prediction model of the **BHV-DP** algorithm.

## 2 Objectives – 2 Algorithms

In the previous section, we saw that the **GEPS** algorithm was very often better than the other two algorithms, in particular in the first scenario. Moreover, the **PLS** was only the best choice for very small values of $t_u$ and $t^*$. In this section, we choose to ignore the **GEPS** algorithm, to better analyze the selection between the **PLS** and the **BHV-DP** algorithms for instances with 2 objectives.

Table 5.3 gives the overall accuracy on the first selection scenario. Our proposed approach got an accuracy value equal to 0.90, which was the highest. This is slightly less than in the previous case. However, given that always selecting the **PLS** or **BHV-DP** algorithms resulted in accuracy values equal
<table><caption>Table 5.3: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the first scenario. 2 objectives, 2 algorithms.</caption><thead><tr><th>Proposed</th><th>Random</th><th>PLS</th><th>BHV-DP</th></tr></thead><tbody><tr><td><strong>0.90</strong></td><td>0.51</td><td>0.63</td><td>0.37</td></tr></tbody></table>

to 0.63 and 0.37 respectively, the accuracy of our proposed approach looks particularly good, and indicates that our approach is consistently selecting the best algorithm.

Figure 5.3 gives the accuracy on the first selection scenario for different values of $t_u$. We see that the PLS algorithm is often the best choice for smaller values of $t_u$, whereas the BHV-DP algorithm is often the best choice for larger values of $t_u$. As for our approach, we see that it can often select the best approach and that accuracy only falls slightly below 0.75 for small timeout values. The prediction results in Appendix A.1 and Appendix A.4, for the PLS and BHV-DP algorithms respectively, show that the prediction of the PLS algorithm is generally more accurate than that of the BHV-DP. As such, to improve

<figure><img src="image_81.png" /><figcaption>Figure 5.3: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the first scenario at each value of $t_u$. 2 objectives, 2 algorithms.</figcaption></figure>
<table><caption>Table 5.4: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the second scenario. 2 objectives, 2 algorithms.</caption><thead><tr><th>Proposed</th><th>Random</th><th>PLS</th><th>BHV-DP</th></tr></thead><tbody><tr><td><strong>0.90</strong></td><td>0.50</td><td>0.52</td><td>0.48</td></tr></tbody></table>

the accuracy, we consider that the primary focus should be on improving the prediction of anytime performance for the BHV-DP algorithm.

Table 5.4 gives the accuracy on the second selection scenario. We see that the results are not very different than those in the first scenario, and that our approach still has the highest accuracy. However, the accuracy of choosing only the PLS or BHV-DP algorithms is now more balanced. Therefore, the fact that our proposed approach continues to get such an high accuracy, clearly indicates that it can often select the best algorithm.

Figure 5.4 gives the accuracy on the second selection scenario for different values of $t^*$. We see a very similar behavior when compared to the first scenario. In particular, we see that the PLS algorithm is often the best choice for small

<figure><img src="image_82.png" /><figcaption>Figure 5.4: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the second scenario at each value of $t^*$. 2 objectives, 2 algorithms.</figcaption></figure>
values of $t^*$, whereas the BHV-DP algorithm is often the best choice for large values of $t^*$. Moreover, we see that our approach can often select the best algorithm, and that accuracy almost never drops below 0.75. Nonetheless, there is still room for improvement, and, as before, we consider that to improve the accuracy of our approach the prediction of anytime performance for the BHV-DP algorithm should be improved.

## 3 Objectives – 2 Algorithms

We now turn to the selection between the PLS and BHV-DP algorithms on problem instances with 3 objectives.

Table 5.5 gives the accuracy on the first selection scenario considering all testing problem instances and values of $t_u$. We see that our proposed approach got an accuracy value of 0.87, which is the highest. Moreover, we see that choosing only the PLS algorithm had an accuracy value of 0.74, and choosing only the BHV-DP algorithm resulted in an accuracy value of 0.26.

Figure 5.5 gives the accuracy on the first scenario for each value of $t_u$. We see that our proposed approach is always equal to or better than the other approaches. However, we see that for values of $t_u$ close to 1e-3 it has a significantly low accuracy compared to other values of $t_u$. The full prediction results for the PLS and BHV-DP algorithms, which can be seen in Appendix A.2 and Appendix A.5 respectively, show that the prediction for CPU-times around 1e-3 is generally quite good for both algorithms, save for a few exceptions. Moreover, for both algorithms the solution quality, in terms of relative hyper-volume, at that time is often very close to 0. On the one hand, this shows that small errors in prediction can be significant for selection accuracy, and should not be discarded. On the other hand, the fact that quality values are so small indicate that perhaps this is not a very relevant selection scenario. For larger values of $t_u$, we see that the accuracy of our approach is quite good, i.e., with accuracy values around 0.875, despite the fact that there is no algorithm that is clearly the best. For large CPU-time values, the prediction results for the BHV-DP algorithm are clearly worse than for the PLS algorithm. Moreover, in this case, the differences between the true and the predicted values are more

<table><caption>Table 5.5: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the first scenario. 3 objectives, 2 algorithms.</caption><thead><tr><th>Proposed</th><th>Random</th><th>PLS</th><th>BHV-DP</th></tr></thead><tbody><tr><td><strong>0.87</strong></td><td>0.50</td><td>0.74</td><td>0.26</td></tr></tbody></table>
<figure><img src="image_83.png" /><figcaption>Figure 5.5: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the first scenario at each value of $t_u$. 3 objectives, 2 algorithms.</figcaption></figure>

significant. Thus, the error in anytime measure due to a wrong selection is expected to be more significant. Therefore, we consider that to improve selection we should start by improving the predictions for the BHV-DP algorithm.

Table 5.6 and Figure 5.6 give the accuracy results for the second selection scenario. We see that the results are quite similar to the first selection scenario. As before, we consider that accuracy could be further improved, in particular, for larger values of $t^*$, if the prediction of anytime performance for the BHV-DP algorithm is improved.

<table><caption>Table 5.6: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the second scenario. 3 objectives, 2 algorithms.</caption><thead><tr><th>Proposed</th><th>Random</th><th>PLS</th><th>BHV-DP</th></tr></thead><tbody><tr><td><strong>0.87</strong></td><td>0.50</td><td>0.69</td><td>0.31</td></tr></tbody></table>
<figure><img src="image_84.png" /><figcaption>Figure 5.6: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the second scenario at each value of $t^*$. 3 objectives, 2 algorithms.</figcaption></figure>

## 5 Objectives – 2 Algorithms

Lastly, we analyze the selection between the PLS and BHV-DP algorithms for problem instances with 5 objectives.

Table 5.7 gives the accuracy on the first selection scenario. We see that our proposed approach got an accuracy value of 0.87, whereas choosing only the PLS algorithm had an accuracy value of 0.69, and choosing only the BHV-DP algorithm resulted in an accuracy value of 0.31. These results indicate that our approach can often select the best algorithm.

Figure 5.7 gives the accuracy on the first selection scenario for each value of $t_u$. We see that our proposed approach is often better than the other approaches.

<table><caption>Table 5.7: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the first scenario. 5 objectives, 2 algorithms.</caption><thead><tr><th>Proposed</th><th>Random</th><th>PLS</th><th>BHV-DP</th></tr></thead><tbody><tr><td><strong>0.87</strong></td><td>0.50</td><td>0.69</td><td>0.31</td></tr></tbody></table>
<figure><img src="image_85.png" /><figcaption>Figure 5.7: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the first scenario at each value of $t_u$. 5 objectives, 2 algorithms.</figcaption></figure>

However, for values of $t_u$ around 1e-3, we see that it is worse than always selecting the BHV-DP algorithm. Moreover, we get the worst accuracy at those values of $t_u$. Despite this, looking at the full prediction results for the PLS and BHV-DP algorithms, which can be seen in Appendix A.3 and Appendix A.6 respectively, we see that the prediction is quite good for both algorithms at small values of CPU-time, and that in both cases the solution quality, measured in terms of relative hypervolume, is close to zero. The latter observation indicates that perhaps this is not the most interesting selection scenario. On the other hand, for larger values of CPU-time, the prediction for the BHV-DP is worse than the PLS and the differences between the true and the predicted values are much larger. Therefore, to improve the selection we consider that it would be more relevant to focus on improving the prediction of anytime performance for the BHV-DP algorithm, in particular at larger CPU-times, so that not only is accuracy improved but also that the error when making a wrong selection is reduced.

Table 5.8 and Figure 5.8 give the accuracy results on the second selection scenario. We see that the results are quite similar to those of the first scenario. Therefore, we draw the same conclusions as before.
<table><caption>Table 5.8: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the second scenario. 5 objectives, 2 algorithms.</caption><thead><tr><th>Proposed</th><th>Random</th><th>PLS</th><th>BHV-DP</th></tr></thead><tbody><tr><td><strong>0.86</strong></td><td>0.50</td><td>0.67</td><td>0.33</td></tr></tbody></table>

<figure><img src="image_86.png" /><figcaption>Figure 5.8: Accuracy of our proposed approach, a random approach, and approaches that always select the same algorithm, on the second scenario at each value of $t^*$. 5 objectives, 2 algorithms.</figcaption></figure>

We remark that, despite the fact that the prediction of anytime performance for the BHV-DP algorithm on instances with 5 objectives often gives a large error, the selection accuracy remains quite high. The fact that the algorithms have such a different behavior is an important factor to this. Since otherwise, the models would need to be much more accurate. However, this is coupled with the fact that the predicted anytime performance is correctly capturing the tendency of anytime behavior, even when there is a significant error. Otherwise, we would not expect such a high accuracy.
## 5.4 Discussion

In this section we discussed a measure of anytime performance that can take into account the anytime preferences of a decision maker, and proposed an automated algorithm selection approach that can take these anytime preferences into account when selecting the best algorithm for a previously unseen instance. This algorithm selection approach considers models of anytime performance for the algorithms we want to select on previously unseen instances, such as those discussed in Chapters 3 and 4, as well as the discussed anytime measure to take into account the anytime preferences of a decision maker when selecting the best algorithm. Lastly, we carried out an experimental study to analyze the quality of this algorithm selection approach in selecting between algorithms to the MOBKP, considering two distinct utility functions.

This experimental study showed that our selection approach has very good accuracy, and generally works very well despite the fact that the models of anytime performance considered were, for some algorithms, not very accurate. Still, we highlighted several cases in which the accuracy of our approach left something to be desired due to the errors in the models of anytime performance. This shows that our approach relies on the quality of the selected models, and that to improve its accuracy we need to focus on improving the quality of the models. One relevant direction for future work is then to extend the experimental study to better analyze the relation between the models of anytime performance and the accuracy of our approach both theoretically and practically. For example, can lower and upper bounds for the accuracy of the selection approach be defined with respect to the quality of the empirical models, or how do changes to the empirical models such as using more instances and instance features affect our selection approach in practice.

Another aspect worth investigating is the time it takes for our approach to make a selection with respect to the empirical models being used. The way the code was developed did not allow to perform such measurements easily, and it was not developed with selection performance in mind. Still, preliminary experiments with the current code showed that computing the anytime performance profile and anytime measure for a single algorithm took about 1e-2 seconds or less for the considered empirical model, which should be acceptable for most scenarios. Nonetheless, further research is needed to better study and report the computational effort needed to select an algorithm with respect to the empirical models being used.

To better put into context the performance of our approach, it would also be worth investigating other algorithm selection methodologies, to compare
them to our approach. As previously discussed, one issue with more traditional
classification and regression approaches is that they do not take into account
the anytime preferences of the DM at the time of selection. Still, we could
consider that the anytime preferences of a DM are fixed prior to training, thus
allowing to compare with more traditional classification and regression ap-
proaches. Alternatively, it would be interesting to investigate the development
of new methodologies that can take into account the anytime preferences of
the DM at the time of selection, which would be comparable to our proposed
approach. Lastly, it would be interesting to analyze the quality of the pro-
posed algorithm selection approach in other problems, in particular, problems
appearing in real-world scenarios.
<figure><img src="image_87.png" /></figure>
# Chapter 6

## Online Algorithm Selection

In the previous chapter, we considered the selection of algorithms from an offline perspective, i.e., selecting the algorithm before starting its execution. In this chapter, we consider an online perspective for the ASP, that is, we want to select and change algorithms while already executing an algorithm to solve a previously unseen problem instance in order to improve anytime performance. In particular, we consider selecting between branch-and-bound strategies taking into account the anytime behavior of each strategy, and taking into account the performance of the strategy that is being executed.

To this end, we will start by proposing an *Indicator-based Branch-and-Bound (IBB)* approach that takes into account the potential of a node when selecting the next node to be explored in terms of a binary quality indicator [37], and give four selection strategies for this approach based on two distinct binary quality indicators. Then, we perform an empirical study to analyze the anytime performance of these selection strategies for the MOBKP, which shows that these approaches often have better anytime performance compared to traditional BB selection strategies. This empirical study also shows that not all selection strategies have the same anytime performance and that the selection strategy that most often gives the best approximation depends on the CPU-time and on the number of objectives of the problem instance being solved. Taking into account these empirical results, we propose an online methodology that changes between IBB selection strategies during execution based on a set of simple rules, with the goal of improving anytime performance. Lastly, we carry out an experimental study to analyze the anytime performance of this online methodology, which shows that it can often return better or equivalent approximations compared to the individual IBB selection strategies.

This chapter is organized as follows. In Section 6.1, we present the IBB approach and the implementation details of four selection strategies for this
approach. We also present the results of the experimental study analyzing the anytime performance of these selection strategies. In Section 6.2, we propose and empirically analyze the online selection methodology to change between IBB selection strategies. In Section 6.3, we summarize the results of this chapter and discuss possible directions for future research.

# 6.1 Indicator-based Branch-and-Bound

## 6.1.1 Framework

As discussed in Section 2.3.2, BB approaches enumerate feasible solutions by recursively dividing the decision space such that each subdivision gives way to a subproblem. Each subdivision is often seen as a node in a search tree. A key aspect of BB approaches is that lower and upper bound sets can be computed for each node and used to avoid exploring nodes that cannot lead to efficient solutions.

An important component for a BB approach, which can greatly impact its (anytime) performance, is how to select the next node to be explored. In Section 2.3.2, we discussed four distinct selection strategies: DFS, which selects the nodes closest to the bottom of the search tree first; BFS, which selects the nodes closest to the top of the search tree first; BeFS, which selects the most promising node according to some heuristic criteria; BeDFS, which selects the most promising node that is closest to the bottom of the search tree. In this section, we are particularly interested in defining a heuristic to identify the most promising node in the BeFS and BeDFS strategies, in the context of MOO. In particular, we propose using binary quality indicators to measure the quality of the upper bound set of a node with respect to the archive of solutions kept by the BB algorithm. Two such indicators are the binary hypervolume indicator and the ε-indicator discussed in Section 2.2. We denote by Indicator-based Branch-and-Bound (IBB) a BB approach that uses BeFS or BeDFS strategies guided by quality indicators, as described in the following.

Formally, considering the BB frameworks described in Algorithms 1 and 2 in Section 2.3.2, and that, w.l.o.g., the binary quality indicator considered is to be maximized, a BeFS selection strategy can be implemented by defining the SelectNode(Q) function as follows:

$$ \text{SelectNode}(Q) = \underset{\text{node} \in Q}{\operatorname{argmax}} I(U(\text{node}), \{f(x) : x \in S\}) \quad (6.1) $$

where Q denotes the active queue of nodes that can be selected, U(node) denotes the upper bound set of a node, S denotes the archive of solutions
currently kept by the algorithm, and $I(A, B) \to \mathbb{R}$ denotes a binary quality indicator that characterizes the quality of a set $A \subset \mathbb{R}^m$ with respect to a set $B \subset \mathbb{R}^m$. For a BeDFS selection strategy, the SelectNode is similar, but it considers only the nodes in $Q$ that are at the deepest level of the search tree.

Note that, under the assumption that the binary quality indicator $I$ is order-preserving for a fixed reference set, then this selection guarantees that the upper bound set of the chosen node is not dominated by the upper bound sets of the remaining nodes. Moreover, if the indicator is strictly order-preserving, and the optimal solution to the selection is unique, then the upper bound set of the chosen node is further guaranteed to not be weakly dominated by the upper bound sets of the remaining nodes. In Section 2.2 we have shown that the binary hypervolume is strictly order-preserving, and that the $\varepsilon$-indicator is order-reversing, which is functionally equivalent since, by definition, its negation is order-preserving.

As an example, in Figure 6.1 we illustrate the upper bound set $\{u\}$ of two distinct nodes, and in gray the area given by the binary hypervolume indicator for each upper bound set with respect to the image of the archive in the objective space (points in black). In this case, our selection strategy would select the node that gives the upper bound of the left-hand side figure.

A potential issue for this approach is that the computational cost of the binary quality indicator may be high, thus slowing down the search process significantly. For example, this can be an issue when considering the binary hypervolume indicator for problem instances with a large number of objectives [27]. We expect this to be less critical for the BeDFS strategy since it only considers the nodes that are closest to the bottom of search tree which are often small in number.

<figure><img src="image_88.png" /><figcaption>Figure 6.1: Illustration of the binary hypervolume indicator (in gray) for the upper bound set $\{u\}$ of two distinct nodes.</figcaption></figure>
## 6.1.2 Implementation Details

In this section we discuss the components of an IBB approach to the MOBKP problems using the BeFS and BeDFS selection strategies. We consider that the bound sets are computed according to the strategy described in Chapter 2.

The binary hypervolume and the $\epsilon$-indicator, described in Section 2.2, are considered as the binary quality indicators for the BeFS and BeDFS selection strategies. Since we consider an upper bound set comprised of a single point in the objective space, the binary hypervolume computation can be formulated as a hypervolume contribution calculation. For two objectives, the hypervolume contribution can be computed in $O(\log \mu)$ time, where $\mu$ is the number of solutions in the archive, if the objective vectors of the archive solutions are kept sorted by one of the objective values and data pertaining to the hypervolume calculation with a dimension sweep is kept for each node. For three objectives, the hypervolume contribution can be computed in $O(\mu)$ time with the HV3D$^+$-U algorithm [26] if the objective vectors of the archive solutions are stored in the data structure of the HV3D$^+$ algorithm [26]. For 4 or more objectives, we consider the use of the WFG algorithm [76], with the sorting and slicing improvements discussed in that work, which can compute the hypervolume contribution in $O(\mu^{m/2} \log \mu)$ time for $m$ objectives.

To compute the $\epsilon$-indicator of an upper bound set comprised of a single point, with respect to the archive A, we consider the problem:

$$I_{\epsilon}(\{u\}, A) = \max_{1 \le i \le m} \max_{a \in A} a_i / u_i \qquad (6.2)$$

Note that, we can maintain a list of the maximum values of $a_i$ for each coordinate $i$, $1 \le i \le m$, in an array of size $m$, which is trivially updated when the archive A is updated. Then, the computation of $I_{\epsilon}(\{u\}, A)$ takes $O(m)$ time. As such, calculating the binary $\epsilon$-indicator is expected to be much faster than calculating the binary hypervolume for our upper bound set, which should be particularly noticeable for a high number of objectives.

If a binary quality indicator is order-preserving (or order-reversing) with respect to the weak dominance relation when fixing the first parameter, which is the case for the binary hypervolume and $\epsilon$-indicator as discussed in Section 2.2, then its values can be cached for nodes in the queue that have not yet been selected and kept in a priority queue to more quickly select the next node to be processed. For a BeFS selection strategy this needs to be a global priority queue containing all the nodes that can be selected, whereas for the BeDFS selection strategy we need to maintain a set of priority queue for each level of the search tree. However, note that when considering a dichotomic branching strategy, there is in fact no need to keep any priority queue, since
after selecting the most promising node on a particular level, there is only a
single node remaining at that level.

One potential issue with keeping a priority queue is that when the archive
maintained by the BB changes, then, depending on the quality indicator, the
cached values may need to be updated and the priority queue needs to be
recomputed, which can be quite costly if done often. As such, it is questionable
whether or not the values should be kept in a priority queue. Our preliminary
experiments suggested that for the ε-indicator it is best to maintain a priority
queue at all times, since a reconstruction is rarely required. However, for the
binary hypervolume indicator, we found it was best to use a priority queue
only if the cached values are not updated often. In particular, we start by not
considering a priority queue and instead keep all the nodes in a vector that
can be searched in linear time to find the most promising node. Then, if there
are 10 consecutive calls to the selection methodology that do not update the
hypervolume of the archive, we build a priority queue from that vector. Once
the hypervolume of the archive changes, we go back to not using a priority
queue until there are 10 consecutive calls to the selection methodology that
do not update the hypervolume of the archive. Finally, to avoid unnecessary
quality indicator computations, we only recompute the quality indicator of the
upper bound after the archive changes on the nodes for which the previously
cached value was better than the current best, since the new quality indicator
value will remain the same or decrease.

**6.1.3 Experimental Study**

In this section, we carry out an experimental study to analyze the (anytime)
performance of the BeFS and BeDFS selection strategies on the MOBKP for
problem instances generated according to the procedure described in Chap-
ter 4. In particular, we considered 100 instances for each number of objectives
$m \in \{2, 3, 5, 7\}$. The remaining parameters were randomly sampled from the
following uniform distributions:

• $n \in \mathcal{U}(50, 150);$

• $\rho_v \in \mathcal{U}\left(\frac{6}{\pi} \sin^{-1} \frac{1}{2(1-m)}, 1\right);$

• $\rho_w \in \mathcal{U}(-1, 1);$

• $\omega \in \mathcal{U}(0.3, 0.7).$

We consider the following alternatives for the implementation of the BB
and IBB approaches:
* **Branching**: Dichotomic;

* **Branching order**: Default (Random) or $O^{sum}$;

* **Selection strategy**: DFS, BFS, $\varepsilon$-indicator BeFS, $\varepsilon$-indicator BeDFS, binary hypervolume BeFS, binary hypervolume BeDFS.

The BB and IBB approaches were implemented in C++, and the code is available at [33]. The code was compiled with GCC 10.2.0, and the experiments were carried out in parallel, one per thread, on a machine with two Intel(R) Xeon(R) Silver 4210R processors. The algorithms were run with a timeout of 100 seconds and an 8Gb memory limit.

In the results that follow we consider the performance of the BB and IBB approaches for different test scenarios. In particular, we measure the hypervolume of the archive found by an BB or IBB approach for a given problem instance considering a given CPU timeout value. There are a total of 100 instances for each number of objectives $m \in \{2, 3, 5, 7\}$, and for each instance we consider 200 distinct CPU timeout values evenly distributed on a log scale in the range $[1e-3, 1e2]$. Therefore, we consider a total of 20 000 test scenarios for each value of $m$. The code to reproduce the experiments, and to generate the tables and figures presented in the following sections, is available at [32].

## 2 objectives

Table 6.1 gives the ratio of test scenarios with 2 objectives for which the BB and IBB approaches using particular selection strategies found the best known archive, with respect to the hypervolume quality indicator, and considering two distinct branching orders. Note that, the best known archive is defined with respect to all the archives found by any BB or IBB approach using the same branching order for that test scenario, i.e., for that instance and CPU timeout value.

For the default branching order, we see that the IBB approaches guided by the binary hypervolume indicator have the best ratio, and that the traditional BB approaches have the worst ratio. The IBB approaches guided by the $\varepsilon$-indicator are slightly better than the BB approaches, but have small ratios compared against approaches guided by the hypervolume. Note that the sum of the ratios for each branching order may be greater than 1 since multiple algorithms can find an archive with the same hypervolume value. This is likely to happen in scenarios with large CPU timeout values since multiple approaches may find the Pareto set within that time.

For the $O^{sum}$ branching order, we see that the BB approach using the DFS selection strategy has the best ratio by a large margin. This indicates that a
<table><caption>Table 6.1: Ratio of test scenarios with 2 objectives for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</caption><thead><tr><th>Order</th><th>BFS</th><th>DFS</th><th>HV-BeFS</th><th>HV-BeDFS</th><th>ε-BeFS</th><th>ε-BeDFS</th></tr></thead><tbody><tr><td>Default</td><td>0.13</td><td>0.12</td><td><strong>0.56</strong></td><td>0.42</td><td>0.21</td><td>0.16</td></tr><tr><td>O<sup>sum</sup></td><td>0.14</td><td><strong>0.80</strong></td><td>0.28</td><td>0.21</td><td>0.18</td><td>0.18</td></tr></tbody></table>

good ordering of the items for the MOBKP can lead to a good archive, in terms of hypervolume, using the DFS selection strategy. Despite this, we see that the IBB approaches, especially those guided by the hypervolume, can sometimes find better, or equally good, archives. Moreover, it should be noted that such an ordering may not be easy to achieve for every problem, and further analysis of the data reveals that the IBB approaches considering a default branching order, in particular those guided by the hypervolume quality indicator, can often achieve archives with hypervolume values that are not much worse, and sometimes even better, than those found by the DFS selection strategy with the O<sup>sum</sup> branching order. This suggests that our IBB approaches are particularly interesting when a good branching order for the DFS selection strategy is not known.

Figure 6.2 gives the ratio of test scenarios with specific CPU timeout values for which a given approach was able to find the best archive. We see that for the default branching order, the IBB approach guided by the binary hypervolume using a BeDFS selection strategy got the highest ratio for small CPU timeout values. However, for larger CPU timeout values the IBB approach guided by the binary hypervolume using a BeFS selection strategy surpasses it. Note that, since we are measuring archive quality in terms of hypervolume, it is not surprising that the approaches guided by the binary hypervolume have the best performance. Also, note that the sum of ratios at CPU timeout values closer to 100 are clearly greater than for values closer to 1. We recall that this happens because for some instances the BB and IBB approaches can all find the Pareto set. For the O<sup>sum</sup> branching order, we see that the BB approach following a DFS selection strategy, has the best ratio for all CPU-timeout values.

Figure 6.3 gives the mean error, and standard deviation, in terms of the difference between the hypervolume found by a given selection strategy and the hypervolume found by any other strategy considering the same branching order, when that difference is greater than 0. We discard values where the difference is equal to 0 because we want to evaluate how close a given strategy is to the best, when that strategy itself is not the best. For the default branching order, we see that the BFS and DFS selection strategies give the worst error for
<figure><img src="image_89.png" /><figcaption>Figure 6.2: Ratio of test scenarios, with 2 objectives and a given CPU timeout value, for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</figcaption></figure>

all timeout values, which means that not only can these selection strategies rarely find the best archive, as evidenced by the ratios shown previously, but also that the archives found by those strategies are significantly worse than those found by the **IBB** approaches. On the other hand, the **BeDFS** strategies give the smallest error for small timeout values, and **BeFS** strategies give the smallest error for large timeout values. This indicates that, even when these strategies cannot find the best archive, the difference in terms of hypervolume to the best is small. In particular, note that the approaches guided by the $\epsilon$-indicator, despite having a small ratio, generally have small errors. As such all **IBB** approaches are generally quite good, as they often find the best archive or otherwise have a small error.

For the $O^{sum}$ branching order, we see that the **BFS** strategy gives the largest error, but that the **DFS** strategy gives the smallest error. This is not too surprising given the results in terms of ratio. But we also see that the errors of
<figure><img src="image_90.png" /><figcaption>Figure 6.3: Mean and standard deviation of the difference between the quality of the archive found by a selection strategy for instances with 2 objectives and a particular CPU timeout value, and the quality of the best archive found, when that difference is greater than 0.</figcaption></figure>
the IBB approaches are now more significant, with the exception of the BeDFS approach guided by the hypervolume, which generally has a small error. However, we see that the error for the BeFS strategies is decreasing significantly, and we would expect the error to become smaller than that of the BeDFS strategies for larger timeout values.

### 3 objectives

Table 6.2 gives the ratio of test scenarios with 3 objectives for which a given BB or IBB approach found an archive with the best hypervolume. For the default branching order, we see that the BeFS approach guided by the $\epsilon$-indicator has the best ratio, followed by the IBB approaches guided by the hypervolume indicator. This contrasts with the previous scenarios with 2 objectives, where the approaches guided by the hypervolume indicator had much better ratio than the IBB approaches guided by the $\epsilon$-indicator. This is not too surprising since the cost of computing the hypervolume contribution for the upper bound point is significantly higher than the cost of computing the $\epsilon$-indicator contribution for instances with 3 or more objectives, as discussed in Section 6.1.2. Nonetheless, the IBB approaches guided by the hypervolume still have a higher ratio than the BeDFS approach guided by the $\epsilon$-indicator, despite their increased computational cost. Lastly, we see that all IBB approaches have better ratio values than the traditional BB approaches, as in the previous case.

For the $O^sum$ branching order, we see that the BB approach using a DFS selection strategy once again has the best ratio by a large margin. However, we see that this ratio decreased slightly compared to the previous case with 2 objectives. Moreover, we remark that the IBB approaches guided by the hypervolume indicator also decreased compared to the previous case, and that the BeFS approach guided by the $\epsilon$-indicator increased, such that it is now the second best approach tied with the BeFS approach guided by the hypervolume indicator.

Figure 6.4 gives the ratio of test scenarios with a given CPU timeout value, for which a given approach was able to find the archive with the best hypervolume. For the default branching order, we see that the BeDFS approach guided

<table><caption>Table 6.2: Ratio of test scenarios with 3 objectives for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</caption><thead><tr><th>Order</th><th>BFS</th><th>DFS</th><th>HV-BFS</th><th>HV-BeDFS</th><th>ε-BFS</th><th>ε-BeDFS</th></tr></thead><tbody><tr><td>Default</td><td>0.12</td><td>0.11</td><td>0.36</td><td>0.33</td><td><strong>0.42</strong></td><td>0.15</td></tr><tr><td>O<sup>sum</sup></td><td>0.12</td><td><strong>0.74</strong></td><td>0.23</td><td>0.15</td><td>0.23</td><td>0.15</td></tr></tbody></table>
<figure><img src="image_91.png" /><figcaption>Figure 6.4: Ratio of test scenarios, with 3 objectives and a given CPU timeout value, for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</figcaption></figure>

by the hypervolume indicator is the approach with the highest ratio for CPU timeout values below 1e-2. Then, it is tied with the BeFS approach guided by the hypervolume indicator until a CPU timeout value close to 1e-1. After that, the BeFS approach guided by the $\epsilon$-indicator has the best ratio. This shows, that the IBB approaches guided by the hypervolume indicator are still preferable in an initial phase, despite the higher computational costs. However, for large CPU timeout values the BeFS approach guided by the $\epsilon$-indicator is clearly preferred.

For the $O^{sum}$ branching order, the DFS is clearly the best selection strategy at all times, much like it was for 2 objectives, but we see that its ratio is generally not as high as in that case. With regards to the other approaches, we see that the BeFS selection strategy guided by the hypervolume has a better ratio for CPU timeout values below 1e0, but the BeFS selection strategy guided by the $\epsilon$-indicator has a better ratio for CPU timeout values greater than those.
<figure><img src="image_92.png" /><figcaption>Figure 6.5: Mean and standard deviation of the difference between the quality of the archive found by a selection strategy for instances with 3 objectives and a particular CPU timeout value, and the quality of the best archive found, when that difference is greater than 0.</figcaption></figure>
Figure 6.5 gives the error of the archive found by a selection strategy that did not find the best archive for instances with 3 objectives. For the default branching order, we see that the BeDFS selection strategy guided by the hypervolume indicator gives the smallest error for small timeout values, whereas the BeFS strategy guided by the $\epsilon$-indicator gives the smallest error for large timeout values, which is in accordance with the ratio results. When considering the $O^{sum}$ branching order we see that, besides the DFS strategy, these two strategies also have the smallest error.

## 5 objectives

Table 6.3 gives the ratio of test scenarios with 5 objectives for which the different selection strategies found the archive with the best hypervolume. For the default branching order, the BeFS selection strategy guided by the $\epsilon$-indicator has the best ratio by a large margin. The second and third best ratios are for the BeDFS approaches guided by the $\epsilon$-indicator and hypervolume indicator respectively. The worst approach is the BeFS approach guided by the hypervolume, which is worse than the naive BB approaches. These results indicate that the computational cost of the binary hypervolume indicator for 5 objectives is a problem for the performance of the IBB approaches guided by that indicator. For the $O^{sum}$ branching order, we see that the IBB approaches guided by the hypervolume are also the worst. But we see that the BeFS strategy guided by the $\epsilon$-indicator has a ratio that is much better than in previous cases, and not far from the ratio of the DFS strategy, which is still the best.

Figure 6.6 gives the ratio of test scenarios with a given CPU timeout value for which a given approach was able to find the archive with the best hypervolume. For the default branching order, we see that the BeDFS approach guided by the $\epsilon$-indicator is the approach with the highest ratio for CPU timeout values below $2e-2$. For CPU timeout values greater than $2e-2$, the BeFS approach guided by the $\epsilon$-indicator has the best ratio by a large margin. It is also worth noting that the IBB approaches guided by the hypervolume indicator have small ratio for almost all CPU timeout values, with the exception of the BeDFS approach which can achieve a ratio greater than 0.25 for CPU timeout values

<table><caption>Table 6.3: Ratio of test scenarios with 5 objectives for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</caption><thead><tr><th>Order</th><th>BFS</th><th>DFS</th><th>HV-BFS</th><th>HV-BeDFS</th><th>ε-BeFS</th><th>ε-BeDFS</th></tr></thead><tbody><tr><td>Default</td><td>0.10</td><td>0.09</td><td>0.04</td><td>0.14</td><td><strong>0.66</strong></td><td>0.23</td></tr><tr><td>O<sup>sum</sup></td><td>0.10</td><td><strong>0.63</strong></td><td>0.05</td><td>0.06</td><td>0.44</td><td>0.12</td></tr></tbody></table>
<figure><img src="image_93.png" /><figcaption>Figure 6.6: Ratio of test scenarios, with 5 objectives and a given CPU timeout value, for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</figcaption></figure>

close to $1e-1$, despite the fact that the binary hypervolume indicator has a high computational cost. Note that, in the BeDFS case the binary indicator does not need to be computed as often, which explains why the approach can sometimes achieve good results. Nonetheless, this shows that, as expected, the high computation cost of the hypervolume indicator has a big impact on the performance of the IBB approaches guided by that indicator. However, we see that the $\epsilon$-indicator, which has a small computational cost, can achieve very good results despite the fact that we are measuring archive quality in terms of the hypervolume indicator.

For the $O^{sum}$ branching order, the DFS is the best selection strategy for CPU timeout values smaller than $2e-1$, as in the previous cases. However, we see that the BeFS approach guided by the $\epsilon$-indicator has a better ratio for CPU timeout values greater than that. This contrasts with the previous cases for 2 and 3 objectives. One plausible reasoning is that it is more difficult to get a good
<figure><img src="image_94.png" /><figcaption>Figure 6.7: Mean and standard deviation of the difference between the quality of the archive found by a selection strategy for instances with 5 objectives and a particular CPU timeout value, and the quality of the best archive found, when that difference is greater than 0.</figcaption></figure>
approximation of the Pareto front, i.e., an approximation that uniformly covers the whole Pareto front, with a static order as the number of objectives increases, due to the conflicting relation between multiple objective functions. That is, the DFS strategy can quickly find good solutions in a particular direction in objective space as it goes down in the search tree, which explains why it is initially quite good. However, the approach then struggles to find solutions that are far from that initial direction since it gets stuck at the bottom of the search tree in a particular direction if the lower and upper bounds are not very tight. On the other hand, the BeFS approach can explore different directions more easily if the indicator that guides the search favors uniformly distributed points in the objective space. Nonetheless, further analysis is needed to understand what problem properties lead to this behavior.

Figure 6.7 gives the mean and standard deviation of the error of a selection strategy for instances with 5 objectives, when it failed to find the best archive. For the default branching order, we see that the BeFS selection strategy guided by the $\epsilon$-indicator most often has the smallest error, and that the BeDFS approaches guided by either indicator also have small errors when the CPU timeout values are small. These results are in line with those in Figure 6.6 since the best approaches at each stage, are also the ones that have the smallest error. For the $O^{sum}$ branching order, we see that the errors of the IBB approaches follow a similar trend but are significantly larger. On the other hand, the DFS approach has a very small error at all times. Notably, the small error for large CPU timeout values indicates that, despite not being the approach that most often finds the best archive for such timeout values, it can very often find an archive that is close to the best.

## 7 objectives

Table 6.4 gives the ratio of test scenarios with 7 objectives for which the different selection strategies found the archive with the best hypervolume. The results are quite similar to those we found for 5 objectives. In particular, for the default branching order, the BeFS selection strategy guided by the $\epsilon$-indicator has the best ratio by a large margin, the second and third best ratios are for the BeDFS approaches guided by the $\epsilon$-indicator and hypervolume indicator respectively, and the worst approach is by the BeFS approach guided by the hypervolume. For the $O^{sum}$ branching order, we see that the DFS strategy is the best, and the BeFS guided by the $\epsilon$-indicator is the second best, whereas the other strategies are all much worse than these two. These results, again highlight that the computational cost of the hypervolume has a large impact on the performance of the IBB approaches guided by binary hypervolume.
<table><caption>Table 6.4: Ratio of test scenarios with 7 objectives for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</caption><thead><tr><th>Order</th><th>BFS</th><th>DFS</th><th>HV-BeFS</th><th>HV-BeDFS</th><th>ε-BeFS</th><th>ε-BeDFS</th></tr></thead><tbody><tr><td>Default</td><td>0.07</td><td>0.08</td><td>0.01</td><td>0.12</td><td><strong>0.62</strong></td><td>0.21</td></tr><tr><td>O<sup>sum</sup></td><td>0.06</td><td><strong>0.65</strong></td><td>0.03</td><td>0.04</td><td>0.39</td><td>0.09</td></tr></tbody></table>

Figure 6.8 gives the ratio of test scenarios with a given CPU timeout value for which a given approach was able to find the archive with the best hypervolume. Once again, the results are similar to those for instances with 5 objectives. In particular, for the default branching order, the BeDFS approach guided by the ε-indicator has a large ratio for small CPU timeout values, and the BeFS approach guided by the ε-indicator has a much larger ratio than all others

<figure><img src="image_95.png" /><figcaption>Figure 6.8: Ratio of test scenarios, with 7 objectives and a given CPU timeout value, for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</figcaption></figure>
<figure><img src="image_96.png" /><figcaption>Figure 6.9: Mean and standard deviation of the difference between the quality of the archive found by a selection strategy for instances with 7 objectives and a particular CPU timeout value, and the quality of the best archive found, when that difference is greater than 0.</figcaption></figure>
strategies for large CPU timeout values. For the *O*<sup>sum</sup> branching order, we see
that the DFS strategy has the best ratio most often, but that for large CPU time-
out values the BeFS approach guided by the ε-indicator is better. Notably, the
difference between the ratio of this strategy and the ratio of the DFS strategy
is much greater than for 5 objectives, which suggests that as the number of
objectives increases the difference is likely to be more significant.

Figure 6.9 gives the mean error and corresponding standard deviation for each selection strategies, when the archive found for instances with 7 objectives was not the best. The results are similar to those for instances with 5 objectives. However, we can see that both the errors are slightly larger in this case, which indicates that the error increases with the number of objectives.

6.1.4 Discussion

In the previous section we compared the proposed IBB approaches guided
by the binary hypervolume and ε-indicator against the naive BB approaches
using a DFS and BFS search strategies to solve instances of the MOBKP. In
particular, we analyzed which approaches found the best archive with respect
to the hypervolume quality indicator on a set of instances and CPU timeout
values, considering two distinct branching orders. We also analyzed the mean,
and standard deviation, of the difference in relative hypervolume between the
archive found by a given approach, and the best archive found by any strategy
for the same CPU-time.

For a default branching order, which corresponds to a random ordering of
the items, we saw that the IBB approaches often found the best archive, and
gave the smallest error. In particular, the BeDFS selection strategies often had
the best performance for small CPU timeout values, and the BeFS strategies had
the best performance for medium and large CPU timeout values. Moreover,
for 2 objectives the IBB approaches guided by the hypervolume performed
better, and for 5 and 7 objectives the IBB approaches guided by the ε-indicator
performed better. For 3 objectives, the BeDFS guided by the hypervolume had
better performance for small CPU timeout values, and the BeFS guided by the
ε-indicator had better performance for large CPU timeout values. As such, we
conclude that for these MOBKP instances, and for a random branching order
our IBB approach is significantly better than the naive DFS and BFS selection
strategies.

For the *O*<sup>sum</sup> branching order the results favored the DFS strategy in most
scenarios, which indicates that a good branching order is particularly important
for that strategy. However, it is worth noting that such an order might not
be available for every problem. Moreover, we saw that for large CPU timeout
values and instances with 5 and 7 objectives, the DFS approach started to have
worse performance in terms of finding the best archive, and the BeFS strategy
guided by the ε-indicator was more often able to find the best archive. Still, the
difference in archive quality between the archive found by the DFS strategy
and the best archive was quite small, which means that the archive found was
quite good despite not being the best.

Further analysis also revealed that the difference in archive quality between
the best archive found by the IBB approaches with the default order, and the
best archive with the $O^{sum}$ branching order, was often quite small. This sug-
gests that the IBB approaches can often find good archives without the need
to devise any particular branching order.

For future work, we consider that it would be relevant to study the perfor-
mance of the IBB approaches on a broader set of instances to better understand
what characteristics of the problem are significant to each strategy. One ques-
tion that arose, but for which preliminary analysis revealed no answer was
for what kinds of instances is the DFS strategy with a $O^{sum}$ branching order
not the best approach. Moreover, it would be relevant to analyze the impact
of different lower and upper bound sets on the performance of the IBB ap-
proaches. Lastly, it would be interesting to analyze the performance of the IBB
approaches on different problems, in particular, problems for which no clear
branching order is known.

**6.2 Branch-and-Bound Online Selection**

**6.2.1 Methodology**

In Section 6.1.3, we highlighted that IBB approaches following a BeDFS search
strategy can achieve good performance for small CPU timeout values, but that
for large medium and large CPU timeout values the BeFS search strategies
more often had the best performance. Analyzing the anytime traces of the
approaches also revealed that the BeDFS can often find an archive with good
quality, but then struggles to significantly improve the archive over time. By
contrast, BeFS approaches cannot find such a good archive for small CPU times,
but can consistently improve archive quality over time.

Taking these observations into account, we propose an online selection
methodology to select between BB search strategies in order to improve any-
time performance. We start with an IBB approach that uses a BeDFS search
strategy. Then, we swap to a BeFS search strategy once we consider that the
initial approach can no longer improve archive quality significantly. In partic-
ular, we monitor the relative difference in archive quality, with respect to the
total archive quality, over the last *k* explored nodes. If this relative difference is
below a certain threshold value, denoted by *δ*, then we swap approaches. Note
that, following the analysis in Section 6.1.3, a BeDFS search strategy guided
by the binary hypervolume is initially considered if *m* < 4, or guided by the
*ε*-indicator if *m* ≥ 4. Then, we swap to a BeFS search strategy guided by the
binary hypervolume if *m* < 3, or guided by the *ε*-indicator if *m* ≥ 3.

Finally, we consider swapping back to the original BeDFS search strategy
if the number of active nodes is greater than a parameter *ℓ*, to avoid running
out of memory.

**6.2.2 Experimental Study**

In this section, we carry out an experimental study to analyze the (anytime)
performance of the online selection methodology described in the previous
section. We empirically set the parameters *k* = 100, *δ* = 1e-6, and *ℓ* = 100000
for the online selection methodology since these parameters gave good results
in preliminary experiments. For comparison, we consider the same instances
and algorithms used for the experiments in Section 6.1.3.

The online methodology was implemented in C++, and the code is available
at [33]. The experiments were carried out in parallel, one per thread, on a
machine with two Intel(R) Xeon(R) Silver 4210R processors. The algo-
rithms were run with a timeout of 100 seconds and an 8Gb memory limit. We
consider the performance of the BB, IBB, and online approaches on the same
scenarios presented in Section 6.1.3. The code to reproduce the experiments
and to generate the tables and figures presented in the following sections is
available at [32].

**2 Objectives**

Table 6.5 gives the ratio of test scenarios with 2 objectives for which an ap-
proach found the best archive. For the default branching order, we see that
the online selection methodology has a high ratio (0.83) that is significantly
larger than all other approaches. This indicates that our approach is working
correctly, and that the changing algorithms positively improves anytime be-
havior. For the *O*<sup>sum</sup> branching order, we see that the DFS approach still has
the best ratio, which is not surprising since it was the best approach in the
previous experiments, and was not considered for the online selection method-
ology. However, it is worth noting that the ratio of the DFS approach decreased
slightly, from 0.8 to 0.72, compared to the ratio values without the online selec-
<table><caption>Table 6.5: Ratio of test scenarios with 2 objectives for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</caption><thead><tr><th>Order</th><th>BFS</th><th>DFS</th><th>HV-BeFS</th><th>HV-BeDFS</th><th>ε-BeFS</th><th>ε-BeDFS</th><th>Online</th></tr></thead><tbody><tr><td>Default</td><td>0.12</td><td>0.12</td><td>0.28</td><td>0.16</td><td>0.13</td><td>0.14</td><td><strong>0.83</strong></td></tr><tr><td>O<sup>sum</sup></td><td>0.14</td><td><strong>0.72</strong></td><td>0.20</td><td>0.20</td><td>0.17</td><td>0.18</td><td>0.34</td></tr></tbody></table>

tion methodology, which means that our online methodology approach could sometimes find a better archive in cases where the individual IBB approaches could not. Nonetheless, these results indicate that taking into account the ordering of the items to select the initial selection strategy could improve the performance of our online selection methodology further. Lastly, we see that, as for the default order, the online selection methodology has the best ratio of all other approaches.

Figure 6.10 gives the ratio of test scenarios for which a given approach was able to find the best archive, at different CPU timeout values. For the default branching order, we see that the online selection methodology has the best ratio at all times. Note that, despite the fact that our online selection methodology starts with the BeDFS selection strategy guided by the hypervolume, that same approach is still the second best for small CPU timeout values despite both approaches being deterministic. This is due to the fact that we are considering anytime performance in terms of CPU time, as such, slightly different conditions during the execution of the experiments can lead to either approach having better performance. However, we see that for CPU timeout values close to 1e-2, when the BeFS selection strategy guided by the hypervolume surpasses the BeDFS, the online methodology is significantly better than the latter, which indicates that the online methodology is in fact changing to the BeFS approach correctly, and that this increases anytime performance significantly. For the O<sup>sum</sup> branching order, we see that the online selection methodology is often better than the IBB approaches.

Figure 6.11 gives the mean error, and standard deviation, in terms of the difference between the relative hypervolume of an archive found by a given selection strategy and the best archive found by any other strategy considering the same branching order, when that difference is greater than 0. We see that, for both branching orders, the online approach has a very small error. As such, we see that the online approach is not only good in terms of the ratio, but also that when it does not find the archive with best quality for a particular test scenario, it finds an archive that is very close to the best.
<figure><img src="image_97.png" /><figcaption>Figure 6.10: Ratio of test scenarios, with 2 objectives and a given CPU timeout value, for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</figcaption></figure>
<figure><img src="image_98.png" /><figcaption>Figure 6.11: Mean and standard deviation of the difference, in terms of hyper-volume, between the archive found by a selection strategy and the best archive found, when the difference is greater than 0.</figcaption></figure>
## 3 Objectives

Table 6.6 gives the ratio of test scenarios where each approach found the best archive. For the default branching order, we see that the online selection methodology still has the best ratio. However, there is a decrease compared to the previous case with 2 objectives. Moreover, we see that the BeFS strategy guided by the hypervolume increased slightly, and that the other approaches have similar ratio values. Compared to the results with 3 objectives, but without the online selection methodology, we see that both the strategies considered in our online selection methodology, that is, the BeDFS strategy guided by the hypervolume and the BeFS strategy guided by the $\epsilon$-indicator, decreased significantly, while the other two IBB strategies did not. As the BeFS strategy guided by the hypervolume has a ratio that is quite significant, this suggests that opting not to consider this strategy in our approach is detrimental to the performance of our online selection methodology. As such, to further improve our online methodology we should consider both BeFS strategies when changing algorithms. Unfortunately, preliminary experiments did not reveal any relation between the characteristics of the instances and which BeFS strategy had the best performance. Therefore, further analysis is required to better understand this, and successfully select between the two strategies.

For the $O^{sum}$ branching order, the results are similar to the previous case with 2 objectives. In particular, we see that the online selection methodology had better performance than the other IBB approaches, and that the ratio values for the DFS strategy decreased slightly, from 0.74 to 0.7, compared to the results without the online selection methodology.

Figure 6.12 gives the ratio at the sampled CPU timeout values. For the default branching order, we see that, while in the previous case with 2 objectives the online methodology got a ratio value close to 1 for certain CPU timeout values, in this case the maximum ratio value is close to 0.75. The fact that the BeFS strategy guided by the hypervolume has significant ratio values, indicates that not considering that strategy for online selection is decreasing the performance of our online methodology. Still, the online methodology has

<table><caption>Table 6.6: Ratio of test scenarios with 3 objectives for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</caption><thead><tr><th>Order</th><th>BFS</th><th>DFS</th><th>HV-BeFS</th><th>HV-BeDFS</th><th>ε-BeFS</th><th>ε-BeDFS</th><th>Online</th></tr></thead><tbody><tr><td>Default</td><td>0.11</td><td>0.11</td><td>0.34</td><td>0.15</td><td>0.12</td><td>0.14</td><td><strong>0.65</strong></td></tr><tr><td><i>O</i><sup>sum</sup></td><td>0.12</td><td><strong>0.70</strong></td><td>0.21</td><td>0.14</td><td>0.14</td><td>0.15</td><td>0.30</td></tr></tbody></table>
the best ratio at all times, which shows that it is expectedly improving any-
time performance. For the *O*<sup>sum</sup> branching order, we see that the DFS strategy
clearly has the best ratio at all CPU timeout values. Still, we see that, as with
2 objectives, the online selection methodology is often the best between the
other approaches.

Figure 6.13 gives the error for test scenarios with 3 objectives, at the sam-
pled CPU timeout values. As with 2 objectives, we see that the online selection
methodology has a very small error for both branching orders. This means
that even if it does not find the archive with the best quality, it can find an
archive with quality close to that.

<figure><img src="image_99.png" /><figcaption>Figure 6.12: Ratio of test scenarios, with 3 objectives and a given CPU timeout value, for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</figcaption></figure>
<figure><img src="image_100.png" /><figcaption>Figure 6.13: Mean and standard deviation of the difference, in terms of hyper-volume, between the archive found by a selection strategy and the best archive found, when the difference is greater than 0.</figcaption></figure>
## 5 Objectives

Table 6.7 gives the ratio of test scenarios with 5 objectives for which each approach found the best archive. We see that the online selection methodology has the best ratio for the default branching order, as in previous cases. However, in contrast with previous cases, the BeFS strategy guided by the $\epsilon$-indicator has the best performance among all others. This is not too surprising given the results we saw without the online selection methodology. However, it is somewhat surprising that the value is so high considering that we are using that strategy in our online approach. Moreover, the value for the online selection methodology is not as high as in previous cases. For the $O^{sum}$ branching order, we see that, as in previous cases the DFS strategy has the highest ratio, but that its ratio is slightly lower than for the experiments without the online selection methodology. However, more surprisingly, we see that the online selection methodology is the best among the other approaches, but the BeFS strategy guided by the $\epsilon$-indicator has a ratio value that is only slightly worse.

<table><caption>Table 6.7: Ratio of test scenarios with 5 objectives for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</caption><thead><tr><th>Order</th><th>BFS</th><th>DFS</th><th>HV-BeFS</th><th>HV-BeDFS</th><th>ε-BeFS</th><th>ε-BeDFS</th><th>Online</th></tr></thead><tbody><tr><td>Default</td><td>0.10</td><td>0.09</td><td>0.04</td><td>0.09</td><td>0.30</td><td>0.14</td><td><strong>0.60</strong></td></tr><tr><td>O<sup>sum</sup></td><td>0.10</td><td><strong>0.59</strong></td><td>0.05</td><td>0.06</td><td>0.22</td><td>0.11</td><td>0.36</td></tr></tbody></table>

Looking at the ratio over different CPU timeout values in Figure 6.14, we see that at CPU timeout values close to 1e-2 the online selection methodology improves significantly, which is to be expected due to the swap between strategies, and indicates that the methodology is correctly, and favorably, changing strategies. However, at around 1e-1, we see a meaningful drop in the ratio values of the online selection methodology. This appears to coincide, first with an increase in ratio for the BeDFS strategy guided by the hypervolume indicator, and second with an increase in ratio from the BeFS strategy guided by the $\epsilon$-indicator. Analysis of the individual anytime traces shows that the BeDFS strategy guided by the hypervolume can sometimes achieve very good archive quality at such CPU times, despite a generally worse start compared to the same strategy guided by the $\epsilon$-indicator. Therefore, if a DM establishes that small CPU timeout values are not relevant, and we incorporate that preference into the selection, then it could make sense to choose the BeDFS guided by the hypervolume initially. For the second case, the anytime traces reveal that the BeFS strategy guided by $\epsilon$-indicator has an anytime performance that is very
<figure><img src="image_101.png" /><figcaption>Figure 6.14: Ratio of test scenarios, with 5 objectives and a given CPU timeout value, for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</figcaption></figure>

similar to that of the online methodology for large CPU time values. Therefore, the difference in archive quality between the two is very small, and the drop in ratio is, for that reason, not very significant.

For the *O*<sup>sum</sup> branching order, we see that the DFS approach has very good ratio values in the beginning but at around 1e-1 our online methodology has similar ratio values. Moreover, for large CPU timeout values the BeFS approach guided by the ε-indicator surpasses both the online selection methodology and the DFS. As discussed in the previous paragraph, this happens because for large CPU time values both the online methodology and the BeFS strategy have very similar anytime performance. Therefore, the difference in ratio between the two is not significant.

Figure 6.15 gives the error for each strategy, when it could not find the archive with the best quality, in terms of the difference between the quality of the archive it found and the best. For the default branching order, we see that,
<figure><img src="image_102.png" /><figcaption>Figure 6.15: Mean and standard deviation of the difference, in terms of hyper-volume, between the archive found by a selection strategy and the best archive found, when the difference is greater than 0.</figcaption></figure>
as in the previous cases, the error of the online selection methodology is very small for all CPU timeout values. On the other hand, we see an increase in its error for the $O^{sum}$ branching order compared to the previous cases. Nonetheless, it is still the IBB approach with the smallest error.

## 7 Objectives

Table 6.8 gives the ratio of test scenarios with 7 objectives for which each strategy was able to find the archive with best quality. Overall, we see that results are similar to the case of 5 objectives. In particular, for the default branching order the online methodology has the best ratio value, and the BeFS strategy guided by the $\epsilon$-indicator the second best. For the $O^{sum}$ branching order, we have that the DFS has the best ratio, followed by the online selection methodology and the BeFS strategy guided by the $\epsilon$-indicator.

<table><caption>Table 6.8: Ratio of test scenarios with 7 objectives for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</caption><thead><tr><th>Order</th><th>BFS</th><th>DFS</th><th>HV-BeFS</th><th>HV-BeDFS</th><th>ε-BeFS</th><th>ε-BeDFS</th><th>Online</th></tr></thead><tbody><tr><td>Default</td><td>0.07</td><td>0.07</td><td>0.01</td><td>0.08</td><td>0.26</td><td>0.10</td><td><strong>0.58</strong></td></tr><tr><td>O<sup>sum</sup></td><td>0.06</td><td><strong>0.58</strong></td><td>0.03</td><td>0.03</td><td>0.19</td><td>0.08</td><td>0.35</td></tr></tbody></table>

Figure 6.16 gives the ratio values over the CPU timeout values. For the default branching order, we see that the online selection methodology is not always the best for very small CPU timeout values. However, analysis of the individual anytime traces reveals that this happens because both the online methodology and the BeDFS strategy guided by the $\epsilon$-indicator have very similar anytime behavior in the beginning, since the former is using the latter, and due to fluctuations runtime conditions the latter is sometimes better. However, after CPU timeout values 1e-2, we see that the online selection methodology increases significantly due to a meaningful change of algorithms. Then, at CPU timeout values 1e-1 we see a slight decrease. As in the previous case with 5 objectives, this is first due to the BeDFS strategy guided by the hypervolume indicator sometimes having better performance than the IBB approaches guided by the $\epsilon$-indicator at those times, and later because the BeFS strategy guided by the $\epsilon$-indicator has very similar anytime performance compared to the online selection methodology which uses the former. For the $O^{sum}$ branching order, the results are very similar to the case with 5 objectives.

Figure 6.17 gives the error of each approach at the sampled CPU timeout values. For the default branching order, we see that the online methodology has
<figure><img src="image_103.png" /><figcaption>Figure 6.16: Ratio of test scenarios, with 7 objectives and a given CPU timeout value, for which a selection strategy found the best archive with respect to the hypervolume quality indicator.</figcaption></figure>
<figure><img src="image_104.png" /><figcaption>Figure 6.17: Mean and standard deviation of the difference, in terms of hyper-volume, between the archive found by a selection strategy and the best archive found, when the difference is greater than 0.</figcaption></figure>
the smallest error at all times, as in the previous cases. For the *O*<sup>sum</sup> branching order, we see that, besides the DFS approach, the online methodology generally has the smallest error. However, at CPU timeout values close to 1e-1, the BeDFS approach guided by the hypervolume has a smaller error, which is in line, with what was explained in the previous paragraph with regards to the anytime performance of the approach for those CPU time values.

### 6.2.3 Discussion

The results for the online selection methodology presented in the previous section show that this methodology does improve anytime performance, as we expected during its conception. In particular, we see that the ratio of test scenarios for which this methodology was able to find the archive the best quality is generally very high when considering a default branching order. For the *O*<sup>sum</sup> branching order, we saw that the DFS strategy is still often the best. However, there were a small number of scenarios where the DFS strategy was better than the individual IBB, but worse than the online methodology. Nonetheless, this means that only considering IBB approaches is not always the best approach, since with a good branching order the DFS strategy often found the best archive.

We also saw that fixing the initial and secondary strategies a priori resulted in some cases where the other IBB approaches that were not chosen were able to find an archive with better quality. As such, in the future, it would be relevant to consider an online selection methodology that is capable of selecting which approaches are the best taking into account the characteristics of the instance being solved, and the anytime preferences of the DM, similarly to the offline selection methodology presented in Chapter 5.

Lastly, in this experimental study we chose parameters *k*, *δ* and *ℓ* that gave good results during a preliminary analysis but did not thoroughly study their effect. As such, it would be relevant to investigate the impact of these parameters in the future.

## 6.3 Conclusion

In this chapter, we started by presenting the IBB framework, which consists of a BB for multi-objective optimization problems guided by quality indicators. Then, we performed an experimental study on the MOBKP considering four distinct IBB approaches, that use the BeFS and BeDFS selection strategies, and two quality indicators, the binary hypervolume and the ε-indicator, and two naive BB approaches that use the DFS and BFS selection strategies. The
experimental results showed that our IBB approaches are very often better
than the naive BB approaches, when considering a random ordering of the
items for the MOBKP. Note that we say that an approach is better than another
for a given test scenario, if the quality of the archive returned by that approach,
in terms of hypervolume, is better. Moreover, we noted that the approaches
guided by the hypervolume indicator were often better than the ones guided by
the ε-indicator for instances with 2 objectives, which is to be expected since we
are measuring quality in terms of the hypervolume indicator. However, with
the increase in the number of objectives, the approaches guided by ε-indicator
became better due to the computational overhead of the hypervolume. We also
noted that a good ordering of items can lead to very good results for the DFS
strategy. Despite this, we saw that the difference in quality between the archive
found by some IBB approaches, and the archive found by the DFS strategy, was
often not very large.

Then, we considered an online selection methodology that can change
between IBB strategies online, while solving a previously unseen problem
instance. This is of particular interest, since in the previous results we had
seen that BeDFS strategies were often quite good for small CPU time values,
whereas BeFS strategies were better for large values. Therefore, our online
selection methodology changes between these two strategies. The empirical
results showed that changing algorithms did in fact result in significant im-
provements in anytime performance, and this approach was most often the
best for a random ordering of the items. However, we also noted that, by only
considering two IBB approaches for each problem meant that the results were
not as good as they could have been. Therefore, one direction for future work
is to consider an online selection that can select between any number of BB
and IBB approaches, and perhaps even other algorithms, taking into account
the characteristics of the problem instance. Moreover, we also did not take
into account the anytime preferences of the DM during the selection. As such,
another direction for the future is to incorporate these anytime preferences
into the online selection.

Finally, it would also be relevant to study the performance of the IBB frame-
work, and of the online selection methodology, on other problems, and to
compare it against other state-of-the-art algorithms.
<figure><img src="image_105.png" /></figure>
# Chapter 7

## Conclusion

### 7.1 Concluding Remarks

In this thesis, we considered the problem of automatically selecting between algorithms for MOO problems. In particular, we focused on the selection between anytime MOO algorithms, such that the anytime performance of the chosen algorithm is optimal with respect to the preferences of the DM. However, before looking at the ASP problem itself, we started by considering the problem of theoretically and empirically modeling the anytime performance of MOO algorithms. In the following, we discuss the main contributions of each chapter, first related to the theoretical and empirical models of anytime performance for MOO algorithms, and then with regards to the offline and online selection of MOO algorithms.

#### 7.1.1 Theoretical Models

In Chapter 3, we presented two variants of a theoretical model of anytime performance for scalarization techniques to MOO problems with 2 objectives that find, at each iteration, an efficient solution that maximizes the hypervolume contribution. It is worth noting that, when developing these models, there was no known scalarization technique that found efficient solutions that maximized hypervolume contribution. However, Paquete et al. [61] have recently proposed such a scalarization technique, whose anytime behavior can, by definition, be modeled by these theoretical models.

The first model is given by an analytical formulation that, while simple and computationally fast, requires several assumptions that may not always be practical, such as the shape of the non-dominated set and the location of the reference point for the hypervolume indicator. The second model is given by an algorithm designed to overcome these limitations. It can be used for
any problem where the set of non-dominated points can be approximated by
a piecewise linear function with any number of linear segments, and for any
reference point. One disadvantage of the second model is that it is slower to
compute than the first model. Still, empirical results showed that it is very fast
for parameterizations that we consider reasonable for most scenarios, and as
such we expect that this is not likely to be a problem in practice.

An experimental study was carried out on two variants of the bi-objective
knapsack problem, showing that these models, especially the second one, can
very accurately model the behavior of a scalarization technique that finds a
solution that maximizes hypervolume contribution at each iteration. More-
over, the model also proved useful in the design of a $\varepsilon$-constraint scalarization
approach that has very good anytime performance. In particular, we used the
model to set the constraint values for the scalarization problem to be solved
at each iteration. This approach guided by our model, showed anytime perfor-
mance that is very close to the anytime performance of a technique that finds
a solution that maximizes the hypervolume contribution at each iteration.

7.1.2 Empirical Models

One disadvantage of the proposed theoretical models is that they cannot model
the anytime performance in terms of CPU time, which we wished to consider
for the ASP in this thesis. As a result, in Chapter 4, we proposed three frame-
works for the development of empirical models that, in order to predict the
anytime performance of MOO algorithms on previously unseen instances, take
into account the anytime performance gathered from runs of those algorithms
on known problem instances.

The first framework, which builds an anytime performance profile of an
algorithm for the previously unseen problem instance from the anytime data
gathered from runs on known instances, can easily be applied to any algo-
rithm and should generally be easy to implement. However, it cannot be used
to predict the anytime performance for CPU times for which anytime data
was not gathered from actual runs on known problem instances. Moreover, it
requires that known problem instances share similarities, in terms of anytime
performance and problem instance features, to unseen problem instances. We
presented an experimental study to analyze the quality of this framework by
implementing an empirical model to predict the anytime behavior of three
MOO algorithms for MOBKP problem instances with 2, 3, and 5 objectives.
The results showed that the model could predict the anytime performance in
most cases. However, for one of the algorithms, the quality of the prediction
was often not very good on instances with 3 and 5 objectives. We believe this
was likely due to fact that we had a small number of training instances and
instance features.

The second framework considers fitting a (non)-linear model for each
known anytime performance profile in order to predict anytime behavior for
a previously unseen problem instance. As such, empirical models taking into
account this framework should be able to predict, to a certain degree, the any-
time performance for instances that are different than the ones we have for
training, and for CPU-times for which no anytime data is available. However,
it requires that a (non)-linear model can be fitted to the known anytime data,
which might not be trivial. In particular, we performed some preliminary ex-
periments, in which we were able to sometimes fit a non-linear growth model
to the anytime traces of the PLS and BHV-DP algorithms. However, we found
instances for which the same model was clearly not adequate.

The third framework is based on the idea of using a theoretical model that
consider time in terms of the number of iterations, such as the theoretical
models proposed in Chapter 3, and transforming it to a model that considers
anytime performance in terms of CPU time by using empirically collected
anytime data of how long each iteration takes. This framework may also allow
to predict approximation quality for CPU time values for which there is no
empirical data, contrary to the first framework. Moreover, it does not require
that the anytime performance can be modeled by (non)-linear growth model.
However, it requires that a theoretical model is known for the algorithm, which
is admittedly not very common.

At this point, it is worth noting that although our primary interest for the
development of these theoretical and empirical models was in regards to the
ASP, they also have other applications. For example, these models can be used
for the problem of automatically configuring the parameters of an algorithm,
to monitor and compare the performance of algorithms, and to decide when
to stop or restart an algorithm. Moreover, although we studied the empirical
models in the context of MOO, they are applicable to predict the anytime
performance single-objective optimization algorithms as well.

7.1.3 Offline Algorithm Selection

In Chapter 5, we presented an offline algorithm selection framework for select-
ing which anytime MOO algorithm to execute for a previously unseen instance.
An important aspect in the formulated ASP is that we consider the anytime
preferences of a DM with respect to what the anytime conditions for stopping
the algorithm were, in terms of execution time and archive quality. To this
end, we presented a measure of anytime performance that takes into account a
utility function describing the utility of execution time and archive quality to the DM. Moreover, we assumed that these conditions were only known when giving an instance to the selection methodology, and not before; i.e., they were not known when training the selection methodology. With this in mind, we highlighted that traditional classification and regression approaches were not particularly suited for this selection problem.

As a result, we proposed an offline selection methodology that takes into account the models of anytime performance such as the ones presented in Chapters 3 and 4. In particular, it uses models of anytime performance to predict the anytime performance profile of each algorithm on a previously unseen instance, and then applies the anytime performance measure with the utility function defined by the DM to the predicted anytime performance profile, in order to select the best algorithm.

We carried out an experimental study for selecting between two and three algorithms to the MOBKP, using the first empirical model to predict anytime performance, and taking into account two distinct utility functions. The results showed that our algorithm selection methodology could often select the best algorithm, and was better than always selecting the same algorithm for nearly every scenario. One aspect that is particularly relevant to highlight is that our methodology could often select the best algorithm even in scenarios where the quality of the prediction of anytime performance given by the empirical model was not the ideal, as long as the general tendency of anytime behavior was captured. However, we did see a decrease in selection accuracy in such cases. This shows that the quality of selection is closely related to the quality of the model, and we expect that improving the quality of the empirical model will result in an improved quality for the selection.

### 7.1.4 Online Algorithm Selection

In Chapter 6, we considered the ASP in an online perspective, that is to select and change algorithms while solving a problem instance. In particular, we considered selecting between BB strategies taking into account the anytime performance of the currently selected strategy and previously gathered empirical knowledge about each strategy.

To this end, we started by developing and analyzing several BB strategies. In particular, we presented the IBB framework, that takes into account the quality of the upper bound set of each node, in terms of quality indicator such as the hypervolume and $\varepsilon$-indicator. Then, we performed an experimental study to compare the anytime performance of different IBB strategies, and traditional BB strategies, on the MOBKP. Experiments revealed that the IBB approaches
were often much better than traditional *BB* approaches when no heuristic for branching is available. However, when a good heuristic for branching is available, we saw that the traditional *DFS* strategy was quite good. We also noted that, the best strategy often varied with time, and that depending on the number of objectives, the best quality indicator to guide the *IBB* approaches also changed.

With this information, we devised a simple online selection methodology that could change between *IBB* strategies. This online selection methodology proved to be quite effective, and was very often the best approach for a random branching order. However, we identified several scenarios where we expect that anytime performance can still be improved by considering a more complex selection strategy. In particular, we only considered changing between two strategies that were manually pre-selected before execution from the empirical results we had collected. However, there were several cases in which another approach was sometimes better. In addition, we only consider selecting between *IBB* strategies. However, when a good branching order was available the traditional *DFS* strategy was often better than *IBB* strategies. Therefore, if we also considered traditional strategies in specific scenarios we could improve the anytime performance of our online methodology. These situations suggest that a more automatic online methodology, that takes into account instances features and selects between all known strategies based on those features, could achieve better anytime performance.

## 7.2 Future Work

Throughout this thesis, we highlighted several opportunities for future work with respect to each aspect that was studied, which we summarize in the following sections. We leave out of this summary, future work related to the study of the algorithms, models, and selection methodologies on different problems and instances, since it would obviously be interesting to analyze them on different problems, especially on real-world problems. Moreover, we also leave out future work related to the comparison with other approaches, which would also be relevant. Instead, we focus on discussing aspects for the algorithms, models, and methodologies that we believe could be improved in the future, or even novel approaches based on the ideas discussed in this thesis.

### 7.2.1 Theoretical Models

A shortcoming of our theoretical model, and consequently of the proposed *GEPS* approach, is that it currently only works for *MOO* problems with 2 ob-
jectives. Therefore, given the positive results we obtained so far, an important
direction for future work would be to extend the theoretical model for more
dimensions. We consider that there are two main challenges for this. The first
is that the approximation of the non-dominated set can no longer be defined by
a set of linear segments. We believe that for 3 objectives, a representation given
by a set of polygons is feasible, albeit harder to maintain. However, we have
not yet thought about extending it for more dimensions. Another possibility,
even for 2 objectives, would be to consider curved surfaces for approximating
the surface. These may be harder to work with initially, but may more gen-
erally extend for more objectives. The second challenge is related to keeping
the set of unexplored regions up to date, since finding a point in a region can
potentially affect regions other than its own. This makes it harder to define an
analytical model, and makes the algorithmic model less efficient as it can no
longer fully cache the best values for each region.

Another important aspect for our theoretical model that deserves more re-
search is how to approximate the non-dominated set. In this work, we only con-
sidered that the non-dominated set could be well approximated by a quadrant
of a superellipse, which was in turn approximated by a set of linear segments.
This worked quite well for the knapsack problems considered. However, it
obviously does not work for every problem. One possibility would be to con-
sider a subset of supported solutions given by a weighted sum scalarization,
such as the DWS, to derive the linear segments that make up the piecewise
approximation. This has an intrinsic computational cost depending on how
difficult or easy it is to solve such scalarized problems. Moreover, depending
on the problem, the set of supported solutions found may not give a good ap-
proximation. Other possibilities, could, for example, rely on theoretical results
on the shape of the non-dominated set, or on using empirically data to estimate
the piecewise linear function from problem instance features.

7.2.2 Empirical Models

In the implementation of the empirical model following the first framework, we
considered a rather simple selection strategy based on the *k*-nearest neighbor
algorithm that selects instances that have similar instance features compared
to the previously unseen problem instance for which we want to predict any-
time performance, since we expect that this will mean that they will have
similar anytime performance compared to the previous unseen instance. This
selection strategy showed very positive results for some scenarios. However, a
natural direction for future research is to consider the use of different selection
strategies, or to further study the parameterization of the current strategy. For
example, we considered using a fixed value of *k* anytime traces during the selection. However, this can lead to selecting anytime traces from instances that are quite far from the instance for which we want to predict anytime performance if there is only a small number of similar instances. Instead, it would be interesting to consider dynamically setting the value of *k* depending on the instance for which we are attempting to predict performance. Alternatively, we could explore assigning different weights for the anytime traces depending on the distance, which would require incorporating such weights in the construction of the anytime performance profile.

Another aspect that deserves further investigation is the metric used to tune and evaluate the model. In particular, the measure of anytime performance that we considered cannot properly capture the tendency of anytime behavior, since, to put it simply, it only captures the area under an anytime trace and as such, two very distinct anytime traces may have the same measure. As such, a measure that could capture the difference in trend between the predicted and real anytime performance profile could lead to a better tuning and numerical evaluation of the model.

Lastly, another direction for future work is to implement empirical models following the second and third frameworks proposed. We did consider a preliminary model following the second framework that showed some promising results in preliminary experiments, but which had some issues. Nonetheless, we believe that if properly investigated it can lead to particularly accurate predictions.

### 7.2.3 Offline Algorithm Selection

The proposed offline algorithm selection methodology depends heavily on the models used to predict the anytime performance of each algorithm. Still, in this thesis we only investigated its performance for a particular case of a single empirical model. As such, the first aspect that we consider requires further work is the study of how the algorithm selection methodology relates to the chosen model. In particular, it would be interesting to study whether a theoretical relation between the quality of the model and the quality of the selection can be derived. Moreover, it would be interesting to study how changes to the model impact the quality of the selection in practice.

Another aspect that was not investigated in this thesis, but that is relevant for any algorithm selection methodology, is how long does algorithm selection take, and how does this impact the accuracy of the selection. In particular, it would be relevant to analyze the computational effort needed to perform algorithm selection, and to see how considering the selection time in the anytime
performance of the algorithm impacts the selection accuracy of our methodology, since time spent selecting an algorithm is time that is not being spent executing the algorithm.

Lastly, another important direction for future work would be to consider
new selection methodologies that could be compared to our own. In particular,
despite the fact that we have identified potential issues with respect to the use
of more traditional classification and regression approaches considering the
dynamic anytime preferences of a DM, there may be more restricted scenarios
where such approaches are viable and worth exploring.

7.2.4 Online Algorithm Selection

With regards to the proposed IBB approach, one clear direction for future
research is to study the impact of different lower and upper bound sets on the
performance of our approach, compared to more traditional BB approaches.
Moreover, it would also be relevant to study the use and impact of other quality
indicators.

With regards to the proposed online selection methodology, one clear short-
coming is that it currently depends on manually setting two strategies between
which we can swap. Moreover, changing between strategies depends only on
the anytime performance of the initial strategy, but not on the expected per-
formance of the next strategy. As such, two important aspects to investigate
further are the use of more than two strategies in the online selection method-
ology, and the automated selection of which strategy to use at each stage
depending on its predicted anytime performance, similar to what we did for
the offline algorithm selection. Another issue, is that the current online selec-
tion methodology was only considered for changing between BB approaches
that use different selection strategies. Therefore, it would relevant to consider
changing between algorithms other than BB variants. One difficulty that we
anticipate is that the change between distinct algorithms may not be ideal,
in the sense that some information collected by one algorithm may not be
leveraged by the other, and some calculations may need to be computed from
scratch.

Lastly, another direction for future work is to incorporate the anytime
preferences of a DM into the online selection methodology as we did with the
offline algorithm selection methodology, such that strategies can be selected
with respect to those preferences.
# Acronyms

**AEPS** Adaptive $\epsilon$-constraint 18

**ASP** Algorithm Selection Problem 2, 9, 28, 30, 127, 163–166

**BB** Branch-and-Bound 18–20, 127, 128, 131–133, 136, 139, 145–147, 160, 161, 166, 167, 170

**BeDFS** Best Depth First Search 20, 128–134, 136, 139, 140, 142, 143, 145–148, 151, 154, 157, 160, 161

**BeFS** Best First Search 20, 128, 130–134, 136, 137, 139, 140, 142, 143, 145–148, 151, 154, 155, 157, 160, 161

**BFS** Breadth First Search 20, 128, 132–134, 145, 160

**BHV-DP** Bazgan-Hugot-Vanderpooten Dynamic Programming 23, 62, 68, 69, 76–78, 80, 85, 87, 89, 94, 96, 104, 112, 113, 115–123, 165

**CCUBKP** Capacity Constrained UBKP 44–46, 48–50

**DFS** Depth First Search 20, 128, 132–134, 136, 137, 139, 140, 142, 145–147, 151, 152, 154, 155, 157, 160, 161, 167

**DM** Decision Maker 1–3, 5, 25, 28, 107, 108, 110, 125, 154, 160, 161, 163, 165, 166, 170

**DP** Dynamic Programming 22, 23, 44

**DWS** Dichotomic Weighted Sum 16, 24, 168

**FPSV-DP** Figueira-Paquete-Simões-Vanderpooten Dynamic Programming 24

**GEPS** Guided $\epsilon$-constraint 49, 50, 55, 62, 68, 69, 98, 104, 112–116, 167

**GNLS** Generalized Non-Linear Least Squares 105
**IBB** Indicator-based Branch-and-Bound 127, 128, 130–134, 136, 137, 139, 140, 142, 145–148, 151, 157, 160, 161, 166, 167, 170

**LOESS** Locally Estimated Scatterplot Smoothing 70

**LOOCV** Leave-One-Out Cross-Validation 67, 70, 76, 82, 85, 91, 95, 98

**MAE** Mean Absolute Error 67, 68, 70, 71, 76, 82, 85, 91, 95, 98

**MOBKP** Multi-Objective Binary Knapsack Problem 7, 15–18, 21–24, 29, 50, 57, 58, 62, 63, 65, 68, 104, 108, 111, 124, 127, 130, 131, 133, 145, 160, 161, 164, 166

**MOCO** Multi-Objective Combinatorial Optimization 9, 10, 15, 16

**MOO** Multi-Objective Optimization 1–5, 7–10, 12, 16, 20, 25, 26, 28–31, 33, 43, 107, 128, 163–165, 167

**PLS** Pareto Local Search 24, 25, 62, 68, 69, 72–74, 76–78, 80, 87, 104, 112–119, 121, 122, 165

**RMSE** Root-Mean-Square Error 67

**UBKP** Unconstrained Binary Knapsack Problem 43, 44, 46, 47, 49, 50
Notation

$\mathcal{X}$ Feasible solutions set

$\mathcal{X}_E$ Efficient set

$\mathcal{X}_S$ Supported solutions set

$\mathcal{X}_{ES}$ Extreme supported solutions set

$\mathcal{Y}$ Objective vectors set

$\mathcal{Y}_N$ Non-dominated set

$\mathcal{Y}_S$ Supported objective vectors set

$\mathcal{Y}_{ES}$ Extreme supported objective vectors set

$y^1 \ge y^2$ Point $y^1$ weakly dominates $y^2$

$y^1 > y^2$ Point $y^1$ dominates $y^2$

$y^1 > y^2$ Point $y^1$ strictly dominates $y^2$

$y^1 \ge_{lex} y^2$ Point $y^1$ is lexicographically greater than or equal to $y^2$

$y^1 >_{lex} y^2$ Point $y^1$ is lexicographically greater than $y^2$

$Y^1 \ge Y^2$ Set $Y^1$ weakly dominates $Y^2$

$Y^1 > Y^2$ Set $Y^1$ dominates $Y^2$

$Y^1 > Y^2$ Set $Y^1$ strictly dominates $Y^2$

$I_H$ Hypervolume indicator

$I_\epsilon$ $\epsilon$-indicator

$\mathbb{R}$ The set of real numbers

$\mathbb{Z}$ The set of integers
<figure><img src="image_106.png" /></figure>
List of References

[1] Y. P. Aneja and K. P. K. Nair. "Bicriteria Transportation Problem". In: *Management Science* 25.1 (1979), pp. 73–78. doi: 10.1287/mnsc.25.1.73 (cit. on pp. 16, 17).

[2] A. Arbelaez, Y. Hamadi, and M. Sebag. "Online Heuristic Selection in Constraint Programming". In: *International Symposium on Combinatorial Search*. 2009 (cit. on p. 29).

[3] C. Bazgan, H. Hugot, and D. Vanderpooten. "Solving Efficiently the 0-1 Multi-Objective Knapsack Problem". In: *Computers & Operations Research* 36.1 (2009), pp. 260–279. doi: 10.1016/j.cor.2007.09.009 (cit. on pp. 21, 23, 64, 68).

[4] *benchmark*. Version v1.6.0. Google (cit. on p. 42).

[5] F. Bökler. "Output-Sensitive Complexity of Multiobjective Combinatorial Optimization with an Application to the Multiobjective Shortest Path Problem". PhD thesis. Technischen Universität Dortmund, 2018 (cit. on p. 17).

[6] A. Cerqueus, X. Gandibleux, A. Przybylski, and F. Saubion. "On Branching Heuristics for the Bi-Objective 0/1 Unidimensional Knapsack Problem". In: *Journal of Heuristics* 23.5 (2017), pp. 285–319. doi: 10.1007/s10732-017-9346-9 (cit. on p. 21).

[7] M. Chiarandini. "Stochastic Local Search Methods for Highly Constrained Combinatorial Optimisation Problems". PhD thesis. Darmstadt: Technische Universität, 2005 (cit. on p. 27).

[8] W. S. Cleveland, E. Grosse, and W. M. Shyu. "Local Regression Models". In: *Statistical Models in S*. Routledge, 1992 (cit. on p. 70).

[9] G. B. Dantzig. "Discrete-Variable Extremum Problems". In: *Operations Research* 5.2 (1957), pp. 266–288. doi: 10.1287/opre.5.2.266 (cit. on pp. 21, 23).
[10] F. Daolio, A. Liefooghe, S. Verel, H. Aguirre, and K. Tanaka. "Problem Features versus Algorithm Performance on Rugged Multiobjective Combinatorial Fitness Landscapes". In: *Evolutionary Computation* 25.4 (2017), pp. 555-585. DOI: 10.1162/evco_a_00193 (cit. on p. 28).

[11] T. Dean and M. Boddy. "An Analysis of Time-Dependent Planning". In: *Proceedings of the Seventh AAAI National Conference on Artificial Intelligence*. AAAI'88. AAAI Press, 1988, pp. 49-54 (cit. on pp. 2, 25).

[12] C. Delort and O. Spanjaard. "Using Bound Sets in Multiobjective Optimization: Application to the Biobjective Binary Knapsack Problem". In: *Experimental Algorithms*. SEA 2010. Vol. 6049. Lecture Notes in Computer Science. Springer, 2010, pp. 253-265. DOI: 10.1007/978-3-642-13193-6_22 (cit. on p. 23).

[13] D. M. Dias, A. D. Jesus, and L. Paquete. "A Software Library for Archiving Nondominated Points". In: *Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion*. GECCO 2021. Association for Computing Machinery, 2021, pp. 53-54. DOI: 10.1145/3449726.3462737 (cit. on p. 7).

[14] D. M. Dias, A. D. Jesus, and L. Paquete. *nondLib*. Version v0.2.0. 2021. DOI: 10.5281/zenodo.4733027 (cit. on p. 7).

[15] M. Ehrgott. "Hard to Say It's Easy — Four Reasons Why Combinatorial Multiobjective Programmes Are Hard". In: *Research and Practice in Multiple Criteria Decision Making*. MCDM. Vol. 487. Lecture Notes in Economics and Mathematical Systems. Springer, 2000, pp. 69-80. DOI: 10.1007/978-3-642-57311-8_5 (cit. on p. 1).

[16] M. Ehrgott. *Multicriteria Optimization*. 2nd ed. Springer, 2005. DOI: 10.1007/3-540-27659-9 (cit. on pp. 10, 11, 16, 17, 49).

[17] M. Ehrgott and X. Gandibleux. "Bounds and Bound Sets for Biobjective Combinatorial Optimization Problems". In: *Multiple Criteria Decision Making in the New Millennium*. MCDM. Vol. 507. Lecture Notes in Economics and Mathematical Systems. Springer, 2001, pp. 241-253. DOI: 10.1007/978-3-642-56680-6_22 (cit. on p. 18).

[18] M. T. M. Emmerich and A. H. Deutz. "Test Problems Based on Lamé Superspheres". In: *Evolutionary Multi-Criterion Optimization*. EMO 2007. Vol. 4403. Lecture Notes in Computer Science. Springer, 2007, pp. 922-936. DOI: 10.1007/978-3-540-70928-2_68 (cit. on p. 33).
[19] J. R. Figueira, L. Paquete, M. Simões, and D. Vanderpooten. "Algorithmic Improvements on Dynamic Programming for the Bi-Objective {0,1} Knapsack Problem". In: *Computational Optimization and Applications* 56.1 (2013), pp. 97-111. DOI: 10.1007/s10589-013-9551-x (cit. on pp. 16, 23, 24).

[20] G. Fitzmaurice, M. Davidian, G. Verbeke, and G. Molenberghs, eds. *Longitudinal Data Analysis*. CRC Press, 2008 (cit. on p. 60).

[21] M. Gagliolo, C. Legrand, and M. Birattari. "Mixed-Effects Modeling of Optimisation Algorithm Performance". In: *Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics*. SLS 2009. Vol. 5752. Lecture Notes in Computer Science. Springer, 2009, pp. 150-154. DOI: 10.1007/978-3-642-03751-1_17 (cit. on pp. 60, 61).

[22] M. Gagliolo and J. Schmidhuber. "Learning Dynamic Algorithm Portfolios". In: *Annals of Mathematics and Artificial Intelligence* 47.3 (2006), pp. 295-328. DOI: 10.1007/s10472-006-9036-z (cit. on p. 29).

[23] M. Gagliolo, V. Zhumatiy, and J. Schmidhuber. "Adaptive Online Time Allocation to Search Algorithms". In: *Machine Learning: ECML 2004*. ECML 2004. Vol. 3201. Lecture Notes in Computer Science. Springer, 2004, pp. 134-143. DOI: 10.1007/978-3-540-30115-8_15 (cit. on p. 29).

[24] C. E. Galarza, L. M. Castro, F. Louzada, and V. H. Lachos. "Quantile Regression for Nonlinear Mixed Effects Models: A Likelihood Based Perspective". In: *Statistical Papers* 61.3 (2020), pp. 1281-1307. DOI: 10.1007/s00362-018-0988-y (cit. on p. 61).

[25] V. Grunert da Fonseca, C. M. Fonseca, and A. O. Hall. "Inferential Performance Assessment of Stochastic Optimisers and the Attainment Function". In: *Evolutionary Multi-Criterion Optimization*. EMO 2001. Vol. 1993. Lecture Notes in Computer Science. Springer, 2001, pp. 213-225. DOI: 10.1007/3-540-44719-9_15 (cit. on p. 27).

[26] A. P. Guerreiro and C. M. Fonseca. "Computing and Updating Hypervolume Contributions in Up to Four Dimensions". In: *IEEE Transactions on Evolutionary Computation* 22.3 (2018), pp. 449-463. DOI: 10.1109/TEVC.2017.2729550 (cit. on p. 130).

[27] A. P. Guerreiro, C. M. Fonseca, and L. Paquete. "The Hypervolume Indicator: Computational Problems and Algorithms". In: *ACM Computing Surveys* 54.6 (2021), 119:1-119:42. DOI: 10.1145/3453474 (cit. on p. 129).
[28] E. A. Hansen and S. Zilberstein. "Monitoring and Control of Anytime Algorithms: A Dynamic Programming Approach". In: *Artificial Intelligence* 126.1 (2001), pp. 139–157. doi: 10.1016/S0004-3702(00)00068-0 (cit. on p. 29).

[29] H. H. Hoos and T. Stützle. *Stochastic Local Search: Foundations & Applications*. Morgan Kaufmann Publishers Inc., 2005 (cit. on pp. 27, 28).

[30] A. D. Jesus. anytime. Version v0.0.2. Zenodo, 2022. doi: 10.5281/zenodo.6856120 (cit. on p. 8).

[31] A. D. Jesus. apm. Version v0.1.1. Zenodo, 2022. doi: 10.5281/zenodo.6857541 (cit. on pp. 8, 42).

[32] A. D. Jesus. Data, Scripts, and Results for: Algorithm Selection for Multi-Objective Optimization. Zenodo, 2022. doi: 10.5281/zenodo.6858045 (cit. on pp. 8, 43, 68, 69, 112, 113, 132, 147).

[33] A. D. Jesus. mobkp. Version v0.1.1. Zenodo, 2022. doi: 10.5281/zenodo.6857821 (cit. on pp. 7, 16, 21, 68, 112, 132, 147).

[34] A. D. Jesus. moco_abm. Version v0.2.0. Zenodo, 2019. doi: 10.5281/zenodo.3548869 (cit. on p. 7).

[35] A. D. Jesus. moutils. Version v0.1.0. Zenodo, 2022. doi: 10.5281/zenodo.6855879 (cit. on p. 7).

[36] A. D. Jesus, A. Liefooghe, B. Derbel, and L. Paquete. "Algorithm Selection of Anytime Algorithms". In: *Proceedings of the 2020 Genetic and Evolutionary Computation Conference*. GECCO 2020. Association for Computing Machinery, 2020, pp. 850–858. doi: 10.1145/3377930.3390185 (cit. on pp. 6, 64, 109).

[37] A. D. Jesus, L. Paquete, B. Derbel, and A. Liefooghe. "On the Design and Anytime Performance of Indicator-based Branch and Bound for Multi-objective Combinatorial Optimization". In: *Proceedings of the 2021 Genetic and Evolutionary Computation Conference*. GECCO 2021. Association for Computing Machinery, 2021, pp. 234–242. doi: 10.1145/3449639.3459360 (cit. on pp. 6, 127).

[38] A. D. Jesus, L. Paquete, and A. Liefooghe. "A Model of Anytime Algorithm Performance for Bi-Objective Optimization". In: *Journal of Global Optimization* 79 (2020), pp. 329–350. doi: 10.1007/s10898-020-00909-9 (cit. on pp. 6, 31).
[39] A. D. Jesus, L. Paquete, and A. Liefooghe. "A Model of Anytime Algorithm Performance for Biobjective Optimization Problems". In: *Proceedings LeGO - 14th International Global Optimization Workshop*. LeGO 2018. Vol. 2070. AIP Conference Proceedings. AIP, 2019, p. 020049. DOI: 10.1063/1.5090016 (cit. on pp. 6, 31).

[40] A. D. Jesus, L. Paquete, A. Liefooghe, and B. Derbel. "Techniques to Analyze the Anytime Behavior of Algorithms for Multi-Objective Optimization". 31st European Conference on Operational Research (EURO 2021). 2021 (cit. on p. 7).

[41] P. Kerschke, H. H. Hoos, F. Neumann, and H. Trautmann. "Automated Algorithm Selection: Survey and Perspectives". In: *Evolutionary Computation* 27.1 (2019), pp. 3–45. DOI: 10.1162/evco_a_00242 (cit. on pp. 2, 28).

[42] K. Klamroth and M. M. Wiecek. "Dynamic Programming Approaches to the Multiple Criteria Knapsack Problem". In: *Naval Research Logistics (NRL)* 47.1 (2000), pp. 57–76. DOI: 10.1002/(SICI)1520-6750(200002)47:1<57::AID-NAV4>3.0.CO;2-4 (cit. on p. 23).

[43] J. Knowles and D. Corne. "On Metrics for Comparing Nondominated Sets". In: *Proceedings of the 2002 Congress on Evolutionary Computation*. CEC 2002. IEEE, 2002, pp. 711–716. DOI: 10.1109/CEC.2002.1007013 (cit. on pp. 11, 12).

[44] L. Kotthoff. "Algorithm Selection for Combinatorial Search Problems: A Survey". In: *Data Mining and Constraint Programming*. Vol. 10101. Lecture Notes in Computer Science. Springer, 2016, pp. 149–190. DOI: 10.1007/978-3-319-50137-6_7 (cit. on pp. 2, 28, 29).

[45] M. Laumanns, L. Thiele, and E. Zitzler. "An Efficient, Adaptive Parameter Variation Scheme for Metaheuristics Based on the Epsilon-Constraint Method". In: *European Journal of Operational Research* 169.3 (2006), pp. 932–942. DOI: 10.1016/j.ejor.2004.08.029 (cit. on p. 18).

[46] K. Leyton-Brown, E. Nudelman, G. Andrew, J. McFadden, and Y. Shoham. "A Portfolio Approach to Algorithm Selection". In: *Proceedings of the 18th International Joint Conference on Artificial Intelligence*. IJCAI '03. Morgan Kaufmann Publishers Inc., 2003, pp. 1542–1543 (cit. on p. 28).

[47] A. Liefooghe, F. Daolio, S. Verel, B. Derbel, H. Aguirre, and K. Tanaka. "Landscape-Aware Performance Prediction for Evolutionary Multiobjective Optimization". In: *IEEE Transactions on Evolutionary Computation* 24.6 (2020), pp. 1063–1077. DOI: 10.1109/TEVC.2019.2940828 (cit. on p. 28).
[48] A. Liefooghe, L. Paquete, M. Simões, and J. R. Figueira. "Connectedness and Local Search for Bicriteria Knapsack Problems". In: *Evolutionary Computation in Combinatorial Optimization*. EvoCOP 2011. Vol. 6622. Lecture Notes in Computer Science. Springer, 2011, pp. 48–59. DOI: 10.1007/978-3-642-20364-0_5 (cit. on pp. 24, 25).

[49] A. Liefooghe, S. Verel, B. Lacroix, A.-C. Zăvoianu, and J. McCall. "Landscape Features and Automated Algorithm Selection for Multi-Objective Interpolated Continuous Optimisation Problems". In: *Proceedings of the 2021 Genetic and Evolutionary Computation Conference*. GECCO 2021. Association for Computing Machinery, 2021, pp. 421–429. DOI: 10.1145/3449639.3459353 (cit. on p. 28).

[50] M. López-Ibáñez, L. Paquete, and T. Stützle. "Exploratory Analysis of Stochastic Local Search Algorithms in Biobjective Optimization". In: *Experimental Methods for the Analysis of Optimization Algorithms*. Springer, 2010, pp. 209–222. DOI: 10.1007/978-3-642-02538-9_9 (cit. on p. 28).

[51] M. López-Ibáñez and T. Stützle. "Automatically Improving the Anytime Behaviour of Optimisation Algorithms". In: *European Journal of Operational Research* 235.3 (2014), pp. 569–582. DOI: 10.1016/j.ejor.2013.10.043 (cit. on pp. 64, 109).

[52] U.-E. Lukata and J. Teghem. "Solving Multi-Objective Knapsack Problem by a Branch-and-Bound Procedure". In: *Multicriteria Analysis*. MCDM. Springer, 1997, pp. 269–278. DOI: 10.1007/978-3-642-60667-0_26 (cit. on pp. 19, 20, 22).

[53] A. Makhorin. GLPK. Version v5.0. 2020 (cit. on p. 49).

[54] S. Martello and P. Toth. "An Upper Bound for the Zero-One Knapsack Problem and a Branch and Bound Algorithm". In: *European Journal of Operational Research* 1.3 (1977), pp. 169–175. DOI: 10.1016/0377-2217(77)90024-8 (cit. on pp. 22, 24).

[55] O. Mersmann, B. Bischl, H. Trautmann, M. Preuss, C. Weihs, and G. Rudolph. "Exploratory Landscape Analysis". In: *Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation*. GECCO 2011. Association for Computing Machinery, 2011, pp. 829–836. DOI: 10.1145/2001576.2001690 (cit. on p. 28).

[56] O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, and F. Neumann. "A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem". In: *Annals of Mathematics and Artificial Intelligence* 69.2 (2013), pp. 151–182. DOI: 10.1007/s10472-013-9341-2 (cit. on p. 28).
[57] A. M. Molinaro, R. Simon, and R. M. Pfeiffer. "Prediction Error Estimation: A Comparison of Resampling Methods". In: *Bioinformatics* 21.15 (2005), pp. 3301-3307. doi: 10.1093/bioinformatics/bti499 (cit. on p. 67).

[58] G. L. Nemhauser and Z. Ullmann. "Discrete Dynamic Programming and Capital Allocation". In: *Management Science* 15.9 (1969), pp. 494-505. doi: 10.1287/mnsc.15.9.494 (cit. on pp. 23, 44).

[59] E. Nudelman, K. Leyton-Brown, H. H. Hoos, A. Devkar, and Y. Shoham. "Understanding Random SAT: Beyond the Clauses-to-Variables Ratio". In: *Principles and Practice of Constraint Programming - CP 2004*. CP 2004. Vol. 3258. Lecture Notes in Computer Science. Springer, 2004, pp. 438-452. doi: 10.1007/978-3-540-30201-8_33 (cit. on p. 28).

[60] L. Paquete, M. Chiarandini, and T. Stützle. "Pareto Local Optimum Sets in the Biobjective Traveling Salesman Problem: An Experimental Study". In: *Metaheuristics for Multiobjective Optimisation*. Vol. 535. Lecture Notes in Economics and Mathematical Systems. Springer, 2004, pp. 177-199. doi: 10.1007/978-3-642-17144-4_7 (cit. on p. 24).

[61] L. Paquete, B. Schulze, M. Stiglmayr, and A. C. Lourenço. "Computing Representations Using Hypervolume Scalarizations". In: *Computers & Operations Research* 137 (2022), p. 105349. doi: 10.1016/j.cor.2021.105349 (cit. on pp. 55, 163).

[62] M. Pilu and R. B. Fisher. "Equal-Distance Sampling of Superellipse Models". In: *Proceedings of the 1995 British Machine Vision Conference*. BMVC 1995. BMVA Press, 1995, pp. 257-266. doi: 10.5244/C.9.26 (cit. on p. 34).

[63] J. Pinheiro and D. Bates. *Mixed-Effects Models in S and S-PLUS*. Statistics and Computing. Springer, 2000. doi: 10.1007/b98882 (cit. on p. 60).

[64] S. Polyakovskiy, M. R. Bonyadi, M. Wagner, Z. Michalewicz, and F. Neumann. "A Comprehensive Benchmark Set and Heuristics for the Traveling Thief Problem". In: *Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation*. GECCO 2014. Association for Computing Machinery, 2014, pp. 477-484. doi: 10.1145/2576768.2598249 (cit. on p. 28).

[65] A. Przybylski and X. Gandibleux. "Multi-Objective Branch and Bound". In: *European Journal of Operational Research* 260.3 (2017), pp. 856-872. doi: 10.1016/j.ejor.2017.01.032 (cit. on pp. 18, 19).
[66] A. Przybylski, X. Gandibleux, and M. Ehrgott. "A Recursive Algorithm for Finding All Nondominated Extreme Points in the Outcome Set of a Multiobjective Integer Programme". In: *INFORMS Journal on Computing* 22.3 (2010), pp. 371–386. DOI: 10.1287/ijoc.1090.0342 (cit. on pp. 17, 24).

[67] J. R. Rice. "The Algorithm Selection Problem". In: *Advances in Computers* 15 (1976), pp. 65–118. DOI: 10.1016/S0065-2458(08)60520-3 (cit. on pp. 2, 28).

[68] S. J. Russell and S. Zilberstein. "Composing Real-time Systems". In: *Proceedings of the 12th International Joint Conference on Artificial Intelligence*. IJCAI '91. Morgan Kaufmann Publishers Inc., 1991, pp. 212–217 (cit. on p. 29).

[69] K. A. Smith-Miles. "Cross-Disciplinary Perspectives on Meta-Learning for Algorithm Selection". In: *ACM Computing Surveys (CSUR)* 41.1 (2008), p. 6. DOI: 10.1145/1456650.1456656 (cit. on p. 2).

[70] V. Srinivasan and G. L. Thompson. "Algorithms for Minimizing Total Cost, Bottleneck Time and Bottleneck Shipment in Transportation Problems". In: *Naval Research Logistics Quarterly* 23.4 (1976), pp. 567–595. DOI: 10.1002/nav.3800230402 (cit. on p. 17).

[71] J. Svegliato, K. H. Wray, and S. Zilberstein. "Meta-Level Control of Any-time Algorithms with Online Performance Prediction". In: *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*. IJCAI '18. 2018. DOI: 10.24963/ijcai.2018/208 (cit. on p. 29).

[72] S. Verel, A. Liefooghe, L. Jourdan, and C. Dhaenens. "Analyzing the Effect of Objective Correlation on the Efficient Set of MNK-Landscapes". In: *Learning and Intelligent Optimization*. LION 2011. Vol. 6683. Lecture Notes in Computer Science. Springer, 2011, pp. 116–130. DOI: 10.1007/978-3-642-25566-3_9 (cit. on p. 44).

[73] S. Verel, A. Liefooghe, L. Jourdan, and C. Dhaenens. "On the Structure of Multiobjective Combinatorial Search Space: MNK-landscapes with Cor-related Objectives". In: *European Journal of Operational Research* 227.2 (2013), pp. 331–342. DOI: 10.1016/j.ejor.2012.12.019 (cit. on p. 63).

[74] M. G. Vilas Boas, H. G. Santos, L. H. d. C. Merschmann, and G. V. Berghe. "Optimal Decision Trees for the Algorithm Selection Problem: Integer Programming Based Approaches". In: *International Transactions in Operational Research* (2019). DOI: 10.1111/itor.12724 (cit. on p. 28).
[75] M. Visée, J. Teghem, M. Pirlot, and E. Ulungu. "Two-Phases Method and Branch and Bound Procedures to Solve the Bi-Objective Knapsack Problem". In: *Journal of Global Optimization* 12.2 (1998), pp. 139–155. DOI: 10.1023/A:1008258310679 (cit. on pp. 19, 20).

[76] L. While, L. Bradstreet, and L. Barone. "A Fast Way of Calculating Exact Hypervolumes". In: *IEEE Transactions on Evolutionary Computation* 16.1 (2012), pp. 86–95. DOI: 10.1109/TEVC.2010.2077298 (cit. on p. 130).

[77] L. Xu, F. Hutter, H. H. Hoos, and K. Leyton-Brown. "SATzilla: Portfolio-based Algorithm Selection for SAT". In: *Journal of Artificial Intelligence Research* 32 (2008), pp. 565–606. DOI: 10.1613/jair.2490 (cit. on p. 28).

[78] S. Zilberstein. "Using Anytime Algorithms in Intelligent Systems". In: *AI Magazine* 17.3 (1996), pp. 73–83. DOI: 10.1609/aimag.v17i3.1232 (cit. on pp. 2, 25, 26, 28, 29).

[79] E. Zitzler. "Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications". PhD thesis. Swiss Federal Institute of Technology Zurich, 1999 (cit. on p. 13).

[80] E. Zitzler and L. Thiele. "Multiobjective Optimization Using Evolutionary Algorithms – A Comparative Case Study". In: *Parallel Problem Solving from Nature – PPSN*. PPSN 1998. Vol. 1498. Lecture Notes in Computer Science. Springer, 1998, pp. 292–301. DOI: 10.1007/BFb0056872 (cit. on pp. 3, 12).

[81] E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. Grunert da Fonseca. "Performance Assessment of Multiobjective Optimizers: An Analysis and Review". In: *IEEE Transactions on Evolutionary Computation* 7.2 (2003), pp. 117–132. DOI: 10.1109/TEVC.2003.810758 (cit. on pp. 11, 12, 14).
<figure><img src="image_107.png" /></figure>
# Appendix A

## Empirical Model Results
A.1 PLS — 2 objectives

<figure><img src="image_108.png" /><figcaption>Figure A.1: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_109.png" /><figcaption>Figure A.2: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_110.png" /><figcaption>Figure A.3: Results of anytime performance prediction on the testing data set.</figcaption></figure>
A.2 PLS – 3 objectives

<figure><img src="image_111.png" /><figcaption>Figure A.4: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_112.png" /><figcaption>Figure A.5: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_113.png" /><figcaption>Figure A.6: Results of anytime performance prediction on the testing data set.</figcaption></figure>
A.3 PLS — 5 objectives

<figure><img src="image_114.png" /><figcaption>Figure A.7: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_115.png" /><figcaption>Figure A.8: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_116.png" /><figcaption>Figure A.9: Results of anytime performance prediction on the testing data set.</figcaption></figure>
A.4 BHV-DP – 2 objectives

<figure><img src="image_117.png" /><figcaption>Figure A.10: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_118.png" /><figcaption>Figure A.11: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_119.png" /><figcaption>Figure A.12: Results of anytime performance prediction on the testing data set.</figcaption></figure>
A.5 BHV-DP — 3 objectives

<figure><img src="image_120.png" /><figcaption>Figure A.13: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_121.png" /><figcaption>Figure A.14: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_122.png" /><figcaption>Figure A.15: Results of anytime performance prediction on the testing data set.</figcaption></figure>
A.6 BHV-DP — 5 objectives

<figure><img src="image_123.png" /><figcaption>Figure A.16: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_124.png" /><figcaption>Figure A.17: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_125.png" /><figcaption>Figure A.18: Results of anytime performance prediction on the testing data set.</figcaption></figure>
A.7 GEPS – 2 objectives

<figure><img src="image_126.png" /><figcaption>Figure A.19: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_127.png" /><figcaption>Figure A.20: Results of anytime performance prediction on the testing data set.</figcaption></figure>
<figure><img src="image_128.png" /><figcaption>Figure A.21: Results of anytime performance prediction on the testing data set.</figcaption></figure>