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

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

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
09:00 - 11:0018.01.2016 - 22.01.2016Seminarraum 384 Lecture
14:00 - 16:0018.01.2016 - 22.01.2016Sem.R. DB gelb 03 Lecture
Thu12:00 - 14:0021.01.2016Sem.R. DB gelb 03 Lecture
Modeling and Solving Constrained Optimization Problems - Single appointments
DayDateTimeLocationDescription
Mon18.01.201609:00 - 11:00Seminarraum 384 Lecture
Mon18.01.201614:00 - 16:00Sem.R. DB gelb 03 Lecture
Tue19.01.201609:00 - 11:00Seminarraum 384 Lecture
Tue19.01.201614:00 - 16:00Sem.R. DB gelb 03 Lecture
Wed20.01.201609:00 - 11:00Seminarraum 384 Lecture
Wed20.01.201614:00 - 16:00Sem.R. DB gelb 03 Lecture
Thu21.01.201609:00 - 11:00Seminarraum 384 Lecture
Thu21.01.201612:00 - 14:00Sem.R. DB gelb 03 Lecture
Fri22.01.201609:00 - 11:00Seminarraum 384 Lecture
Fri22.01.201614:00 - 16:00Sem.R. DB gelb 03 Lecture
Course is held blocked

Examination modalities

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

Course registration

Begin End Deregistration end
21.09.2015 15:00 31.01.2016 23:59 31.01.2016 23:59

Curricula

Literature

No lecture notes are available.

Previous knowledge

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

Preceding courses

Language

English