Date of acceptance Grade Instructor Algorithm portfolios in constraint solving

Abstract

Although NP-hard problems are generally thought to be intractable in the worst case, in practice many instances can be solved efficiently by heuristic algorithms. Typically, different algorithms perform well on different instances and there is no single best algorithm. Indeed, while an algorithm might solve many instances in a few seconds, solving other instances of same size may instead take several weeks. One approach in such cases is to construct an algorithm portfolio that comprises multiple algorithms and attempts to select the best one for a given problem instance. In this report we present SATzilla, a generic process for constructing an algorithm portfolio that utilizes so called empirical hardness models to predict an algorithm's running time on given instance. Such models are constructed by first identifying a set of instance features and then using machine learning techniques to exploit correlations between features and algorithm performance. While the SATzilla approach originally targets boolean satisfiability, the same techniques have been successfully applied to various other constraint problems. Työn nimi — Arbetets titel — Title Oppiaine — Läroämne — Subject Työn laji — Arbetets art — Level Aika — Datum — Month and year Sivumäärä — Sidoantal — Number of pages Tiivistelmä — Referat — Abstract Avainsanat — Nyckelord — Keywords Säilytyspaikka — Förvaringsställe — Where deposited Muita tietoja — övriga uppgifter — Additional information

Topics

4 Figures and Tables

Download Full PDF Version (Non-Commercial Use)