Automating meta-algorithmic analysis and design

Sophisticated empirical methods based upon automated experimental analysis techniques drive the development of high-performance solvers for an increasing range of problems from industry and academia. However, tools implementing these methods are often difficult to develop and to use. This thesis describes work towards addressing this issue. First, we develop a formal description of meta-algorithmic problems, and use it as the basis for a framework supporting the development and application of a broad class of automated algorithm analysis and design techniques. Second, we describe the High-performance Algorithm Laboratory (HAL), an extensible software implementation of this framework that provides developers and users of automated empirical techniques with support for distributed execution, remote monitoring, data management, and statistical analysis of results. We use HAL to construct a suite of interoperable tools that implement a variety of automated empirical techniques, and demonstrate our approach by conducting a sequence of increasingly complex analysis and design tasks on state-of-the-art solvers for Boolean satisfiability and mixed-integer programming problems.Science, Faculty ofComputer Science, Department ofGraduat