Abstract
The Quasigroup Completion Problem (QCP) is a very challenging benchmark among combinatorial problems, and the focus of much recent interest in the area of constraint programming. [5] reports that QCPs of order 40 could not be solved by pure constraint programming approaches, but could sometimes be solved by hybrid approaches combining constraint programming with mixed integer programming techniques from operations research. In this paper, we show that the pure constraint satisfaction approach can solve many problems of order 45 in the transition phase, which corresponds to the peak of difficulty. Our solution combines a number of known ideas –the use of redundant modeling [3] with primal and dual models of the problem connected by channeling constraints [13] – with some novel aspects, as well as a new and very effective value ordering heuristic.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Bessiere, C., Regin, J.C.: Mac and combined heuristics: two reason to forsake FC (and CBJ?) on hard problems. In: 2nd Int. Conf. on Principles and Practice of Constraint Programming pp. 61–75 (1996)
Bitner, J., Reingold, E.M.: Backtrack programming techniques. Communications of the ACM 18, 651–655
Cheng, B.M.W., Lee, J.H.M., Wu, J.C.K.: Speeding up constraint propagation by redundant modeling. In: 2nd Int. Conf. on Principles and Practice of Constraint Programming, pp. 91–103 (1996)
Colbourn, C.: The complexity of completing partial latin squares. Discrete applied Mathematics
Gomes, C., Shmoys, D.B.: The promise of LP to Boost CSP Techniques for Combinatorial Problems. In: CP-AI-OR 2002, pp. 291–305 (2002)
Gomes, C., Shmoys, D.B.: Completing Quasigroups or Latin Squares: A Structured Graph Coloring Proble. In: Proc. Computational Symposium on Graph Coloring and Extensions (2002)
Gomes, C., Selman, B., Kautz, H.: Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. Journal of Automated Reasoning 24, 67–100 (2000)
Regin, J.-C.: A filtering algorithm for constraints of difference in CSPs. In: Proc. AAAI 1994, pp. 362–367 (1994)
Sergiou, K., Walsh, T.: The difference all-difference makes. In: Proc. IJCAI 1999 (1999)
Slaney, J., Fujita, M., Stickel, M.: Automated reasoning and exhaustive search: Quasigroup Existence Problems. Computers and Mathematics with Applications 29, 115–132 (1995)
Barbara, M.S.: Modeling a Permutation Problem. In: Proceedings of ECAI 2000 Workshop on Modeling and Solving Problems with Constraints (2000)
van Beek, P., Chen, X.: CPlan: A Constraint Programming Approach to Planning. In: AAAI 1999, pp. 585–590 (1999)
Walsh, T.: Permutation Problems and Channeling Constraints. In: Nieuwenhuis, R., Voronkov, A. (eds.) LPAR 2001. LNCS (LNAI), vol. 2250, p. 377. Springer, Heidelberg (2001)
Smith, B.M.: Dual Models in Constraint Programming. School Computing Research Report 2001.02, University of Leeds (January 2001)
Cheng, B.M.W., et al.: Increasing Constraint Propagation by Redundant Modeling: an Experience Report. In: Constraints, pp. 167–192. Kluwer Academic Publishers, Dordrecht (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dotú, I., del Val, A., Cebrián, M. (2003). Redundant Modeling for the QuasiGroup Completion Problem. In: Rossi, F. (eds) Principles and Practice of Constraint Programming – CP 2003. CP 2003. Lecture Notes in Computer Science, vol 2833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45193-8_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-45193-8_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20202-8
Online ISBN: 978-3-540-45193-8
eBook Packages: Springer Book Archive