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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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 
@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
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/

[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