Sampling strategies in automated algorithm configuration

Anastacio, M.I.A.

When confronted with complex real-world problems, the first step is often to express them mathematically to make them accessible to a multitude of tools for solving them. Among those representations, non-deterministic polynomial-time hard (NP-hard) problems are commonly considered unsolvable in polynomial time. They have two important characteristics: creating the correct solution from scratch is typically intractable, but verifying if a solution is correct does not require as much effort. Researchers gathered a variety of methods to solve increasingly complex problems. In particular, heuristic methods can often solve NP-hard problems, even large ones, through approximations and trial and error. They come with parameters that can be tailored to the problem instances at hand. Setting them correctly can make the difference between solving a problem in minutes or weeks. To optimise such algorithms by setting the values of their parameters is an optimisation problem known as...Show more When confronted with complex real-world problems, the first step is often to express them mathematically to make them accessible to a multitude of tools for solving them. Among those representations, non-deterministic polynomial-time hard (NP-hard) problems are commonly considered unsolvable in polynomial time. They have two important characteristics: creating the correct solution from scratch is typically intractable, but verifying if a solution is correct does not require as much effort. Researchers gathered a variety of methods to solve increasingly complex problems. In particular, heuristic methods can often solve NP-hard problems, even large ones, through approximations and trial and error. They come with parameters that can be tailored to the problem instances at hand. Setting them correctly can make the difference between solving a problem in minutes or weeks. To optimise such algorithms by setting the values of their parameters is an optimisation problem known as the automated algorithm configuration problem. Heuristic algorithms (referred to as configurators) are now applied to configure heuristic algorithms (referred to as solvers). The main topic of interest in the present thesis is the strategies applied by configurators to sample parameter values and problem instances in the context of running time reduction of solvers for NP-hard problems.
Show less

Leiden University Scholarly Publications

View statistics

Documents

In Collections

Sampling strategies in automated algorithm configuration