Discrete Optimization

TDA206 / DIT370 • Period 3 • 2018


Point range

Chalmers grade

GU grade












Exam Live Updates and FAQs

Sample Problems

For practicing purposes, no solutions will be provided yet.

  1. Oil Fields

  2. Diet

  3. Boolean Satisfiability

The 2017 exam can be found here, and a version with solutions can be found here. Consider solving the exam first using the PDF without solutions, to counteract the “Oh yeah, that’s how I would’ve done it”-effect.

Homework solutions

Lecture Notes

Lecture notes and other material will be available here. Note that the lecture plan is tentative and subject to change. If you find any typos or errors, please feel free to send an email to John. Lecture notes contain a timestamp at the bottom of every page, so you can make sure you always have the latest revision.

  1. Convex Optimization

  2. Linear Programming (LP)

  3. Integer Linear Programming (ILP)

  4. Primal-Dual Method (PDM)

  5. TSP, Branch-and-Bound




Assistants will take turns offering consultations on Tuesdays 10:00-11:00, and by arrangement, in room EDIT 5354.

Student representatives

Brief Course Description and Goals

See also the syllabus of this course.

This course is intended to provide a basic understanding of mathematical optimization and its applications. In optimization problems, the main goal is to obtain the maximum (or minimum) value of an objective function, often under a set of additional conditions and constraints. This goal is desirable in a large variety of applications, but may be difficult to achieve. In this course, you learn how to use mathematical methods to tackle optimization problems. Examples from different application domains will be presented. In particular, optimization problems with discrete-valued parameters are discussed.

After the course you should be able to:


Furthermore, some basic knowledge of graph theory will be helpful. However, sufficient explanation for the graph-theoretic concepts will be provided when required.

Course literature

The lectures and evaluation will be based on the instructor's lecture notes, the material covered in class and the exercise sets. Therefore, you do not need to buy any book, but the lecture notes are partly based on the books below, which you can read if you are eager to know more:

Exercise sets

Each set of exercises should be submitted before the announced deadline.

We will use the MATLAB-based optimization tool CVX.

Find links to download the systems here: MATLAB, CVX.

Run cvx_setup in matlabs command window to get started with the optimization tool.

All exercises are submitted individually in the FIRE SYSTEM. Deadlines are sharp. No resubmissions or late submissions will be possible.

You are allowed and encouraged to work in groups, but you must write down your solutions yourself (no verbatim copies, as far as that’s feasible). You also have to include the names of the people that you discussed with. Groups can be different each week.

A check list for your submissions:


Grading is based on hand-in exercises (30% of the final grade) and a final take-home exam (70% of the final grade).