Separating control from specification for parallel and distributed search algorithms

Abstract

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.