A Sparse Corner-Difference MILP for Minimum Square Tiling
Abstract
We study the problem of tiling an N× N square with axis-aligned squares whose side lengths are integers strictly less than N, with the objective of minimizing the number of tiles. The standard placement-based exact-cover MILP contains Θ(N5) placement-to-cell nonzero coefficients and is also affected by the dihedral symmetry of the square domain. We introduce a Corner-Difference MILP (CD-MILP) that represents each selected square by at most four signed corner coefficients. Two-dimensional prefix reconstruction shows that the resulting constraints are equivalent to the original cell-cover equations, while reducing the coverage-related nonzero count to Θ(N3). We also introduce lightweight corner-ordering constraints that retain at least one representative from every D4 orbit, although ties may leave residual symmetry. Computational experiments on nine prime-size instances compare the baseline, CD-MILP, the baseline with corner ordering, and their combination using Gurobi and COPT. Under the stated experimental settings, the combined formulation solves eight instances with Gurobi and seven with COPT, compared with four and five, respectively, for the baseline. Its average presolved matrixs contain approximately 105 nonzero coefficients on average, compared with approximately 107 for the baseline.
Related
- Positive Square Energy of Graphs with Minimum Degree at Least Two
- Commutative rings with square-difference factor absorbing factorization
- Singular difference graphs of vector spaces of square matrices
- Fisher Information and the Minimum Mean-Square Error for Locating Closely Spaced Point Sources
- Sparse Moore-local realisations of binary irreducible polynomials on near-square lattice regions
BibTeX
@misc{yu2026sparse,
title = {{A Sparse Corner-Difference MILP for Minimum Square Tiling}},
author = {Zhuo Yu and Yuan Wang and Zhuo Liu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21453},
eprint = {2609.21453},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21453},
}
RIS
TY - UNPB
TI - A Sparse Corner-Difference MILP for Minimum Square Tiling
AU - Zhuo Yu
AU - Yuan Wang
AU - Zhuo Liu
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21453
UR - https://arxiv.org/abs/2609.21453
AB - We study the problem of tiling an N× N square with axis-aligned squares whose side lengths are integers strictly less than N, with the objective of minimizing the number of tiles. The standard placement-based exact-cover MILP contains Θ(N^5) placement-to-cell nonzero coefficients and is also affected by the dihedral symmetry of the square domain. We introduce a Corner-Difference MILP (CD-MILP) that represents each selected square by at most four signed corner coefficients. Two-dimensional prefix reconstruction shows that the resulting constraints are equivalent to the original cell-cover equations, while reducing the coverage-related nonzero count to Θ(N^3). We also introduce lightweight corner-ordering constraints that retain at least one representative from every D_4 orbit, although ties may leave residual symmetry. Computational experiments on nine prime-size instances compare the baseline, CD-MILP, the baseline with corner ordering, and their combination using Gurobi and COPT. Under the stated experimental settings, the combined formulation solves eight instances with Gurobi and seven with COPT, compared with four and five, respectively, for the baseline. Its average presolved matrixs contain approximately 10^5 nonzero coefficients on average, compared with approximately 10^7 for the baseline.
ER -