Incomplete algorithms in the large-block parallelism of combinatorial problems

Authors

  • A.A. Semenov Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)
  • O.S. Zaikin Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS) https://orcid.org/0000-0002-0145-5010

Keywords:

база ограничений, неполнота, крупноблочный параллелизм, декомпозиция, программирование в ограничениях, параллельные программы, прогнозная функция

Abstract

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-00400-a). 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/pavt2008).

Author Biographies

A.A. Semenov

O.S. Zaikin

References

  1. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
  2. Cook S.A. The complexity of theorem-proving procedures// Proc. of the Third Ann. ACM Symp. on Theory of Computing. Shaker Heights (Ohio, USA), 1971. 151-158 (Русский перевод: Кук С.А. Сложность процедур вывода теорем. Кибернетический сборник: Новая серия. 1975. Вып. 12. 5-15).
  3. Davis M., Longemann G., Loveland D. A machine program for theorem proving // Communications of the ACM. 1962. 5. 394-397.
  4. Devis M., Putnam H. A computing procedure for quantification theory // J. of ACM. 1960. 7. 201-215.
  5. Marqeus-Silva J.P., Sakallah K.A. GRASP: a search algorithm for propositional satisfiability // IEEE Trans. on Computers. 1999. 48, N 5. 506-521.
  6. Zchaff (http://www.princeton.edu/ chaff/zchaff.html).
  7. Berkmin (http://eigold.tripod.com/BerkMin.html).
  8. MiniSat (http://minisat.se/MiniSat.html).
  9. Robinson J.A. A machine-oriented logic based on the resolution principle // J. ACM. 1965. 12, N 1. 23-41.
  10. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983.
  11. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.
  12. Buchberger B. Groebner bases: an algorithmic method in polynomial ideal theory // Recent Trends in Multidimensional System Theory. Dordrecht: Reidel Publishing Company, 1985. 184-232.
  13. Кокс Д., Литтл Дж., О’Ши Д. Идеалы, многообразия и алгоритмы. М.: Мир, 2000.
  14. Агибалов Г.П. Логические уравнения в криптоанализе генераторов ключевого потока // Вестник Томского гос. ун-та. Приложение. 2003. № 6. 31-41.
  15. Заикин О.С., Семенов А.А. Технология крупноблочного параллелизма в SAT-задачах // Проблемы управления. 2008. № 1. 43-50.
  16. Заикин О.С., Семенов А.А., Сидоров И.А., Феоктистов А.Г. Параллельная технология решения SAT-задач с применением пакета прикладных программ D-SAT // Вестник Томского гос. ун-та. Приложение. 2007. № 23. 83-95.
  17. Заикин О.С., Сидоров И.А. Технология крупноблочного распараллеливания в криптоанализе некоторых генераторов двоичных последовательностей // Труды международной научной конференции ПАВТ’07. Челябинск, ЮУрГУ, 2007. 1. 158-169.
  18. Cеменов А.А. Логико-эвристический подход в криптоанализе генераторов двоичных последовательностей // Труды международной научной конференции ПАВТ’07. Челябинск, ЮУрГУ, 2007. 1. 170-180.
  19. Bruer J.O. On pseudo random sequences as crypto generators // Proc. Int. Zurich Seminar on Digital Communication. Zurich (Switzerland), 1984. 157-161.
  20. Menezes A., Van Oorschot P., Vanstone S. Handbook of Applied Cryptography. Boca Raton: CRC Press, 1997.
  21. Суперкомпьютерный центр ИДСТУ СО РАН (http://www.mvs.icc.ru).

Published

07-04-2008

How to Cite

Семенов А.А., Заикин О.С. Incomplete Algorithms in the Large-Block Parallelism of Combinatorial Problems // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2008. 9. 108-118

Issue

Section

Section 1. Numerical methods and applications