Me - Constraint Satisfaction with Preferences



- Hana Rudova, Constraint Satisfaction with Preferences.
Ph.D. Thesis, Faculty of Informatics, Masaryk University, 2001.

- Text of the Thesis in PDF with hyper-references or in PostScript

- Summary of the Thesis (also PDF and PostScript)

- BibTeX

- Contents

- Description of the main approaches to deal with preferences in constraint problems
- Constraint hierarchies
- Constraints with variables' annotations
- Constraint-based timetabling

- Abstract

Various types of preferences were proposed to find solutions of over-constrained problems, optimization problems, problems with uncertainties, or ill-defined problems where some kind of softness have to be involved to get feasible solutions. Studying these problems from the point of view of constraint satisfaction, we concentrate on description of constraint satisfaction problems (CSPs) with preferences. An original contribution consists in assigning preferences to particular variables in constraint which lead to study of constraints with the so called variables' annotations. Local annotations of variables in constraints are introduced as a method for computing static and dynamic variable ordering in CSPs with preferences. Interpretations based on existing frameworks with preferences, on fuzzy CSP and constraint hierarchies, use fuzzy and hierarchical annotations. Our intent is also devoted to constraint hierarchies (CHs) having several preference levels of constraints and defining solutions via the so called comparators. New ordered-better and lexicographic-better comparators are proposed and their comparison with traditional comparators of CHs is discussed. Subsequently an algorithm for solving CH with ordered-better comparator is presented. Certain comparators of CHs are introduced as instances of general framework for CSPs with preferences, semiring-based CSP, and classified into complexity classes with help of a new equivalence for semiring-based CSPs. It is also shown that any correspondence does not exist for remaining comparators. Practical application of constraint-based approaches with preferences is described for timetabling problem having special emphasis on variables' annotations. Concentration is devoted to construction of student-oriented schedules representing problem which still was not solved via constraint programming methodology. Proposed methods are applied for solving Faculty of Informatics timetabling problem including construction of individual student schedules for more than 1000 students. Achieved results are compared with other solution methods and solutions of comparable problem instances.

Hana Rudova(hanka@fi.muni.cz), April, 2001.