Conference Publication Details
Mandatory Fields
Yuri Malitsky, Deepak Mehta, Barry O’Sullivan
Proceedings of the Sixth Annual Symposium on Combinatorial Search, SoCS 2013
Evolving Instance Specific Algorithm Configuration
Optional Fields
Malte Helmert and Gabriele Roger
Combinatorial problems are ubiquitous in artficial intelligence and related areas. While there has been a signficant amount of research into the design and implementation of solvers for combinatorial problems, it is well-known that there is still no single solver that performs best across a broad set of problem types and domains. This has motivated the development of portfolios of solvers. A portfolio typically comprises either many different solvers, instances of the same solver tuned in different ways, or some combination of these. However, current approaches to portfolio design take a static view of the process. Specifically, the design of the portfolio is determined offline, and then deployed in some setting. In this paper we propose an approach to evolving the portfolio over time based on the problems instances that it encounters. We study several challenges raised by such a dynamic approach, such as how to re-tune the portfolio over time. Our empirical results demonstrate that our evolving portfolio approach signficantly out-performed the standard static approach in the case when the type of instances observed change over time
Grant Details