Abstract

We consider the problem of configuring generalpurpose solvers to run efficiently on problem instances drawn from an unknown distribution. The goal of the configurator is to find a configuratio that runs fast on average on most instances, and do so with the least amount of total work. It can run a chosen solver on a random instance until the solver finishes or a timeout is reached. We propose L EAPS A ND B OUNDS, an algorithm that tests configurations on randomly selected problem instances for longer and longer time. We prove that the capped expected runtime of the configuration returned by L EAPS A ND B OUNDS is close to the optimal expected runtime, while our algorithm’s running time is near-optimal. Our results show that L EAPS A ND B OUNDS is more efficient than the recent algorithm of Kleinberg et (2017), which, to our knowledge, is the only other algorithm configuration method with non-trivial theoretical guarantees. Experimental results on configuring a public SAT solver on a new benchmark dataset also stand witness to the superiority of our method.