Channeling Constraints and Value Ordering in the QuasiGroup Completion Problem

Abstract

The Quasigroup Completion Problem (QCP) is a very challenging benchmark among combinatorial problems, and a focus of much recent interest in the area of constraint programming. It has numerous practical applications [Gomes et al., 2002]; it has been put forward as a benchmark which can bridge the gap between purely random instances and highly structured problems [Gomes et al., 2002]; and its structure as a multiple permutation problem [Walsh, 2001] is common to many other important problems in constraint satisfaction. [Gomes et al., 2002] 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 [Cheng et al., 1996] with primal and dual models of the problem connected by channeling constraints [Walsh, 2001]– with some novel aspects, as well as a new and very effective value ordering heuristic.