Incomplete algorithms in the large-block parallelism of combinatorial problems

A technique for solving some types of NP-hard combinatorial problems by incomplete algorithms (i.e., the algorithms that are not generally guaranteed to be finite) is studied. The case in point is “programming in constraints” that uses the idea of updating the base of constraints along with the rejection of irrelevant constraints. Two approaches to some combinatorial problems solved by the incomplete algorithms are compared. The first approach is based on the large-block parallelization of the original problem with the subsequent solving of the resulting problems by an incomplete algorithm on a cluster. In the second approach, the original problem is solved on a single processor of the cluster (actually on a PC computer) by the same algorithm. It is shown that in some cases the speedup factor reached in the first approach can substantially exceed the number of processors in the cluster. The work was supported by the Russian Foundation for Basic Research (project N 07-01-00400a). The paper was prepared on the basis of the authors' report at the International Conference on Parallel Computing Technologies (PaVT-2008; http://agora.guru.ru/pavt).