Publication: Portfolio approaches for problem solving
Loading...
Identifiers
Publication date
2016-07
Defense date
2016-07-22
Authors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
Durante los últimos anos el concepto portfolio ha sido recuperado de la Teoría Moderna del Portfolio con el objetivo de rrejorar el rendimiento de los solucionadores actuales. El conrepto de portfolio aplicado a la resolución de problemas ha demostrado ser muy efectivo aprovechando las virtudes complerrentarias de los diferentes solucionadores. Sin embargo, todavía no se han estudiado en profundidad sus limites y posibilidades. Esta Tesis trata el problema de la configuración automática de portfolios secuenciales para resolver problemas combinatorios. Esto comprende, entre otros, tres retos principales: cómo seleccionar los solucionadores que conformarán el portfolio; cómo definir el tiempo asignado a cada solucionador que forma parte del portfolio; y cómo decidir el orden en el cual los solucionadores debetian ser ejecutados.
La mayotia de aproximaciones que estudian ¡iortfolios son totalrrente empíricas. Por lo tanto, nosotros proponemos GOP, un nuevo método teónicamente fundamentado, basado en Programación Entera Mixta Este método obtiene de forma automática la configuración óptima del portfolio (es decir, el conjunto de solucionadores que componen el portfolio y el tiempo asignado a cada uno de ellos) para una métrica específica y un determinado conjunto de entrenamiento. La configuración obtenida sólo es óptima para el conjunto de entreruuniento. Sin embargo, experirrentos con datos de la Competición Internacional de Planificación y la Competición de SAT muestran que GOP supera de forma significativa al resto de aproximaciones bajo las mismas condiciones de experimentación. De hecho, MIPSAT, el portfolio secuencial que ha sido automáticamente configurado con GOP, ganó la rredalla de plata en la categoría open de la Competición de SAT del ano 2013. Además, MIPLAN, el sistema de planificación capaz de generar de forma automática una configuración de portfolio para un determinado dominio de planificación utilizando GOP, ganó la categotia de aprendizaje de la Competición Internacional de Planificación del ano 2014.
El conjunto de entrenamiento utilizado para obtener portfolios secuenciales afecta a la calidad del portfolio generado y al tiempo necesario para configurarlo. Por lo tanto, en esta To sis analizarnos el impacto de la composición y del tamano del conjunto de entrenamiento en el proreso de configuración del portfolio. Específicamente, nosotros utilizarnos GOP para realizar un análisis a posteriori con el objetivo de seleccionar los problemas de entrenamiento que proporcionan la información más relevante para la técnica de configuración de pol1tfolios. Los resultados de la experimentación realizada sugieren que el mejor conjunto de entrenamiento deberla estar compuesto por un pequeno número de problemas, los cuales sólo unos pocos solucionadores debetian ser capaces de resolver.
Esta Tesis también aborda el problema relacionado con el orden de los solucionadores en los portfolios secuenciales. En la literatura no aparecen trabajos que estudien la relación entre el orden de los solucionadores en el portfolio y su rendimcento a lo largo del tiempo. Nosotros proponemos ordenar los solucionadores en los portfolios secuenciales de forma que el portfolio ordenado resultante maximice la probabilidad de obtener el mejor rendimiento en cualquier instante de tiempo. Además, hemos presentado un algoritmo greedy y otro óptimo para resolver este problema. Nuestros resultados demuestran que la aproximación greedy obtiene de forma eficiente soluciones muy cercanas a la óptima. Además, esta aproximación generaliza rnejor que el algoritmo óptimo, el cual padece sobre-aprendizaje.
En resumen, esta Tosis estudia varios problemas relacionados con el diseno automático de portfolios secuenciales. Nosotros hemos disenado un nuevo método para configurar portfolios y hemos tratado el problema del orden en el que los solucionadores de los portfolios secuenciales deberían ser ejecutados. Los experimentos realizados muestran que 105 portfolios obtenidos son extraordinariamente competitivos y con mucha frecuencia superan al resto de aproximaciones.
In recent years the notion of portfolio has been revived from the Modern Portfolio Theory literature with the aim of improving the performance of moder 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 combinatoria! 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 componen! solver; and how to decide the order in which the component solvers should be executed. Most approaches to the study of portfolios are purely empírica!. Thus, we propose a new theoretically-grounded method based on Mixed-Integer Programming named GOP. It automatically derives the optimal portfolio configuration (i.e., th,e set of component solvers and the time allotted to each one) for a specific metric and a given trainin.g set. Optimality is only guaranteed for the given training set. However, experimental results both with data from the Intemational Planning Competition and the SAT Competition show that GOP significanlly 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 genera.te a portfolio configuration for a specific planning domain using GOP, won the leaming track ofthe Entemational 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 posterwri analysis with the goal of selecting the training instances which provide the most relevan! information to the portfolio configuration technique. Empírical 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 optima! algorithms to solve this problem. Moreover, we show that the greedy approach efficiently obtains near-optimal performance over time. Also, it general aes much better than an optima! 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.
In recent years the notion of portfolio has been revived from the Modern Portfolio Theory literature with the aim of improving the performance of moder 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 combinatoria! 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 componen! solver; and how to decide the order in which the component solvers should be executed. Most approaches to the study of portfolios are purely empírica!. Thus, we propose a new theoretically-grounded method based on Mixed-Integer Programming named GOP. It automatically derives the optimal portfolio configuration (i.e., th,e set of component solvers and the time allotted to each one) for a specific metric and a given trainin.g set. Optimality is only guaranteed for the given training set. However, experimental results both with data from the Intemational Planning Competition and the SAT Competition show that GOP significanlly 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 genera.te a portfolio configuration for a specific planning domain using GOP, won the leaming track ofthe Entemational 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 posterwri analysis with the goal of selecting the training instances which provide the most relevan! information to the portfolio configuration technique. Empírical 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 optima! algorithms to solve this problem. Moreover, we show that the greedy approach efficiently obtains near-optimal performance over time. Also, it general aes much better than an optima! 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.
Description
Keywords
Artificial intelligence, Mixed-Integer Programming, GOP, Modern Portfolio Theory