Redundant Modeling for the QUasigroup Completion Problem.pdf

Redundant modeling for the QuasiGroup Completion Problem Iva?n Dotu?, Alvaro del Val, and Manuel Cebria?n Departamento de Ingenier??a Informa?tica Universidad Auto?noma de Madrid ivan.dotu@ii.uam.es, delval@ii.uam.es, meathook@terra.es Abstract. The Quasigroup Completion Problem (QCP) is a very chal- lenging 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 pro- gramming approaches, but could sometimes be solved by hybrid ap- proaches combining constraint programming with mixed integer pro- gramming 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 con- nected by channeling constraints [13]– with some novel aspects, as well as a new and very effective value ordering heuristic. 1 Introduction The Quasigroup Completion Problem (QCP) is a very challenging benchmark among combinatorial problems, which has been the focus of much recent inter- est in the area of constraint programming. It has a broad range of practical applications [5]; it has been put forward as a benchmark which can bridge the gap between purely random instances and highly structured problems [6]; and its structure as a multiple permutation problem [13] is common to many other important problems in constraint satisfaction. Thus, solutions that prove effec- tive on QCPs have a good chance of being useful in other problems with similar structure. In this paper, we present several techniques that together allow us to solve significantly larger QCPs than previously reported in the literature. Specifically, [5] reports that QCPs of order 40 could not be solved by pure constraint pro- gramm