Geodesic
The search for pairs of orthogonal diagonal latin squares of order 10 in the volunteer computing project SAT@home
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 4 (2015) no. 3, pp. 95-108 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: Latin squares, volunteer computing, Boolean satisfiability problem, SAT@home project. 
@article{VYURV_2015_4_3_a7,
     author = {O. S. Zaikin and S. E. Kochemazov},
     title = {The search for pairs of orthogonal diagonal latin squares of order 10 in the volunteer computing project {SAT@home}},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {95--108},
     year = {2015},
     volume = {4},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2015_4_3_a7/}
}
TY  - JOUR
AU  - O. S. Zaikin
AU  - S. E. Kochemazov
TI  - The search for pairs of orthogonal diagonal latin squares of order 10 in the volunteer computing project SAT@home
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2015
SP  - 95
EP  - 108
VL  - 4
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VYURV_2015_4_3_a7/
LA  - ru
ID  - VYURV_2015_4_3_a7
ER  - 
%0 Journal Article
%A O. S. Zaikin
%A S. E. Kochemazov
%T The search for pairs of orthogonal diagonal latin squares of order 10 in the volunteer computing project SAT@home
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2015
%P 95-108
%V 4
%N 3
%U http://geodesic.mathdoc.fr/item/VYURV_2015_4_3_a7/
%G ru
%F VYURV_2015_4_3_a7
O. S. Zaikin; S. E. Kochemazov. The search for pairs of orthogonal diagonal latin squares of order 10 in the volunteer computing project SAT@home. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 4 (2015) no. 3, pp. 95-108. http://geodesic.mathdoc.fr/item/VYURV_2015_4_3_a7/

[1] Tuzhilin M.E., “On the history of the study of Latin squares”, Review of Applied and Industrial Mathematics, 19:2 (2012), 226–227

[2] C.J. Colbourn, J.H. Dinitz, Handbook of Combinatorial Designs, Second Edition, Chapman, 2006, 984 pp. | DOI | MR

[3] A. Biere, V. Heule, H. van Maaren, T. Walsh, Handbook of Satisfiability, IOS Press, 2009 | Zbl

[4] Semenov A.A., Zaikin O.S., Otpushchennikov I.V., Kochemazov S.E., “Using algorithms for solving Boolean satisfiability problem (SAT) to combinatorial problems”, Proceedings of the XII National Conference on Conrtol Problems, Publishing of the Institute of Control Sciences RAS, 2014, 7361–7374

[5] Semenov A.A., Bespalov D.V., “Technology for solving multidimensional problems of logical search”, Tomsk State University Journal, 2005, no. 14, 61–73

[6] H. Zhang, “Combinatorial Designs by SAT Solvers”, Handbook of Satisfiability, eds. Biere A., Heule V., van Maaren H., Walsh T., IOS Press, 2009, 533–568

[7] C. Gomes, D. Shmoys, “Completing quasigroups or Latin squares: A structured graph coloring problem”, Proceedings of the Computational Symposium on Graph Coloring and Generalizations, 2002, 22–39

[8] J.W. Brown, F. Cherry, L. Most, M. Most, E.T. Parker, W.D. Wallis, “Completion of the spectrum of orthogonal diagonal Latin squares”, Lecture notes in pure and applied mathematics, 139, 1992, 43–49 | MR

[9] Zaikin O.S., Posyipkin M.A., Semenov A.A., Hrapov N.P., “Experience of organizing volunteer computing project on the examples of OPTIMA@home and SAT@home”, Lobachevsky State Unversity of Nizhni Novgorod Journal, 2012, no. 5-2, 340–347

[10] Zaikin O.S., Semenov A.A., Posyipkin M.A., “Procedures for constructing decomposition sets for distributed SAT solving in the volunteer computing project SAT@home”, Large-scale systems control, 43 (2013), 138–156, Publishing of the Institute of Control Sciences RAS, Moskow

[11] SAT@home: proekt dobrovolnykh raspredelennykh vychislenii dlya resheniya krupnomasshtabnykh SAT-zadach, (data obrascheniya: 20.03.2015) http://sat.isa.ru/pdsat/

[12] D.P. Anderson, “BOINC: A System for Public-Resource Computing and Storage”, GRID, ed. Buyya R., IEEE Computer Society, 2004, 4–10 | DOI

[13] Ivashko E.E., Nikitina N.N., “Using BOINC-grid in resource-intensive scientific researches”, Novosibirsk State University Journal. Series information technologies, 11:1 (2013), 53–57

[14] Vatutin E.I., Titov V.S., “Use of volunteer computing platform BOINC to analyze the quality of partitions of a graph-schemes of parallel algorithms”, Proceedings of the Sixth International Conference «Parallel Computations and Control Problems», PACO'2012 (Publishing of the Institute of Control Sciences, Moscow, 2012), 37–54

[15] Grinberg Y.R., Kurochkin I.I., Korh A.V., “Algorithm for clustering elements of data networks”, Information technology and computer systems, 2012, no. 3, 18–30

[16] Zaikin O.S., Semenov A.A., “Application of the Monte Carlo method to predict time of parallel solving of the Boolean satisfiability problem”, Numerical methods and programming : new computational technologies, 2014, no. 1, 22–35

[17] Rainbow-tablitsy dlya shifra A5/1, (data obrascheniya 30.11.2014) http://opensource.srlabs.de/projects/a51decrypt

[18] N. Een, N. Sorensson, “An Extensible SAT-solver”, Lecture notes in computer science, 2919, 2003, 502–518 | DOI

[19] Egan J., Wanless I.M., Enumeration of MOLS of small order, arXiv: 1406.3681

[20] Grishagin V.A., Svistunov A.N., Parallel programming on the base of MPI, Publishing of the Lobachevsky State University of Nizhny Novgorod, 2005, 93 pp.