Applying High-Performance Computing to Searching for Triples of Partially Orthogonal Latin Squares of Order 10

Oleg S. Zaikin, Eduard I. Vatutin, Alexey D. Zhuravlev, Maksim O. Manzyuk

Abstract


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, brute force, computing cluster

References


Colbourn C.J., Dinitz J.H. Handbook of Combinatorial Designs. Second Edition. — Chapman&Hall, — 2006. — 984 p.

Malih A.E., Danilova V.I. Ob istoricheskom processe razvitiya teorii latinskih kvadratov i nekotoryh ih prilozheniyah [About Historical Process of the Evolution of Latin squares and Some Their Applications] // Vestnik Permskogo universiteta. Seria: Matematika, Mehanika, Informatika [Bulletin of Perm University: Mathematics, Mechanics, Computer Science]. 2010. No. 4. P. 95–104.

Tuzhilin M.E. Ob istorii issledovany latinskikh kvadratov [On the History of the Study of Latin Squares] // Obozreniye prikladnoy i promyshlennoy matematiki [Review of Applied and Industrial Mathematics]. 2012. Vol. 19, Issue 2. P. 226–227.

Brown J.W., Cherry F., Most L., Most M., Parker E.T., Wallis W.D. Completion of the Spectrum of Orthogonal Diagonal Latin Squares // Lecture Notes in Pure and Applied Mathematics. 1992. Vol. 139. P. 43–49.

Egan J.E., Wanless I.M. Enumeration of MOLS of Small Order // Mathematics of Computation. 2016. Vol. 85. P. 799–824.

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

Semenov A.A., Bespalov D.V. Tehnologiya resheniya mnogomernih zadach logicheskogo poiska [Technology for Solving Multidimensional Problems of the Logical Search] // Vestnik Tomskogo gosudarstvennogo universiteta [Bulletin of Tomsk State University]. 2005. No. 14. P. 61–73.

Zhang H. Combinatorial Designs by SAT Solvers. In: Biere A., Heule V., van Maaren H., Walsh T. (eds.) Handbook of Satisfiability. IOS Press, 2009. P. 533–568.

Zaikin O.S., Semenov A.A., Posypkin M.A. Constructing Decomposition Sets for Distributed Solution of SAT problems in Volunteer Computing Project SAT@home // Large-Scale Systems Control. 2013. Issue 43. P. 138–156.

Zaikin O.S., Posypkin M.A., Semenov A.A., Khrapov N.P. Opyt organizacii dobrovolnih vichisleniy na primere proektov OPTIMA@home i SAT@home [The Experience of Organizing Volunteer Computing Projects on the Examples of OPTIMA@home and SAT@home Projects] // Vestnik Nizhegorodskogo universiteta imeni N.I. Lobachevskogo [Bulletin of the Lobachevsky University of Nizhni Novgorod]. 2012. No. 5-2. P. 340–347.

Zaikin O.S., Kochemazov S.E. 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’. 2015. Vol. 4, No. 3. P. 95–108.

Een N., Sorensson N. An Extensible SAT-solver // Lecture Notes in Computer Science. 2003. Vol. 2919. P. 502–518.

Zaikin O., Kochemazov S. 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, 2015. CEUR-WS. Vol. 1502. P. 52–63.

Biere A. Lingeling, Plingeling and Treengeling Entering the SAT Competition 2013 // Proceedings of SAT Competition 2013. 2013. Vol. B-2013-1. P. 51–52.

Maric F., Janicic P. Formal Correctness Proof for DPLL Procedure // Informatica. 2010. Vol. 21, Issue 1. P. 57–78.

Vatutin E.I., Zhuravlev A.D., Zaikin O.S., Titov V.S. Features of the Use of Weighting Heuristics in the Search for Diagonal Latin Squares // Proceedings of the South-West State University. Series ‘Control, Computer Engineering, Information Science. Medical Instruments Engineering’. 2015. No. 3 (16). P. 18–30.

Land A.H., Doig A.G. An Automatic Method of Solving Discrete Programming Problems // Econometrica. 1960. Vol. 28, No. 3. P. 497–520.

Vatutin E.I., Romanchenko A.S., Titov V.S. 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). P. 58–64.

Vatutin E.I., Bobyntcev D.O., Romanchenko A.S. 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. P. 8–16.




DOI: http://dx.doi.org/10.14529/cmse160304