Martin Kot - Personal webpage

Constraint processing - school year 2015/16

General facts

Guarantee:
Number of credits:	4
Hours:	2/2/0/0
Completition:	Credit
Official web-page:	http://www.cs.vsb.cz/kot/ARUO/
Lecturers:
Exercisers:

Division of points

Credit:

60pts - homework
40pts - term written test
Condition for accreditation is to obtain at least 31 points from homework and at least 20 points from test

Annotation
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).

Annotation

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).

Time table

7:15

8:00

8:45

9:00

9:45

10:30

10:45

11:30

12:15

12:30

13:15

14:00

14:15

15:00

15:45

16:00

16:45

17:30

17:45

18:30

19:15

pondělí

úterý

středa

čtvrtek

EB207

Kot M.

EB207

Kot M.

pátek

sobota

Lectures

Examples of practical problems with constraints and outline of general solving methods. Exact formulation of problems, illustrated on example of an assignment of radio frequencies; choice of unknowns and constraints on them.
Structure of space of potential solutions Constraint propagation methods.
General search strategies for the space of potential solutions.
Scheduling problem (lessons, work shifts,...). Application of selected methods.
Formulation of logical circuits diagnosis problem and some other problems that can be reduced to SAT (satisfiability of boolean formulas) SAT-solvers.
Methods used in SAT-solvers.
Stochastic search strategies.
Combinatorial optimization. Multicommodity flows, logistic problems.
Integer linear constraints and specific solution methods.
Planning (assigning tasks to processors).
Outline of some advanced topics (decomposition methods, probabilistic networks,...).
Hybrid methods.
Summary, review

Study literature

R. Dechter: Constraint processing, Morgan Kaufmann, 2003

Literature is not obligatory. All you need to obtain a credit will be said on lectures and tutorials.