Abstract
We present a range of techniques for tackling the problem of finding sets of Mutually Orthogonal Latin Rectangles (MOLR). In particular, we use a construction that allows us to search for solutions of a particular form with much reduced effort, and a seeding heuristic for the MOLR problem that allows a local search approach to find much better solutions than would be possible otherwise. Finally, we use the MOLR solutions found to construct solutions to the social golfer problem that improve the best known number of rounds for 43 instances, by as many as 10 rounds.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barnier, N., Brisset, P.: Solving the Kirkman’s Schoolgirl Problem in a few seconds. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 477–491. Springer, Heidelberg (2002)
Colbourn, C.H., Dinitz, J.H. (eds.): The CRC Handbook of Combinatorial Designs. CRC Press, Rockville (1996)
Djordjevic, I.B., Vasic, B.: LDPC codes for long haul optical communications based on high-girth designs. Journal of Optical Communications 24(3), 94–96 (2003)
Dotú, I., Van Hentenryck, P.: Scheduling social golfers locally. In: Barták, R., Milano, M. (eds.) CPAIOR 2005. LNCS, vol. 3524, pp. 155–167. Springer, Heidelberg (2005)
Fahle, T., Schamberger, S., Sellmann, M.: Symmetry breaking. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 93–107. Springer, Heidelberg (2001)
Franklin, M.F.: Triples of almost orthogonal 10 ×10 latin squares useful in experimental design. Ars Combinatoria 17, 141–146 (1984)
The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.3 (2002), http://www.gap-system.org
Gent, I.P., Harvey, W., Kelsey, T., Linton, S.: Generic SBDD using computational group theory. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 333–347. Springer, Heidelberg (2003)
Gent, I.P., Walsh, T., Selman, B.: CSPLib: a problem library for constraints, http://csplib.org/
Harvey, W.: Warwick’s results page for the MOLR problem, http://www.icparc.ic.ac.uk/~wh/molr
Harvey, W.: Warwick’s results page for the social golfer problem, http://www.icparc.ic.ac.uk/~wh/golf
Harvey, W.: Symmetry breaking and the social golfer problem. In: Flener, P., Pearson, J. (eds.) Proc. SymCon 2001: Symmetry in Constraints, pp. 9–16 (2001)
mathtalk-ga. Answer to Unique combinations of 4 numbers between 1 to N. Google Answers (2005), http://answers.google.com/answers/threadview?id=274891
Michel, L., Van Hentenryck, P.: A simple tabu search for warehouse location. European Journal of Operations Research 157(3), 576–591 (2004)
Mullen, G.L., Shiue, J.-S.: A simple construction for orthogonal latin rectangles. Journal of Combinatorial Mathematics and Combinatorial Computing 9, 161–166 (1991)
Prestwich, S.: Randomised backtracking for linear pseudo-boolean constraint problems. In: Jussien, N., Laburthe, F. (eds.) Proc. of the Fourth International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems (CP-AI-OR 2002), Le Croisic, France, March, 25–27, pp. 7–19 (2002)
Puget, J.-F.: Symmetry breaking revisited. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 446–461. Springer, Heidelberg (2002)
Sharma, V.K., Das, M.N.: On resolvable incomplete block designs. Austral. J. Statist. 27(3), 298–302 (1985)
Smith, B.M.: Reducing symmetry in a combinatorial design problem. In: CPAIOR 2001: Proc. of the Third International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, April 2001, pp. 351–359 (2001)
Stinson, D.R., Wei, R., Zhu, L.: New constructions for perfect hash families and related structures using combinatorial designs and codes. Journal of Combinatorial Designs 8(3), 189–200 (2000)
Wallace, M.G., Novello, S., Schimpf, J.: ECLiPSe: A platform for constraint logic programming. ICL Systems Journal 12(1), 159–200 (1997)
Wanless, I.M.: Answers to questions by Dénes on latin power sets. Europ. J. Combinatorics 22, 1009–1020 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Harvey, W., Winterer, T. (2005). Solving the MOLR and Social Golfers Problems. In: van Beek, P. (eds) Principles and Practice of Constraint Programming - CP 2005. CP 2005. Lecture Notes in Computer Science, vol 3709. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11564751_23
Download citation
DOI: https://doi.org/10.1007/11564751_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29238-8
Online ISBN: 978-3-540-32050-0
eBook Packages: Computer ScienceComputer Science (R0)