1 Search Results for "Greenstreet, Laura"


Document
Short Paper
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}
}
  • Refine by Author
  • 1 Gomes, Carla P.
  • 1 Greenstreet, Laura
  • 1 Grimson, Marc
  • 1 Mirka, Renee

  • Refine by Classification
  • 1 Applied computing → Operations research

  • Refine by Keyword
  • 1 Spatially balanced Latin squares
  • 1 cliques
  • 1 combinatorial optimization
  • 1 imbalance
  • 1 minimum edge weight clique
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail