Dissertation/Thesis Abstract

Separating control from specification for parallel and distributed search algorithms
by See, Andrew G., Ph.D., University of Connecticut, 2009, 173; 3384551
Abstract (Summary)

Discrete combinatorial optimization problems are ubiquitous in modern civilization. Unfortunately these problems are also difficult to solve and are often NP-hard. Two techniques have proved particularly well suited: Constraint Programming and Local Search. Research on these two areas has proceeded largely independently and they have yet to be effectively combined into a single framework. Moreover, insufficient progress has been made to exploit the structure of combinatorial optimization for execution on modern parallel hardware, leaving parallel optimization algorithms difficult to code. Though parallelizing can not make NP-Hard problems solvable in polynomial time, significant performance gains are possible in many practical problems.

This thesis argues in favor of separating the search specification from search control, and the mapping to the underlying hardware architecture. By isolating these orthogonal elements, one can easily experiment with new search algorithms and move from a sequential to a parallel or distributed architecture. The parallelizations described in this thesis target a modest number of processors (e.g., multi-core desktop machines, clusters of workstations, and mid-range supercomputers) that are easily obtainable for most users. Code samples show the usefulness of the approach for users while experimental results show the feasibility of applying it to difficult real world problems.

Indexing (document details)
School: University of Connecticut
School Location: United States -- Connecticut
Source: DAI-B 70/11, Dissertation Abstracts International
Subjects: Computer science
Keywords: Distributed computing, Distributed search, Parallel computing
Publication Number: 3384551
ISBN: 978-1-109-48883-8
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy