Geodesic
Applying high-performance computing to searching for triples of partially orthogonal Latin squares of order 10
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 5 (2016) no. 3, pp. 54-89

Voir la notice de l'article provenant de la source Math-Net.Ru

This paper deals with the search for triples of partially orthogonal Latin squares of order 10. For every known pair of orthogonal Latin squares of order 10 we add a third diagonal Latin square in such a way that the orthogonality condition between it and squares from a considered pair coincides in the maximum possible number of cells. Two approaches are used: the first one is based on reducing an original problem to Boolean satisfiability problem; the second one is based on Brute force method. Several triples of the aforementioned kind with high characteristics were constructed. The experiments were held in the volunteer computing project SAT@home and on a computing cluster.
Keywords: diagonal Latin squares, partial orthogonality, Boolean satisfiability problem, volunteer computing, computing cluster.
Mots-clés : brute force 
O. S. Zaikin; E. I. Vatutin; A. D. Zhuravlev; M. O. Manzyuk. Applying high-performance computing to searching for triples of partially orthogonal Latin squares of order 10. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 5 (2016) no. 3, pp. 54-89. http://geodesic.mathdoc.fr/item/VYURV_2016_5_3_a3/
@article{VYURV_2016_5_3_a3,
     author = {O. S. Zaikin and E. I. Vatutin and A. D. Zhuravlev and M. O. Manzyuk},
     title = {Applying high-performance computing to searching for triples of partially orthogonal {Latin} squares of order 10},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {54--89},
     year = {2016},
     volume = {5},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2016_5_3_a3/}
}
TY  - JOUR
AU  - O. S. Zaikin
AU  - E. I. Vatutin
AU  - A. D. Zhuravlev
AU  - M. O. Manzyuk
TI  - Applying high-performance computing to searching for triples of partially orthogonal Latin squares of order 10
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2016
SP  - 54
EP  - 89
VL  - 5
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VYURV_2016_5_3_a3/
LA  - ru
ID  - VYURV_2016_5_3_a3
ER  - 
%0 Journal Article
%A O. S. Zaikin
%A E. I. Vatutin
%A A. D. Zhuravlev
%A M. O. Manzyuk
%T Applying high-performance computing to searching for triples of partially orthogonal Latin squares of order 10
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2016
%P 54-89
%V 5
%N 3
%U http://geodesic.mathdoc.fr/item/VYURV_2016_5_3_a3/
%G ru
%F VYURV_2016_5_3_a3

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

[2] A.E. Malih, V.I. Danilova, “About Historical Process of the Evolution of Latin squares and Some Their Applications”, Bulletin of Perm University: Mathematics, Mechanics, Computer Science, 2010, no. 4, 95–104

[3] M.E. Tuzhilin, “On the History of the Study of Latin Squares”, Review of Applied and Industrial Mathematics, 19:2 (2012), 226–227

[4] 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

[5] J.E. Egan, I.M. Wanless, “Enumeration of MOLS of Small Order”, Mathematics of Computation, 85 (2015), 799–824 | DOI

[6] A. Biere, V. Heule, H. van Maaren, T. Walsh (eds.), Handbook of Satisfiability, IOS Press, 2009, 980 pp.

[7] A.A. Semenov, D.V. Bespalov, “Technology for Solving Multidimensional Problems of the Logical Search”, Bulletin of Tomsk State University, 2005, no. 14, 61–73

[8] H. Zhang, “Combinatorial Designs by SAT Solvers”, Handbook of Satisfiability, 2009, no. 14, 533–568, IOS Press

[9] O.S. Zaikin, A.A. Semenov, M.A. Posypkin, “Constructing Decomposition Sets for Distributed Solution of SAT problems in Volunteer Computing Project SAT@home”, Large-Scale Systems Control, 2013, no. 43, 138–156

[10] O.S. Zaikin, M.A. Posypkin, A.A. Semenov, N.P. Khrapov, “The Experience of Organizing Volunteer Computing Projects on the Examples of OPTIMA@home and SAT@home Projects”, Bulletin of the Lobachevsky University of Nizhni Novgorod, 2012, no. 5-2, 340–347

[11] 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”, Bulletin of the South Ural State University: Series Computational Mathematics and Software Engineering, 4:3 (2015), 95–108

[12] N. Een, N. Sorensson, “An Extensible SAT-solver”, Lecture Notes in Computer Science, 2919 (2003), 502–518 | DOI

[13] O. Zaikin, S. Kochemazov, “The Search for Systems of Diagonal Latin Squares Using the SAT@home Project”, Proceedings of the Second International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2015) (Petrozavodsk, Russia), CEUR Workshop Proceedings, 1502, 2015, 52–63

[14] A. Biere, “Lingeling, Plingeling and Treengeling Entering the SAT Competition 2013”, Proceedings of SAT Competition 2013., B-2013-1 (2013), 51–52

[15] F. Maric, P. Janicic, “Formal Correctness Proof for DPLL Procedure”, Informatica, 21:1 (2010), 57–78

[16] E.I. Vatutin, A.D. Zhuravlev, O.S. Zaikin, V.S. Titov, “Osobennosti ispolzovaniya vzveshivayuschikh evristik v zadache poiska diagonalnykh latinskikh kvadratov”, Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya: Upravlenie, vychislitelnaya tekhnika, informatika. Meditsinskoe priborostroenie, 2015, no. 3(16), 18–30

[17] A.H. Land, A.G. Doig, “An Automatic Method of Solving Discrete Programming Problems”, Econometrica, 28:3 (1960), 497–520 | DOI

[18] E.I. Vatutin, A.S. Romanchenko, V.S. Titov, “Investigation of the Effect of Pairs Consideration Order on the Quality of Scheduling Using the Greedly Approach”, Proceedings of South-West State University, 2013, no. 1(46), 58–64

[19] E.I. Vatutin, D.O. Bobyntcev, A.S. Romanchenko, “Investigation of the Effect of Partial Ordering of Pairs and the Local Improvement of Pair Neighborhood on Schedule Quality Using the Greedy Approach”, Proceedings of South-West State University. Series Control, Computer Engineering, Information Science. Medical Instruments Engineering, 2014, no. 1, 8–16