Reproduce “Integer and Constraint Programming Revisited for Mutually Orthogonal Latin Squares” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Noah Rubin, Curtis Bright, Kevin K. H. Cheung, Brett Stevens
Updated integer-programming and constraint-programming models show that modern general-purpose solvers can find pairs of mutually orthogonal Latin squares, or certify infeasibility, through order 10. An indexing-based CP formulation and cycle-type symmetry breaking improve search substantially, but exhaustive solver-based exploration is estimated to require about $10^{20}$ years to resolve the existence of three MOLS of order 10.
Key insights
- The CP-index formulation generally outperforms the arithmetic CP model and IP on feasible pair searches, particularly at order 10, where it is much faster than the alternatives.
- Symmetry handling has a major effect on runtime; organizing searches by cycle types can reduce the relevant first-column cases more effectively than the earlier Fibonacci-based restriction.
- Fast performance on individual fixed-square instances does not make exhaustive triple-MOLS(10) search practical, because the remaining candidate space is extraordinarily large.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.