460-4089/02 – Constraint Processing (ARUO)

Gurantor departmentDepartment of Computer ScienceCredits4
Subject guarantorIng. Martin Kot, Ph.D.Subject version guarantorIng. Martin Kot, Ph.D.
Study levelundergraduate or graduateRequirementChoice-compulsory
Year1Semesterwinter
Study languageEnglish
Year of introduction2015/2016Year of cancellation
Intended for the facultiesFEIIntended for study typesMaster, Follow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
KOT06 Ing. Martin Kot, Ph.D.
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Graded credit 2+2
Combined Graded credit 0+19

Subject aims expressed by acquired skills and competences

Student after successful completion of this subject: - understands basic notions from the area "constraint processing" - can classify practical problems from this area - is able to find relevant unknowns for practical problem and precisely formulate corresponding constraints - has an overview of general solution methods - has an overview of available software tools for solving problems with constraints - has some practice in solving practical problems using some of those tools

Teaching methods

Lectures
Tutorials

Summary

Many practical problems share the following feature - a desirable solution must satisfy a lot of constraints resulting from reality (a timetable for teaching, a schedule for working on something, an assignment of radio frequencies, ...). In last several decades, an area called "constraint processing" has been developed, where general forms of description of such constraints are examined and where general methods for solving such problems are studied. Instances of these methods are used successfully in many different areas, from molecular biology, through computer graphics, natural language processing, to, for example, design of logic circuits. The aim of this course is to introduce students to possible forms of a description of constraints and some selected methods for finding solutions satisfying these constraints, and to illustrate their use on some practical problems. Students will also try to solve such problems in practice in tutorials and in a semestral project, using freely available software libraries and tools (as for example "SAT-solvers", i.e., solvers for satisfiability of boolean formulas).

Compulsory literature:

Rina Dechter: Constraint Processing, Morgan Kaufmann, 2003

Recommended literature:

- Krzysztof Apt: Principles of Constraint Programming, Cambridge University Press, 2003. - Malik Ghallab, Dana Nau, Paolo Traverso: Automated Planning: Theory & Practice, Morgan Kaufmann, 2004. - Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998. - Alexander Schrijver: Combinatorial Optimization (3 volume, A,B, & C), Springer, 2003. - Daniel Kroening, Ofer Strichman: Decision Procedures: An Algorithmic Point of View, Springer, 2008.

Way of continuous check of knowledge in the course of semester

Solving tasks for each tutorial. Elaborating project, finished by written report. Final test.

E-learning

Electronic materials underlying the lectures and tutorials, pointers to software tools, and futher information are accessible from the course web-page.

Další požadavky na studenta

No additional requirements are placed on the student.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: --------- 1. Examples of practical problems with constraints and outline of general solving methods. Exact formulation of problems shown on Huffman-Clowes scene labeling 2. Constraint networks and graph representations, special forms of networks. 3. Constraint propagation (arc consistency, global constraints), relevant algorithms 4. Solution of problems using backtracking, algorithms improving forward phase of backtracking 5. Algorithms improving backward phase of backtracking 6. Problem SAT, its NP-completness, using SAT for solving problems with constraints 7. Variants of SAT with polynomial-time solution, relevant algorithms 8. Solutions for general problem SAT, algorithm DPLL, stochastic algorithms,... 9. Optimization problems, the use of backtracking (Branch and Bound), bucket elimination techniques 10. The use of probabilistic networks (medical diagnosis example) 11. Planning, scheduling 12. Aproximation algorithms (traveling salesman problem) Outline of tutorials: --------------------- 1. Precise formulation of problems. Introductory session with Gecode tool (constraint solver). 2. Gecode - construction of a model of a problem 3. Gecode - the use of different search methods implemented in this tool 4. Formulation of a problem in a form of an input for a SAT solver. Introductory session with MiniSAT - a simple SAT solver. 5. Solution of practical problems with MiniSAT. 6. UBCSAT - stochastic SAT solver 7. The use of JAVA library Sat4j for SAT solving in own programs 8. Sat4j as a standalone SAT solver, other available SAT solvers, their commonalities and differences 9.-10. Other SW tools for solving problems with constraints 11.-12. Consultation of projects 13. A written test

Conditions for subject completion

Full-time form (validity from: 2015/2016 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Graded credit Graded credit 100 (100) 51
        Practical solution of a problem with constraints Other task type 60  31
        Test Written test 40  20
Mandatory attendence parzicipation: 80% attendance at the exercises

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 1 Choice-compulsory study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 1 Choice-compulsory study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 1 Choice-compulsory study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 1 Choice-compulsory study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 1 Choice-compulsory study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 1 Choice-compulsory study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 1 Choice-compulsory study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 1 Choice-compulsory study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 1 Choice-compulsory study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 1 Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner