Constraint Programming (CP) is a declarative paradigm for problem modeling and solving that is based on the idea of describing a problem in terms of restrictions (constraints) imposed on possible solutions. CP has an interdisciplinary nature, since it relies on methods from Artificial Intelligence, Logic Programming and Operations Research. Moreover this paradigm has been identified by ACM as one of the strategic directions in computer science. The paradigm has been successfully applied to satisfaction and optimization problems in several domains, ranging from scheduling to computer graphics to computational biology.
The course will focus on both aspects of modeling and solving problems by means of CP. In particular the main aims of the course are to:
- provide the knowledge of the fundamental concepts of CP
- develop skills in modeling combinatorial problems, and
- develop skills in the solution techniques that can be applied to constraint satisfaction and constrained optimization problems, including the hybridization of CP techniques with other solution paradigms (mainly in the heuristic optimization field).
More specifically, particular emphasis will be posed on modeling constrained optimization problems by providing the student with a comprehensive set of conceptual and programming tools to effectively model and solve optimization problems through CP. Moreover during the course several case studies will be developed in order to exemplify the concepts learned.
- Constraint Programming basics: fundamental concepts, types of domains (finite domains, intervals, sets), constraints, search, branch and bound
- CP modeling techniques: global constraints, redundant constraints, symmetry elimination, special-purpose constraints (e.g., scheduling), modeling of optimization problems, problem reduction
- CP languages/libraries: GECODE, COMET, ...
- Modeling examples: n-Queens, Cryptoarithmetic, Sudoku, Scheduling, Timetabling, ...
- Basic solution methods: propagation, consistency, search
- Advanced solution methods: heuristic methods, hybrid approaches, integration with heuristic/metaheuristic techniques
- Statistical analysis of optimization algorithms
- Lab practice
ECTS-Breakdown:
20 h lectures
2 h lab practice
32 h preparation of assignments
20 h preparation for final oral exam
1 h oral exam and presentation of last assignment
------
75 h overall
The course is blocked. The lecture times will be announced.
