LeapsAndBounds: A Method for Approximately Optimal Algorithm Configuration
We consider the problem of configuring general-purpose solvers to run efficiently on problem instances drawn from an unknown distribution. The goal of the configurator is to find a configuration 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 LeapsAndBounds, 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 LeapsAndBounds is close to the optimal expected runtime, while our algorithm’s running time is near-optimal. Our results show that LeapsAndBounds is more efficient than the recent algorithm of Kleinberg et al. (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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
LeapsAndBounds: A Method for Approximately Optimal Algorithm Configuration
We consider the problem of configuring general-purpose solvers to run efficiently on problem instances drawn from an unknown distribution. The goal of the configurator is to find a configuration that runs fast on average…
Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration
Algorithm configuration methods optimize the performance of a parameterized heuristic algorithm on a given distribution of problem instances. Recent work introduced an algorithm configuration procedure ("Structured Procr…
Sub-Optimal Multi-Phase Path Planning: A Method for Solving Rubik's Revenge
Rubik's Revenge, a 4x4x4 variant of the Rubik's puzzles, remains to date as an unsolved puzzle. That is to say, we do not have a method or successful categorization to optimally solve every one of its approximately $7.40…
Rubik's CubeTime SeriesTime Series AnalysisImpatientCapsAndRuns: Approximately Optimal Algorithm Configuration from an Infinite Pool
Algorithm configuration procedures optimize parameters of a given algorithm to perform well over a distribution of inputs. Recent theoretical work focused on the case of selecting between a small number of alternatives. …
Genetic Algorithms For Parameter Optimization for Disparity Map Generation of Radiata Pine Branch Images
Traditional stereo matching algorithms like Semi-Global Block Matching (SGBM) with Weighted Least Squares (WLS) filtering offer speed advantages over neural networks for UAV applications, generating disparity maps in app…