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.
|School:||University of Connecticut|
|School Location:||United States -- Connecticut|
|Source:||DAI-B 70/11, Dissertation Abstracts International|
|Keywords:||Distributed computing, Distributed search, Parallel computing|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be