Automatic construction of optimal static sequential portfolios for AI planning and beyond

摘要

In recent years the notion of portfolio has been revived with the aim of improving the performance of modern solvers. For example, Fast Downward Stone Soup and SATzilla have shown an excellent performance at the International Planning and SAT Competitions respectively. However, a deeper understanding of the limits and possibilities of portfolios is still missing. Most approaches to the study of portfolios are purely empirical. Thus, we propose a theoretically-grounded method based on Mixed-Integer Programming named gop. It addresses, among others, three main issues: how to derive an upper bound on the solvers performance for a given set of problem solving tasks; how to analyze the utility of training instances when designing portfolios; and how to configure a high performance portfolio for a given training set which generalizes very well on unseen instances. Experimental results both with data from the International Planning Competitions 2008 and 2011 and the SAT Competition 2013 show that this approach 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.