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.47
URN: urn:nbn:de:0030-drops-190849
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19084/
Go to the corresponding LIPIcs Volume Portal

Mirka, Renee ; Greenstreet, Laura ; Grimson, Marc ; Gomes, Carla P.

A New Approach to Finding 2 x n Partially Spatially Balanced Latin Rectangles (Short Paper)

pdf-format:
LIPIcs-CP-2023-47.pdf (0.8 MB)

Abstract

Partially spatially balanced Latin rectangles are combinatorial structures that are important for experimental design. However, it is computationally challenging to find even small optimally balanced rectangles, where previous work has not been able to prove optimality for any rectangle with a dimension above size 11. Here we introduce a graph-based encoding for the 2 × n case based on finding the minimum-cost clique of size n. This encoding inspires a new mixed-integer programming (MIP) formulation, which finds exact solutions for the 2 × 12 and 2 × 13 cases and provides improved bounds up to n = 20. Compared to three other methods, the new formulation establishes the best lower bound in all cases and establishes the best upper bound in five out of seven cases.

BibTeX - Entry

@InProceedings{mirka_et_al:LIPIcs.CP.2023.47,
  author =	{Mirka, Renee and Greenstreet, Laura and Grimson, Marc and Gomes, Carla P.},
  title =	{{A New Approach to Finding 2 x n Partially Spatially Balanced Latin Rectangles}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{47:1--47:11},
  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/19084},
  URN =		{urn:nbn:de:0030-drops-190849},
  doi =		{10.4230/LIPIcs.CP.2023.47},
  annote =	{Keywords: Spatially balanced Latin squares, partially spatially balanced Latin rectangles, minimum edge weight clique, combinatorial optimization, mixed integer programming, imbalance, cliques}
}

Keywords: Spatially balanced Latin squares, partially spatially balanced Latin rectangles, minimum edge weight clique, combinatorial optimization, mixed integer programming, imbalance, cliques
Collection: 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Issue Date: 2023
Date of publication: 22.09.2023

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