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

2015W, 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 scheduled for the first two weeks of the 2014 winter term. The lecture times will be announced.

Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
09:00 - 11:0018.01.2016 - 22.01.2016Seminarraum 384 Vorlesung
14:00 - 16:0018.01.2016 - 22.01.2016Sem.R. DB gelb 03 Vorlesung
Do.12:00 - 14:0021.01.2016Sem.R. DB gelb 03 Vorlesung
Modeling and Solving Constrained Optimization Problems - Einzeltermine
TagDatumZeitOrtBeschreibung
Mo.18.01.201609:00 - 11:00Seminarraum 384 Vorlesung
Mo.18.01.201614:00 - 16:00Sem.R. DB gelb 03 Vorlesung
Di.19.01.201609:00 - 11:00Seminarraum 384 Vorlesung
Di.19.01.201614:00 - 16:00Sem.R. DB gelb 03 Vorlesung
Mi.20.01.201609:00 - 11:00Seminarraum 384 Vorlesung
Mi.20.01.201614:00 - 16:00Sem.R. DB gelb 03 Vorlesung
Do.21.01.201609:00 - 11:00Seminarraum 384 Vorlesung
Do.21.01.201612:00 - 14:00Sem.R. DB gelb 03 Vorlesung
Fr.22.01.201609:00 - 11:00Seminarraum 384 Vorlesung
Fr.22.01.201614:00 - 16:00Sem.R. DB gelb 03 Vorlesung
LVA wird geblockt abgehalten

Leistungsnachweis

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

LVA-Anmeldung

Von Bis Abmeldung bis
21.09.2015 15:00 31.01.2016 23:59 31.01.2016 23:59

Curricula

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Vorkenntnisse

  • knowledge of algorithms and data structures
  • not mandatory, but useful, knowledge of object-oriented programming languages (C++, Java)

Vorausgehende Lehrveranstaltungen

Sprache

Englisch