Parallel Discrepancy-Based Search: An Efficient and Scalable Search Strategy for Massively Parallel Supercomputers Providing Intrinsic Load-Balancing Without Communication

Free registration required

Executive Summary

Backtracking strategies based on the computation of discrepancies have proved themselves successful at solving large problems. They show really good performance when provided with a high-quality domain-specific branching heuristic (variable and value ordering heuristic), which is the case for many industrial problems. The authors propose a novel approach (PDS) that allows parallelizing a strategy based on the computation of discrepancies (LDS). The pool of processors visits the leaves in exactly the same order as the centralized algorithm would do. The implementation allows for a natural/intrinsic load balancing to occur (filtering induced by constraint propagation would affect each processor pretty much in the same way), although there is no communication between processors.

  • Format: PDF
  • Size: 498.4 KB