The search for pairs of orthogonal diagonal Latin Squares of order 10 in the volunteer computing project SAT@home
DOI:
https://doi.org/10.14529/cmse150308Keywords:
Latin squares, volunteer computing, Boolean satisfiability problem, SAT@home projectAbstract
In this paper we consider the approach to search for systems of orthogonal Latin Squares, that is based on reducing the corresponding problems to Boolean Satisfiability problem. We constructed the SAT encoding for finding orthogonal diagonal Latin Squares of order 10. Using this encoding and the resources provided by the volunteer computing project SAT@home we managed to find 17 previously unknown pairs. Based on these 17 pairs and on 3 previously published pairs we constructed the pseudotriples of diagonal Latin Squares of order 10. To construct pseudotriples we employed the computing cluster. The last step required us to make parallel implementation of the algorithm for generating diagonal Latin Squares of order 10.
References
Тужилин М.Э. Об истории исследований латинских квадратов / М.Э. Тужилин // Обозрение прикладной и промышленной математики. — 2012. — Т. 19, Вып. 2. — С. 226–227.
Colbourn C.J. Handbook of Combinatorial Designs. Second Edition / C.J. Colbourn, J.H. Dinitz. — Chapman&Hall, — 2006. — 984 p.
Biere A. Handbook of Satisfiability / A. Biere, V. Heule, H. van Maaren, T. Walsh (eds.). — IOS Press. — 2009.
Семенов А.А. Применение алгоритмов решения проблемы булевой выполнимости (SAT) к комбинаторным задачам / А.А. Семенов, О.С. Заикин, И.В. Отпущенников, С.Е. Кочемазов // Труды XII Всероссийского совещания по проблемам управления. — Изд-во ИПУ РАН. — 2014. — С. 7361–7374.
Семенов А.А. Технологии решения многомерных задач логического поиска / А.А. Семенов, Д.В. Беспалов // Вестник Томского государственного университета. —2005. — № 14. — С. 61–73.
Zhang H. Combinatorial Designs by SAT Solvers / H. Zhang. — In: Biere A., Heule V., van Maaren H., Walsh T. (eds.) Handbook of Satisfiability. — IOS Press. — 2009. P. 533–568.
Gomes C. Completing quasigroups or Latin squares: A structured graph coloring problem / C. Gomes, D. Shmoys // Proceedings of the Computational Symposium on Graph Coloring and Generalizations. — 2002. — P. 22–39.
Brown J.W. Completion of the spectrum of orthogonal diagonal Latin squares / J.W. Brown, F. Cherry, L. Most, M. Most, E.T. Parker, W.D. Wallis // Lecture notes in pure and applied mathematics. — 1992. — Vol. 139. — P. 43–49.
Заикин О.С. Опыт организации добровольных вычислений на примере проектов OPTIMA@home и SAT@home / О.С. Заикин, М.А. Посыпкин, А.А. Семенов, Н.П. Храпов // Вестник Нижегородского университета им. Н.И. Лобачевского. — 2012. — № 5-2. — С. 340–347.
Заикин О.С. Процедуры построения декомпозиционных множеств для распределен-ного решения SAT-задач в проекте добровольных вычислений SAT@home / О.С. Заикин, А.А. Семенов, М.А. Посыпкин // Управление большими системами. — М.: ИПУ РАН. — Вып. 43. — 2013. — С. 138–156.
SAT@home: проект добровольных распределенных вычислений для решения круп-номасштабных SAT-задач. URL: http://sat.isa.ru/pdsat/ (дата обращения 20.03.2015).
Anderson D.P. BOINC: A System for Public-Resource Computing and Storage / D.P. Anderson // In: Buyya, R. (ed.) GRID, IEEE Computer Society. — 2004 — P. 4–10.
Ивашко Е.Е. Использование BOINC-грид в вычислительноемких научных исследо-ваниях / Е.Е. Ивашко, Н.Н. Никитина // Вестник Новосибирского государственного университета. Серия: Информационные технологии. — 2013. — Т. 11, № 1. — С. 53–57.
Ватутин Э.И. Использование добровольных распределенных вычислений на плат-форме BOINC для анализа качества разбиений граф-схем параллельных алгоритмов / Э.И. Ватутин, В.С. Титов // Труды шестой международной конференции «Параллельные вычисления и задачи управления» PACO'2012. — Институт проблем управления им. В.А. Трапезникова РАН, Москва. — 2012. — С. 37–54.
Гринберг Я.Р. Алгоритм кластеризации элементов сетей передачи данных / Я.Р. Гринберг, И.И. Курочкин, А.В. Корх // Информационные технологии и вычисли-тельные системы. — 2012. — № 3. — С. 18–30.
Заикин О.С. Применение метода Монте-Карло к прогнозированию времени парал-лельного решения проблемы булевой выполнимости / О.С. Заикин, А.А. Семенов // Вычислительные методы и программирование: новые вычислительные технологии. — 2014. — Т. 15, № 1. — С. 22–35.
Rainbow-таблицы для шифра A5/1. URL: http://opensource.srlabs.de/projects/a51-decrypt (дата обращения 30.11.2014).
Een N. An Extensible SAT-solver / N. Een, N. Sorensson // Lecture notes in computer science. — 2003. — Vol. 2919. — P. 502–518.
Egan J. Enumeration of MOLS of small order / Egan J., Wanless I.M. // arXiv:1406.3681v2 [math.CO].
Гришагин В.А. Параллельное программирование на основе MPI / В.А. Гришагин, А.Н. Свистунов. — Изд-во ННГУ им. Н.И. Лобачевского. — 2005. — 93 с.
