DM826: Modeling and Solving Constrained Optimization Problems (5 ECTS)

STADS: 15008701

Level
Master's level course

Teaching period
The course is offered in the autumn semester.
The course is offered when needed.

Teacher responsible
Email: marco@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal. 3.kvartal

Prerequisites:
None

Academic preconditions:
The content of DM545 Linear and Integer Programming is assumed known.

Course introduction
Constraint Programming is a programming paradigm, wherein variables and constraints between variables are expressed in a declarative form. A solutions, that is, an assignment of valid values to variables, is found by means of searching and filtering. Filtering ensures by means of smart algorithms that only valid values are assigned to variables as a consequence of the application of the constraints.
The course will give to the participants knowledge  of and practical experience on the application of constraint programming. The focus will be set especially on the modelling of problems from real-life and on the use of existing solution systems. Finally, diffrerences and possible combinations of constraint programming with other techinques, such as integer linear programming and local search, will be also taken into consideration.

Expected learning outcome
At the end of the course the student is able to:

• model a problem different from the ones seen in class within the framework of constraint programming.
• argue about the different modeling choices arising from the theory behind the components of constraint programming, including global constraints, propagators, search and branching schemes.
• develop a solution prototype in a constraint programming system.
• undertake an experimental analysis and report the results.
• describe the work done in an appropriate language.

Subject overview
The course focuses on constraint programming and advanced techniques for mixed integer programming. It provides the theory behind the techniques but the focus is mainly on the fast modelling and development of solution prototypes by means of a constraint programming system. The course offers also an integrated view of constraint programming, local search, and mixed integer linear programming techniques for combinatorial optimization applications. The problems addressed include: constraint satisfaction, sport scheduling, and car sequencing.

Literature

• Meddeles ved kursets start.: .

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Mandatory assignments, granded jointly, Danish 7-mark scale, external examiner.

The exam consists of three assignments, two during the course and one at the end. The final grade will be given by a weighted average of the three.

The re-exam takes place according to the rules decided by the Study Board. It consists of a single project.

Expected working hours
The teaching method is based on three phase model.
Intro phase: 28 hours
Skills training phase: 14 hours

Educational activities Study phase: 14 hours

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.