186.861 Modeling and Solving Constrained Optimization Problems
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2019S, VU, 2.0h, 3.0EC, wird geblockt abgehalten

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung

Ziele der Lehrveranstaltung

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.

Inhalt der Lehrveranstaltung

- 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

Weitere Informationen

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.

 

Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Mo.13:00 - 16:0006.05.2019FAV Hörsaal 3 Zemanek (Seminarraum Zemanek) Vorlesung
Di.12:00 - 15:0007.05.2019FAV Hörsaal 3 Zemanek (Seminarraum Zemanek) Vorlesung
Mi.08:00 - 11:0008.05.2019Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mi.12:00 - 15:0008.05.2019Seminarraum FAV 01 A (Seminarraum 183/2) Übung
Do.08:00 - 12:0009.05.2019FAV Hörsaal 2 Vorlesung
Fr.08:00 - 12:0010.05.2019FAV Hörsaal 2 Vorlesung
LVA wird geblockt abgehalten

Leistungsnachweis

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

LVA-Anmeldung

Nicht erforderlich

Curricula

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Sprache

Englisch