Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

1-2015

Abstract

The abundance of algorithms developed to solve different problems has given rise to an important research question: How do we choose the best algorithm for a given problem? Known as algorithm selection, this issue has been prevailing in many domains, as no single algorithm can perform best on all problem instances. Traditional algorithm selection and portfolio construction methods typically treat the problem as a classification or regression task. In this paper, we present a new approach that provides a more natural treatment of algorithm selection and portfolio construction as a ranking task. Accordingly, we develop a Ranking-Based Algorithm Selection (RAS) method, which employs a simple polynomial model to capture the ranking of different solvers for different problem instances. We devise an efficient iterative algorithm that can gracefully optimize the polynomial coefficients by minimizing a ranking loss function, which is derived from a sound probabilistic formulation of the ranking problem. Experiments on the SAT 2012 competition dataset show that our approach yields competitive performance to that of more sophisticated algorithm selection methods.

Keywords

algorithm selection, ranking, satisfiability problem

Discipline

Artificial Intelligence and Robotics | Theory and Algorithms

Publication

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas

First Page

1826

Last Page

1832

Publisher

AAAI Press

City or Country

Menlo Park, CA

Copyright Owner and License

LARC

Additional URL

http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9613

Download

Share

COinS