Learning and parallelization boost constraint search
Item
-
Title
-
Learning and parallelization boost constraint search
-
Identifier
-
d_2009_2013:3c721ba4d303:11950
-
identifier
-
12575
-
Creator
-
Yun, Xi,
-
Contributor
-
Susan L. Epstein
-
Date
-
2013
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer science | Educational technology | Artificial intelligence | Algorithm Portfolio | Case-Based Reasoning | Constraint Search | Hybrid paradigm | Learning | Parallelization
-
Abstract
-
Constraint satisfaction problems are a powerful way to abstract and represent academic and real-world problems from both artificial intelligence and operations research. A constraint satisfaction problem is typically addressed by a sequential constraint solver running on a single processor. Rather than construct a new, parallel solver, this work develops convenient parallelization methods for pre-existing solvers, and thereby benefits from both state-of-the-art research and increasingly available computational resources.;This work proposes and evaluates several approaches that exploit scheduling and partitioning. It formulates parallel algorithm portfolio construction as an integer- programming problem, and solves the problem with algorithms that combine case-based reasoning with either a greedy algorithm or a complete integer-programming solver. This work also develops a hybrid adaptive paradigm that learns critical information to support search and workload splitting while it solves the problem. Extensive experiments show that these approaches improve the performance of the underlying sequential solvers. The hybrid paradigm solves many difficult problems left open after recent solver competitions. Although the empirical results are mainly on constraint satisfaction problems, this work also generalizes the reasoning component of the parallel scheduler to a new, case-based paradigm, and successfully applies it to protein-ligand docking.
-
Type
-
dissertation
-
Source
-
2009_2013.csv
-
degree
-
Ph.D.
-
Program
-
Computer Science
