Course syllabus

Jump to today

Exam 2022

Course-PM

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

Course is offered by the department of Computer Science and Engineering

Contact details

Course purpose

The goal of the course is to 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

  • Lectures:  Monday, Wednesday, 10-12 , in hybrid format, in the lecture room and via Zoom:
  • Zoom link: Join from PC, Mac, Linux, iOS or Android: https://chalmers.zoom.us/j/66652245390
    Password: 620189

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.

The following are good textbooks on convex optimization:

We will use the CVXPY (Links to an external site.) programming framework.

Lectures

Zoom link: Join from PC, Mac, Linux, iOS or Android: https://chalmers.zoom.us/j/66652245390
Password: 620189

Date Topics Reading
17/1 Introduction [MG, Chap. 1]
19/1 LP Models [MG, 2.1 - 2.4]
24/1 Integer LP [MG, 3.1-3.2][MG, pp. 144-146]
26/1 Integer LP (cont'd) [MG, 3.2-3.4] 
31/1 LP Rounding, Branch&Bound [MG 2.7, 3.1] Branch and Bound
2/2 Duality [MG 6.1,6.2] 
7/2 Primal-Dual Algorithm notes
9/2 More Duality Examples [MG 8.1-8.2] notes
14/2 Duality examples concluded  
16/2 Linear Algebra and Geometry of LP [MG 4.1-4.4]
21/2 Simplex Algorithm [MG 5.1-5.10]
23/2 MAXCUT and SDP [GM, Ch.1, 2.1-2.4]
7/3

Guest Lecture: Can LP solve TSP?

Jonah Brown-Cohen
9/3 Guest Lecture: Optimization in Industry, Mattias Grönkvist, Jeppesen

 

Homework

  • Homework 1 won't be graded but is mandatory. You need to do it to form groups and get used to CVXPY.
  • 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.
  • Homework 2 consultation - 4/2 12-13 Zoom link: https://chalmers.zoom.us/j/68920279391
        Password: 641977
  • Homework 2 consultation - 11/2 12-13 Zoom link: https://chalmers.zoom.us/j/67341210635
        Password: 395102
  • Homework 3 consultation - 25/2 12-13 Zoom link: https://chalmers.zoom.us/j/62484507133
        Password: 471881
  • Homework 4 consultation - 4/3 12-13 Zoom link: https://chalmers.zoom.us/j/69781554601
        Password: 020525

 

Due Date Assignment Grader
24/1 Homework 1: Intro Not graded
14/2 Homework 2: LP rounding, graph.txt Adam
28/2 Homework 3: Duality , sol Adam & Divya
7/3 Homework 4: SDP , sol Divya

Submissions in the Assignments Section.

Python and CVXPY

Installation

The required software should be installed on machines in the EDIT building. If you wish to install it on your own machine, follow these instructions . Make sure that your installation also includes the extension GLPK, which is needed for integer linear programming.

Using CVXPY

We will use CVXPY for programming exercises. The documentation provides a Tutorial and many Examples that can help you understand its API.

Demo Jupyter notebook: click here

Using MathJax for Formatting your solutions in Jupyter notebook itself: click here

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,

- work with the scientific literature in the field.

Link to the syllabus on Studieportalen.

Study plan

If the course is a joint course (Chalmers and Göteborgs Universitet) you should link to both syllabus (Chalmers and Göteborgs Universitet).

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.

Sample exams with solution sketches:

 

 

Course summary:

Date Details Due