Programmed Search in a Timetabling Problem over Finite Domains 1

Labeling is crucial in the performance of solving timetabling problems with constraint programming. Traditionally, labeling strategies are based on static and dynamic information about variables and their domains, and selecting variables and values to assign. However, the size of combinatorial problems tractable by these techniques is limited. In this paper, we present a real problem solved with constraint programming using programmed search based on the knowledge about the solution structure as a starting point for classical propagation and labeling techniques to find a feasible solution. For those problems in which solutions are close to the seed because of its structure, propagation and labeling can reach a first solution within a small response time. We apply our approach to a real timetabling problem, and we tackle its implementation with two different languages, OPL and TOY, using the constraint programming paradigm over finite domains. While OPL is a commercial, algebraic, and specific-purpose constraint programming language, TOY is a prototype of a general-purpose constraint functional logic programming language. We present the specification of the problem, its implementation with both languages, and a comparative performance analysis.