Repository logo
 

Metareasoning about propagators for constraint satisfaction

Date

2011-05

Journal Title

Journal ISSN

Volume Title

Publisher

ORCID

Type

Degree Level

Masters

Abstract

Given the breadth of constraint satisfaction problems (CSPs) and the wide variety of CSP solvers, it is often very difficult to determine a priori which solving method is best suited to a problem. This work explores the use of machine learning to predict which solving method will be most effective for a given problem. We use four different problem sets to determine the CSP attributes that can be used to determine which solving method should be applied. After choosing an appropriate set of attributes, we determine how well j48 decision trees can predict which solving method to apply. Furthermore, we take a cost sensitive approach such that problem instances where there is a great difference in runtime between algorithms are emphasized. We also attempt to use information gained on one class of problems to inform decisions about a second class of problems. Finally, we show that the additional costs of deciding which method to apply are outweighed by the time savings compared to applying the same solving method to all problem instances.

Description

Keywords

performance prediction, algorithm selection, propagation, machine learning

Citation

Degree

Master of Science (M.Sc.)

Department

Computer Science

Program

Computer Science

Citation

Part Of

item.page.relation.ispartofseries

DOI

item.page.identifier.pmid

item.page.identifier.pmcid