Algorithm Selection via Ranking

• Main Authors: Richard, Jayadi Oentaryo, Stephanus Daniel, Handoko, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2015
• Subjects: algorithm selection; ranking; satisfiability problem; Artificial Intelligence and Robotics; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/2906; https://ink.library.smu.edu.sg/context/sis_research/article/3906/viewcontent/AlgorithmSelectionviaRanking_2015_AAAI.pdf
• Institution: Singapore Management University

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.