DROPS

Document

Short Paper

DOI: 10.4230/LIPIcs.CP.2023.47

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

Authors: Renee Mirka, Laura Greenstreet, Marc Grimson, and Carla P. Gomes

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

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.

Cite as

Renee Mirka, Laura Greenstreet, Marc Grimson, and Carla P. Gomes. A New Approach to Finding 2 x n Partially Spatially Balanced Latin Rectangles (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 47:1-47:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.CP.2023.47},
  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}
}

@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/entities/document/10.4230/LIPIcs.CP.2023.47},
  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}
}

Search Results

Documents authored by Grimson, Marc

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

Abstract

Cite as

Thanks for your feedback!

Could not send message