Course syllabus for Constraint programming and applied optimization

Course syllabus adopted 2021-02-26 by Head of Programme (or corresponding).

Overview

  • Swedish nameVillkorsprogrammering och tillämpad optimering
  • CodeEEN025
  • Credits7.5 Credits
  • OwnerMPSYS
  • Education cycleSecond-cycle
  • Main field of studyAutomation and Mechatronics Engineering
  • DepartmentELECTRICAL ENGINEERING
  • GradingTH - Pass with distinction (5), Pass with credit (4), Pass (3), Fail

Course round 1

  • Teaching language English
  • Application code 35118
  • Block schedule
  • Open for exchange studentsYes

Credit distribution

0118 Examination 5 c
Grading: TH		5 c
  • 25 Okt 2021 am J
  • 04 Jan 2022 am J
  • 23 Aug 2022 pm J
0218 Laboratory 2.5 c
Grading: UG		2.5 c

In programmes

Examiner

Go to coursepage (Opens in new tab)

Eligibility

General entry requirements for Master's level (second cycle)
Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling the requirements above.

Specific entry requirements

English 6 (or by other approved means with the equivalent proficiency level)
Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling the requirements above.

Course specific prerequisites

Discrete Event Systems (or comparable knowledge acquired by other means).

Aim

The course aims to give advanced knowledge about formal methods in general and constraint programming in particular, and how these methods may be used for reasoning about and analyzing the performance of discrete event systems. Typical applications for using formal methods 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.

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 - MiniZink) and general-purpose solvers (CPLEX, Gurobi, GECODE)

Understand and implement special-purpose heuristic algorithms such as A* and Dijkstra¿s.

Content

The main objective of this course is to give the students the ability to understand and confidently use the optimization tools and techniques from Operations Research (OR) and Computer Science (CS) area, through hands-on tasks. This includes theory and practice of general optimization techniques such as mixed integer-linear programming, constraint programming, branch and bound and other discrete optimization algorithms (Dijkstra's, A*).

Organisation

The course comprises lectures, exercises, and a number of 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.

Literature

Martin Fabian, Lecture notes. Additionally scientific papers and other extra material may be handed out.

Examination including compulsory elements

Examination is based on a conventional written exam, as well as passed hand-ins.

The course examiner may assess individual students in other ways than what is stated above if there are special reasons for doing so, for example if a student has a decision from Chalmers on educational support due to disability.