186.861 Modeling and Solving Constrained Optimization Problems
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2019S, VU, 2.0h, 3.0EC, to be held in blocked form

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise

Aim of course

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.

Subject of course

- 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

Additional information

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.

 

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Mon13:00 - 16:0006.05.2019FAV Hörsaal 3 Zemanek (Seminarraum Zemanek) Lecture
Tue12:00 - 15:0007.05.2019FAV Hörsaal 3 Zemanek (Seminarraum Zemanek) Vorlesung
Wed08:00 - 11:0008.05.2019Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Wed12:00 - 15:0008.05.2019Seminarraum FAV 01 A (Seminarraum 183/2) Übung
Thu08:00 - 12:0009.05.2019FAV Hörsaal 2 Vorlesung
Fri08:00 - 12:0010.05.2019FAV Hörsaal 2 Vorlesung
Course is held blocked

Examination modalities

Home work in the form of theoretical and practical questions, oral exam.

Course registration

Not necessary

Curricula

Literature

No lecture notes are available.

Language

English