zbMATH — the first resource for mathematics

The Langford’s problem: A challenge for parallel resolution of CSP. (English) Zbl 1057.68686
Wyrzykowski, Roman (ed.) et al., Parallel processing and applied mathematics. 4th international conference, PPAM 2001, Nałȩczów, Poland, September 9–12, 2001. Revised papers. Berlin: Springer (ISBN 3-540-43792-4). Lect. Notes Comput. Sci. 2328, 789-796 (2002).
Summary: The paper is mainly concerned with the parallel efficiency of finite constraint satisfaction problems. Langford’s combinatorial problem is used as benchmark and represents a real Challenging Problem especially for Parallel CSP resolution. A more compact encoding is introduced which clearly improves by a factor of ten the basic one for the Forward-Checking and Minimum Remaining Value (FC-MRV) algorithm. The applicability and benefit of this approach are studied within a shared memory model using the new emerging standard OpenMP library. A preliminary implementation is sketched and the experiments were carried out running on the Silicon Graphics Origin’2000 parallel machine. For the Langford’s problem, we mainly highlight appreciable linear efficiencies until 32 processors.
For the entire collection see [Zbl 0992.00055].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
Full Text: Link