by Hana Rudová, Luděk Matyska, December 1999, 17 pages.
FIMU-RS-99-09. Available as Postscript, PDF.
One of the peculiarities of university timetabling problems lies in their huge complexity and the easy transition between complex constrained system to an over-constrained one. The Faculty of Informatics timetabling problem represents very complex scheduling and resource allocation problem as individual timetable for every student has to be scheduled with respect to course pre-enrollment informations. Variables` annotations were proposed to define preferences of variables in constraints and they serve as a source for computing variable ordering in optimization problems where the search space is too large to be fully traversed and explored. Annotations suggest a route through this space which leads quickly to at least sub-optimal solutions. Annotations may even help to find preferred solutions first as they instantiate preferred values in the domain of variables as soon as possible.
by Hana Rudová, This is an extended version of the paper accepted for presentation at ECAI-98. May 1998, 14 pages.
FIMU-RS-98-04. Available as Postscript, PDF.
Variables` annotations in over-constrained problems are proposed and described in order to express preferences for optimal solution selection using preferences on variables. The basic interpretation of variables` annotations is presented and correspondence with hierarchical CSP and possibilistic CSP is described. An algorithm for solving systems of constraints with variables` annotations using mappings to hierarchy is designed. The potential application areas are also mentioned.