Parallel Methods for Constraint Solving and Combinatorial Optimization

NII Shonan Meeting:

@ Shonan Village Center, May. 28-31, 2012

NII Shonan Meeting Report (ISSN 2186-7437):No.2012-5


  • Philippe Codognet, (JFLI-CNRS/UPMC/University of Tokyo)
  • Kazunori Ueda, (Waseda University)
  • Hiroshi Hosobe, (NII)


In the last decade, with the development of multi-core workstations, the availability of GPGPU-enhanced systems and the access to Grid platforms and supercomputers worldwide, Parallel Programming reached mainstream programming and appeared as a key issue in order to use in an efficient manner the computing power at hand.

With the move towards Exascale computing during this decade, this trend will develop all the more.

Search methods and combinatorial optimization techniques are not isolated from this phenomenon, as bigger computing power means the ability to attack more complex combinatorial problems.

In the last years some experiments have been done to extend to parallel execution search methods such as Constraint Programming or SAT solving (Boolean satisfiability), and combinatorial optimization methods such as Local Search, Meta-heuristics and Brand & Bound. However these works have mostly been done for shared memory multi-core systems (i.e. with a few cores) or for small PC clusters (a few machines).

The next challenge is to devise efficient techniques and algorithms for massively parallel computers with tens or hundreds of thousands of cores in the form of heterogeneous hybrid systems based on both multi-core processors and GPUs.

We would like to provide a cross-community forum for researchers working on search methods (Constraint Solving, Artificial Intelligence, Logic Programming, SAT solving, etc), combinatorial optimization methods (metaheuristics, local search, tabu search, evolutionary algorithms, ant colony optimization, particle swarm optimization, memetic algorithms, and other types of algorithms) and High Performance Computing (Grids, large PC clusters, massively parallel computers, GPGPUs) in order to tackle the challenge of efficient implementations on all kinds of parallel hardware: multi-core, GPU-based or heterogeneous massively parallel systems.

Topics that will be addressed include: – parallelization of existing search algorithms and new parallel methods;

– constraint solving and SAT solving on parallel hardware;

– heuristic search algorithms and combinatorial optimization on parallel hardware;

– programming paradigms, languages and implementation issues for Grids, large PC clusters, massively parallel computers, and GPUs;

– heterogeneous massively parallel systems – adaptive strategies and learning for parallel search and optimization; – applications and benchmarking; – theoretical studies and complexity.

This meeting is designed to be a forum for researchers willing to tackle those issues, in order to exchange ideas, theoretical frameworks, design of algorithms and methods, implementation issues, experimental results and further boost this growing area through cross-fertilization.