Algorithm Selection in Optimization and Application to Angry Birds

  • Shahaf S. Shperberg Ben-Gurion University
  • Solomon Eyal Shimony Ben-Gurion University
  • Avinoam Yehezkel Ben-Gurion University

Abstract

Consider the MaxScore algorithm selection problem: given some optimization problem instances, a set of algorithms that solve them, and a time limit, what is the optimal policy for selecting (algorithm, instance) runs so as to maximize the sum of solution qualities for all problem instances?

We analyze the computational complexity of restrictions of MaxScore (NP-hard), and provide a dynamic programming approximation algorithm. This algorithm, as well as new greedy algorithms, are evaluated empirically on data from agent runs on Angry Birds problem instances. Results show a significant improvement over a hyper-agent greedy scheme from related work.

Solomon Eyal Shimony

Avinoam Yehezkel

Published
2019-07-06