Constraint modelling

• Thesis title in Czech: Constraint modelling
• Thesis title in English: Constraint modelling
• Academic year of topic announcement: 2006/2007
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Supervisor: prof. RNDr. Roman Barták, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 08.11.2006
• Date of assignment: 08.11.2006
• Date and time of defence: 10.09.2007 00:00
• Date of electronic submission: 10.09.2007
• Date of proceeded defence: 10.09.2007
• Opponents: doc. RNDr. Pavel Surynek, Ph.D.

Guidelines

Student will first familiarize himself with techniques of constraint satisfaction. Then he will study various modelling approaches for description of problems as constraint satisfaction problems, in particular, he will focus his attention on comparing performance of different constraint models. In the thesis, he will survey the available modelling techniques and compare their advantages and disadvantages.

References

1) B. Smith. Tutorial Modelling, CP Summer School, 2005.
http://www.math.unipd.it/~frossi/cp-school/

2) R. Dechter: Constraint Processing, Morgan Kaufmann Publishers (Elsevier Science), 2003

3) R. Barták: Effective Modeling with Constraints. In Applications of Declarative Programming and Knowledge Management. Springer Verlag, LNCS/LNAI 3392, 2005.

4) K. Marriott, P. Stuckey: Programming with Constraints: An Introduction, The MIT Press, 1998

Preliminary scope of work

Constraint modelling is a non-trivial task requiring some deeper knowledge of how constraint solvers work. Currently, there exists a set of modelling rules-of-thumb, but there is no formal framework recommending how to model a particular problem. The thesis gives an overview of existing modelling techniques including practical examples demonstrating their usage.