Применение высокопроизводительных вычислений для поиска троек взаимно частично ортогональных диагональных латинских квадратов порядка 10

Олег Сергеевич Заикин, Эдуард Игоревич Ватутин, Алексей Дмитриевич Журавлев, Максим Олегович Манзюк

Аннотация


Статья посвящена поиску троек взаимно частично ортогональных диагональных латинских квадратов порядка 10. Для каждой известной пары ортогональных диагональных латинских квадратов порядка 10 достраивается третий диагональный латинский квадрат таким образом, чтобы условие ортогональности между ним и квадратами из рассматриваемой пары нарушалось в как можно меньшем количестве ячеек. Используются два подхода: первый основан на сведении исходной задачи к задаче о булевой выполнимости, а второй – на использовании метода грубой силы. Построено несколько троек указанного вида с рекордными характеристиками. Эксперименты были проведены в проекте добровольных распределенных вычислений SAT@home, а также на вычислительном кластере.


Ключевые слова


диагональные латинские квадраты, частичная ортогональность, задача о булевой выполнимости. добровольные распределенные вычисления, метод грубой силы, вычислительный кластер

Полный текст:

PDF

Литература


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