Integer and Constraint Programming Revisited for Mutually Orthogonal Latin Squares (Student Abstract)

Noah Rubin, Curtis Bright, Brett Stevens, Kevin K. H. CheungAAAI 2022 · DOI

Abstract

Finding Mutually Orthogonal Latin Squares (MOLS) is a classic but computationally intensive problem in combinatorics. This paper introduces two major technical refinements to improve the performance of automated reasoning tools: a novel "CP-index" encoding for Constraint Programming (CP) and an advanced symmetry-breaking method based on the disjoint cycle structure of permutations. These improvements allow solvers to handle larger orders more efficiently, successfully verifying pairs of MOLS up to order 11 and providing a more powerful framework for investigating the existence of order-10 triples.

Introduction

A Latin Square of order $n$ is an $n \times n$ grid where each symbol from $0$ to $n-1$ appears exactly once in every row and column. Two such squares are considered orthogonal if, when overlaid, every possible pair of symbols appears exactly once. Identifying sets of $k$ Mutually Orthogonal Latin Squares (MOLS) is a notoriously difficult task due to the astronomical growth of the search space as $n$ increases. While pairs of MOLS are known for order 10, the existence of a triple (three pairwise orthogonal squares) remains one of the most famous open problems in mathematics. This research aims to push the boundaries of current Integer Programming (IP) and Constraint Programming (CP) solvers to tackle these higher-order challenges.

Methodology

The researchers implemented two primary technical improvements to standard search models:

1. CP-index Encoding

Traditional CP models for MOLS often rely on "linear" encodings to define orthogonality. This paper proposes an alternative "CP-index" encoding based on an algebraic property: two Latin squares $X$ and $Y$ are orthogonal if there exists a third Latin square $Z$ such that $XZ = Y$, where rows are treated as permutations. This relationship is implemented using "element indexing" constraints, which allow the solver to more naturally navigate the dependencies between squares.

2. Advanced Symmetry Breaking

Latin squares possess high degrees of symmetry (e.g., swapping rows or columns). Previous "domain reduction" methods reduced the search space for the second square's first column to a size related to Fibonacci numbers ($F_{n-2}$). The authors introduced a new symmetry-breaking method based on the disjoint cycle structure of permutations. This reduces the search space to the number of partitions of $n-1$ into parts greater than 1, resulting in an exponential reduction ($e^{O(\sqrt{n})}$) compared to previous techniques.

Results and Discussion

The combination of the CP-index encoding and the new symmetry-breaking method yielded significant performance gains across both IP and CP solvers.

Figure 1: Running time comparison across different orders and models.

As shown in Figure 1, the CP-index encoding consistently outperformed the standard CP-linear approach. The impact of the new symmetry-breaking method ("cycle type") is particularly evident in the IP solver's performance, allowing it to reach order 10, whereas the previous state-of-the-art model timed out at order 9.

Performance Benchmarks

The specific running times for orders 5 through 10 highlight the efficiency of the new models. At order $n=9$, the CP-index model was approximately 150 times faster than the CP-linear model. Furthermore, at order $n=10$, the CP-index model completed the search in roughly 215 seconds, while the linear model failed to finish within a 16-hour (60,000-second) window.

Figure 2: Specific running times (in seconds) for IP and CP models across orders 5-10.

Using these improved encodings, the authors were able to find or prove the nonexistence of MOLS pairs for all orders up to $n=11$.

Conclusion

By refining how MOLS problems are encoded and reducing search space through advanced symmetry breaking, this work significantly extends the reach of automated solvers. The CP-index encoding, in particular, proved to be a robust tool for handling higher-order squares. While the existence of an order-10 triple remains unsolved, the tools developed here provide the necessary computational efficiency to begin a rigorous analysis of this long-standing mathematical mystery.

Reference: Rubin, N., Bright, C., Stevens, B., & Cheung, K. (2022). Integer and Constraint Programming Revisited for Mutually Orthogonal Latin Squares (Student Abstract). Proceedings of the AAAI Conference on Artificial Intelligence.

Summary updated

BibTeX
@inproceedings{rubin2022integer,
  author = {Noah Rubin and Curtis Bright and Brett Stevens and Kevin K. H. Cheung},
  title = {{Integer and Constraint Programming Revisited for Mutually Orthogonal Latin Squares (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i11.21655},
}
Figure