- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Automated configuration of algorithms for solving hard...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Automated configuration of algorithms for solving hard computational problems Hutter, Frank
Abstract
The best-performing algorithms for many hard problems are highly parameterized. Selecting the best heuristics and tuning their parameters for optimal overall performance is often a difficult, tedious, and unsatisfying task. This thesis studies the automation of this important part of algorithm design: the configuration of discrete algorithm components and their continuous parameters to construct an algorithm with desirable empirical performance characteristics. Automated configuration procedures can facilitate algorithm development and be applied on the end user side to optimize performance for new instance types and optimization objectives. The use of such procedures separates high-level cognitive tasks carried out by humans from tedious low-level tasks that can be left to machines. We introduce two alternative algorithm configuration frameworks: iterated local search in parameter configuration space and sequential optimization based on response surface models. To the best of our knowledge, our local search approach is the first that goes beyond local optima. Our model-based search techniques significantly outperform existing techniques and extend them in ways crucial for general algorithm configuration: they can handle categorical parameters, optimization objectives defined across multiple instances, and tens of thousands of data points. We study how many runs to perform for evaluating a parameter configuration and how to set the cutoff time, after which algorithm runs are terminated unsuccessfully. We introduce data-driven approaches for making these choices adaptively, most notably the first general method for adaptively setting the cutoff time. Using our procedures—to the best of our knowledge still the only ones applicable to these complex configuration tasks—we configured state-of-the-art tree search and local search algorithms for SAT, as well as CPLEX, the most widely-used commercial optimization tool for solving mixed integer programs (MIP). In many cases, we achieved improvements of orders of magnitude over the algorithm default, thereby substantially improving the state of the art in solving a broad range of problems, including industrially relevant instances of SAT and MIP. Based on these results, we believe that automated algorithm configuration procedures, such as ours, will play an increasingly crucial role in the design of high-performance algorithms and will be widely used in academia and industry.
Item Metadata
Title |
Automated configuration of algorithms for solving hard computational problems
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2009
|
Description |
The best-performing algorithms for many hard problems are highly parameterized. Selecting
the best heuristics and tuning their parameters for optimal overall performance is often a
difficult, tedious, and unsatisfying task. This thesis studies the automation of this important part
of algorithm design: the configuration of discrete algorithm components and their continuous
parameters to construct an algorithm with desirable empirical performance characteristics.
Automated configuration procedures can facilitate algorithm development and be applied
on the end user side to optimize performance for new instance types and optimization objectives.
The use of such procedures separates high-level cognitive tasks carried out by humans
from tedious low-level tasks that can be left to machines.
We introduce two alternative algorithm configuration frameworks: iterated local search in
parameter configuration space and sequential optimization based on response surface models.
To the best of our knowledge, our local search approach is the first that goes beyond local
optima. Our model-based search techniques significantly outperform existing techniques and
extend them in ways crucial for general algorithm configuration: they can handle categorical
parameters, optimization objectives defined across multiple instances, and tens of thousands
of data points.
We study how many runs to perform for evaluating a parameter configuration and how to
set the cutoff time, after which algorithm runs are terminated unsuccessfully. We introduce
data-driven approaches for making these choices adaptively, most notably the first general
method for adaptively setting the cutoff time.
Using our procedures—to the best of our knowledge still the only ones applicable to
these complex configuration tasks—we configured state-of-the-art tree search and local search
algorithms for SAT, as well as CPLEX, the most widely-used commercial optimization tool for
solving mixed integer programs (MIP). In many cases, we achieved improvements of orders
of magnitude over the algorithm default, thereby substantially improving the state of the art in
solving a broad range of problems, including industrially relevant instances of SAT and MIP.
Based on these results, we believe that automated algorithm configuration procedures, such
as ours, will play an increasingly crucial role in the design of high-performance algorithms
and will be widely used in academia and industry.
|
Extent |
9522135 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-10-13
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0051652
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2009-11
|
Campus | |
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International