Resumen de Portfolio approaches for problem solving
Sergio Núñez Covarrubias
In recent years the notion of portfolio has been revived from the Modern Portfolio Theory literature with the aim of improving the performance of modern solvers. This notion of portfolio applied to problem solving has shown to be very effective by exploiting the complementary strengths of different solvers. However, a deeper understanding of the limits and possibilities of portfolios is still missing. In this Thesis, we deal with the problem of automatically configuring sequential portfolios for solving combinatorial problems. It comprises, among others, three main challenges: how to select the solvers to be part in the portfolio; how to define the runtime allotted to each component solver; and how to decide the order in which the component solvers should be executed.
Most approaches to the study of portfolios are purely empirical. Thus, we propose a new theoretically-grounded method based on Mixed-Integer Programming named GOP. It automatically derives the optimal portfolio configuration (i.e., the set of component solvers and the time allotted to each one) for a specific metric and a given training set. Optimality is only guaranteed for the given training set. However, experimental results both with data from the International Planning Competition and the SAT Competition show that GOP significantly outperforms others under the same conditions. Indeed, MIPSat, the sequential SAT portfolio automatically configured with GOP, won the silver medal in the Open track of the SAT Competition 2013. In addition, MIPlan, the planning system which is able to automatically generate a portfolio configuration for a specific planning domain using GOP, won the learning track of the International Planning Competition 2014.
The training benchmark used to derive sequential portfolios affects the quality of the resulting portfolio and the time required to compute it. Hence, we analyze in this Thesis the impact of the composition and the size of the training benchmark in the portfolio configuration process. Specifically, we use GOP to perform a posteriori analysis with the goal of selecting the training instances which provide the most relevant information to the portfolio configuration technique. Empirical results suggest that the best training benchmark should be composed of a small number of instances that only a few solvers are able to solve.
This Thesis also addresses the problem related to the order of the component solvers in a sequential portfolio. In the literature, not much work has been devoted to a better understanding of the relationship between the order of the component solvers and the performance of the resulting portfolio over time. We propose to sort the component solvers in a sequential portfolio, such that the resulting ordered portfolio maximizes the probability of providing the largest performance at any point in time. We also introduce a greedy and optimal algorithms to solve this problem. Moreover, we show that the greedy approach efficiently obtains near-optimal performance over time. Also, it generalizes much better than an optimal approach which has been observed to suffer from overfitting.
In summary, this Thesis studies different issues related to the automated design of sequential portfolios. We design a new portfolio configuration method and address the problem of the order in which the sequential portfolios should be executed. Experimental results show that the resulting portfolios are highly competitive and often outperform other state-of-the-art approaches.
