Integer and Constraint Programming Revisited for Mutually Orthogonal Latin Squares
This work addresses a combinatorial design problem for researchers in mathematics and computer science, but it is incremental as it builds on existing methods with updated solvers.
The authors tackled the problem of searching for sets of mutually orthogonal Latin squares (MOLS) using modern integer and constraint programming solvers, achieving quick results for all orders up to ten and improving solver effectiveness with symmetry breaking and encoding enhancements.
In this paper we provide results on using integer programming (IP) and constraint programming (CP) to search for sets of mutually orthogonal latin squares (MOLS). Both programming paradigms have previously successfully been used to search for MOLS, but solvers for IP and CP solvers have significantly improved in recent years and data on how modern IP and CP solvers perform on the MOLS problem is lacking. Using state-of-the-art solvers as black boxes we were able to quickly find pairs of MOLS (or prove their nonexistence) in all orders up to ten. Moreover, we improve the effectiveness of the solvers by formulating an extended symmetry breaking method as well as an improvement to the straightforward CP encoding. We also analyze the effectiveness of using CP and IP solvers to search for triples of MOLS, compare our timings to those which have been previously published, and estimate the running time of using this approach to resolve the longstanding open problem of determining the existence of a triple of MOLS of order ten.