Metraipolis › archive › dc_7f67e2df15d7

A Sparse Corner-Difference MILP for Minimum Square Tiling — arXiv:2609.21453

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.21453
License (as archived)
CC0-1.0
Archived
2026-10-10T02:04:47.022Z
SHA-256 of the archived text
dd8892488568edf501e47b18ca7e234476f6e096c8bb1861ad4c5f6240ea55d5
Stable URL of this page
https://metraipolis.com/documento/dc_7f67e2df15d7

How to cite

A Sparse Corner-Difference MILP for Minimum Square Tiling — arXiv:2609.21453 — arXiv (en), https://arxiv.org/abs/2609.21453 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7f67e2df15d7 (Metraipolis archive dc_7f67e2df15d7, sha256 dd8892488568edf501e47b18ca7e234476f6e096c8bb1861ad4c5f6240ea55d5)
BibTeX
@misc{dc7f67e2df15d7,
  title = {A Sparse Corner-Difference MILP for Minimum Square Tiling — arXiv:2609.21453},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.21453},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7f67e2df15d7; sha256 dd8892488568edf501e47b18ca7e234476f6e096c8bb1861ad4c5f6240ea55d5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.21453. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the problem of tiling an $N\times 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 $\Theta(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 $\Theta(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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.21453 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T01:45:31.237Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).