Course-PM

EEN025 EEN025 Constraint programming and applied optimization lp1 HT21 (7.5 hp)

The course is offered by the Department of Electrical Engineering

Contact details

• Sabino Roselli, teaching assistant  https://www.chalmers.se/en/staff/Pages/rsabino.aspx
• Martin Fabian, lecturer and examiner https://www.chalmers.se/en/staff/Pages/martin-fabian.aspx

Course purpose

The course aims to give advanced knowledge about mathematical programming methods in general, and constraint programming in particular, and how these methods may be used for reasoning about and analyzing correctness and performance of systems. Typical applications are verification and synthesis of control functions for embedded systems, control and optimization of automated production systems, and communication systems. The course focuses on modeling, specification, simulation, verification, synthesis, and optimization.

Schedule

TimeEdit

Course literature

Martin Fabian, Lecture notes. Additionally, scientific papers, selected book chapters, and other extra material will be handed out. Different presentations of the same subject will be offered in an attempt to increase learning.

Lecture notes are available in the Files folder.

Slides for the introductory lecture are also available in the Files folder. This includes a (preliminary) lecture plan.

Course design

The course comprises lectures, exercises, and three hand-in assignments that address important parts of the course. These hand-in assignments involve modeling, specification, verification, synthesis, and optimization. The hand-in assignments may be peer-reviewed in a scientific conference type of setting.

Lecture notes are available in the Files folder.

Slides for the introductory lecture are also available in the Files folder. This includes a (preliminary) lecture plan.

Changes made since the last occasion

For 2021, essentially the same course as last year will be given, though with in-class lectures. The video lectures from 2020 are available in the Files folder.

For 2020, the lecture notes have been revised to give a more coherent presentation of the different, but similar, approaches to mathematical programming. Also, one hand-in now covers branch-and-bound search algorithms (Dijkstra's, A*).

Learning objectives and syllabus

Learning objectives:

After completion of the course the student should be able to:

• Understand the two mainstream paradigms of Mixed Integer Linear Programming (MILP), and Constraint Programming (CP).
• Explain the differences between MILP and CP, and be able to convert models from one paradigm to the other.
• Analyze and decide which paradigm is probably the better choice given different situations.
• Comfortably model optimization problems using either of the approaches.
• Use state-of-the-art modeling languages (AMPL) and general-purpose solvers (CPLEX, Gurobi, Z3)
• Understand and implement special-purpose heuristic algorithms such as A* and Dijkstra's.

Link to the syllabus on Studieportalen.

Study plan

Examination form

The examination is based on a conventional written exam (graded u, 3, 4, 5), together with passed hand-in assignments (graded pass or fail). No aids are allowed at the written exam. 

The hand-in assignments are carried out in groups of two. Hand-in deadlines are non-negotiable, but failed hand-ins can be reworked. For a final course grade, all of the assignments have to be passed.