License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.48
URN: urn:nbn:de:0030-drops-190855
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19085/
Go to the corresponding LIPIcs Volume Portal

Peruvemba Ramaswamy, Vaidyanathan ; Szeider, Stefan

Proven Optimally-Balanced Latin Rectangles with SAT (Short Paper)

pdf-format:
LIPIcs-CP-2023-48.pdf (0.6 MB)

Abstract

Motivated by applications from agronomic field experiments, Díaz, Le Bras, and Gomes [CPAIOR 2015] introduced Partially Balanced Latin Rectangles as a generalization of Spatially Balanced Latin Squares. They observed that the generation of Latin rectangles that are optimally balanced is a highly challenging computational problem. They computed, utilizing CSP and MIP encodings, Latin rectangles up to 12 × 12, some optimally balanced, some suboptimally balanced.
In this paper, we develop a SAT encoding for generating balanced Latin rectangles. We compare experimentally encoding variants. Our results indicate that SAT encodings perform competitively with the MIP encoding, in some cases better. In some cases we could find Latin rectangles that are more balanced than previously known ones. This finding is significant, as there are many arithmetic constraints involved. The SAT approach offers the advantage that we can certify that Latin rectangles are optimally balanced through DRAT proofs that can be verified independently.

BibTeX - Entry

@InProceedings{peruvembaramaswamy_et_al:LIPIcs.CP.2023.48,
  author =	{Peruvemba Ramaswamy, Vaidyanathan and Szeider, Stefan},
  title =	{{Proven Optimally-Balanced Latin Rectangles with SAT}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{48:1--48:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19085},
  URN =		{urn:nbn:de:0030-drops-190855},
  doi =		{10.4230/LIPIcs.CP.2023.48},
  annote =	{Keywords: combinatorial design, SAT encodings, certified optimality, arithmetic constraints, spatially balanced Latin rectangles}
}

Keywords: combinatorial design, SAT encodings, certified optimality, arithmetic constraints, spatially balanced Latin rectangles
Collection: 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Issue Date: 2023
Date of publication: 22.09.2023
Supplementary Material: Software (Script, Encodings and Models): https://doi.org/10.5281/zenodo.8151905

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI