Course-PM

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

The course is offered by the Department of Electrical Engineering

Contact details

• Martin Fabian, examiner, https://www.chalmers.se/en/staff/Pages/martin-fabian.aspx
• Sabino Roselli, teaching assistant, https://www.chalmers.se/en/staff/Pages/rsabino.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.

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 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*).

For 2019, the lectures and the hand-in assignments have been significantly re-worked. Python is now used as a programming environment (for an excellent crash-course in Python, see here). There are now three hand-in assignments, one on linear programming modeling, one on job-shop scheduling, and one on constraint programming.

Learning objectives and syllabus

Learning outcomes:

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.