An Extensive Evaluation of Portfolio Approaches for Constraint Satisfaction Problems

Roberto Amadini (1, 2) , Maurizio Gabbrielli (1) , Jacopo Mauro (3)

1 FOCUS - Foundations of Component-based Ubiquitous Systems
2 DISI - Department of Computer Science and Engineering [Bologna]
3 UiO - University of Oslo

In the context of Constraint Programming, a portfolio approach exploits the complementary strengths of a portfolio of different constraint solvers. The goal is to predict and run the best solver(s) of the portfolio for solving a new, unseen problem. In this work we reproduce, simulate, and evaluate the performance of different portfolio approaches on extensive benchmarks of Constraint Satisfaction Problems. Empirical results clearly show the benefits of portfolio solvers in terms of both solved instances and solving time.

Mots clés: Algorithm Selection; Algorithm Portfolios; Constraint Programming; Constraint Satisfaction Problems

Domaines: Informatique [cs]

Roberto Amadini, Maurizio Gabbrielli, Jacopo Mauro. An Extensive Evaluation of Portfolio Approaches for Constraint Satisfaction Problems. International Journal of Interactive Multimedia and Artificial Intelligence, 2016. ⟨hal-01336684⟩