Course syllabus

Jump to today

Course-PM

TDA206 / DIT206 TDA206 / DIT206 Discrete optimization lp3 VT25 (7.5 hp)

Course is offered by the department of Computer Science and Engineering

Contact details

 

Course Purpose

Introduce basic concepts of optimization,  developing both the theory and applications. In roughly the first two-thirds of the course we will cover linear programming and its applications and in the last part, we will discuss extensions to convex optimization and their applications.

Schedule

TimeEdit Links to an external site.

Course literature

We'll use this little gem available from Chalmers library:

  • [MG] Matousek, Jiri, Gärtner, Bernd, Understanding and Using Linear Programming, Springer 2007.

The last part of the course will use a bit from:

  • [GM]  Gärtner, Bernd and Matousek, Jiri, Approximation Algorithms and Semidefinite Programming

Both are available electronically from the Chalmers library.

Course Plan

Date Topic Reading
19/1 Introduction [MG, Ch. 1]  
21/1 LP  Models  {MG 2.1-2.4] 
26/1 Integer LP [MG, 3.1-3.2, pp. 144-146]
28/1 Integer LP (cont'd) [MG, 3.2]  TUM matrices and LP. Download TUM matrices and LP.
2/2 LP Rounding, Branch and Bound [MG, 3,3-3.4]  Branch and Bound Download Branch and Bound
4/2 Duality [MG 6.1-6.2]
9/2 Primal Dual Algorithm

notes on primal-dual algorithm Download notes on primal-dual algorithm

notes on duality and complemtary slackness Download notes on duality and complemtary slackness
11/2 More Duality Examples

[MG, 8.1, 8.2]

LP and game theory Download LP and game theory

Max-flow-MinCut Download Max-flow-MinCut

example network Download example network
16/2 Linear Algebra and Geometry of LP [MG 4.1-4.4]
18/2 Simplex Algorithm [MG,5.1, 5.2,5.7-5.10]
23/2 Column Generation
25/2 LP and Game Theory [MG 8.2]
2/3 LP in Robotics
4/3 LP in Industry: Boeing

Homework

  • Homework 1 won't be graded but is mandatory. You need to do it to form groups and get used to CVXPY. Links to an external site.
  • Everyone *must* form groups of 2 unless there are very exceptional circumstances. You should find a partner yourself. If you don't find a partner, we'll match you up with somebody.
  • Discussions page is for you to organize each other within groups and to ask doubts between yourselves regarding the assignments. Do not post the solution to them ! Also, these are unmonitored by the TAs, and you have to meet them at the usual allocated times to ask your doubts.
  • The assignments have the following point distribution: HW1:0p, HW2: 33p, HW3: 30p, HW4: 20p. 
Due Date Assignment Grader Consulting session
26/1 Homework 1: Intro Download Intro Not Graded None
16/2 Homework 2: LP rounding Marc Date: 16/2, Time: 3pm-4pm, Location: CSE EDIT 5128
2/3 Homework 3: Duality Download Duality Marc & Alasdair Date: 2/3, Time: 4.15pm-5.15pm, Location: CSE EDIT 4128
16/3 Homework 4: LP for Games  Download LP for Games Alasdair TBA

Learning objectives and syllabus

Learning objectives:

- identify optimization problems in various application domains,

- formulate them in exact mathematical models that capture the essentials of the real problems but are still manageable by computational methods,

- assess which problem class a given problem belongs to,

- apply linear programming, related generic methods, and additional heuristics, to computational problems,

- explain the geometry of linear programming,

- dualize optimization problems and use the dual forms to obtain bounds,

Examination form

Evaluation will be based on a score computed by the formula max(E, (E + H)/2) where

  • E is the score on the written exam at the end of the course normalized to 60 points.
  • H is the total score on all homeworks normalized to 60.

Finally grade is based on usual thresholds: for Chalmers 28 (3), 36 (4), 48 (5) and for GU 28 (G) and 48 (VG).

Homework is not compulsory but highly recommended for better learning experience and a better grade.

Exam 2024 Download Exam 2024

Exam 2023 Download Exam 2023

Link to Chalmers studieportal. Links to an external site.

Link to GU portal Links to an external site.

Course summary:

Course Summary
Date Details Due