Course syllabus

Course-PM

TDA206/DIT370 Discrete optimization HT19 (7,5hp)

Departmen of Computer Science and Engineering.

 

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 introduce basic algorithms in convex optimization and their applications.

 

Schedule

Timedit

 

Contact details

• Examiner and Lecturer: Devdatt Dubhashi (dubhashi@chalmers.se)
• Course Assistants:
  • Elisabet Lobo Vesga (elilob@chalmers.se)
  • Divya Grover (divya.grover@chalmers.se)
  • Simon Robillard (simon.robillard@chalmers.se)
• Course Representatives

  • Angelika Strandberg, angstr@stud.chalmers.se

  • David Donato, donatod@student.chalmers.se

  • Ted Eriksson   tede@student.chalmers.se  

  • Carl-Johan Heiker heikerc@student.chalmers.se    

  • Ahmet Batikan Unal    ahmetbatikan.94@gmail.com

  • Yonca Yunatci     yyunatci95@gmail.com          

Office hours

Office hours will normally take place on Wednesday and Friday afternoons.

• Every Friday - 1pm-3pm - Divya - Room 6476.
• Wednesdays 13-14, room 6472.

Course literature

For approximately the first two-thirds of the course, we'll use this little gem available from Chalmers library:

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

Supplementary notes on Duality

• [AMP] MIT notes

For the last part, we will use the following lecture notes:

• [J] Martin Jaggi (ETH Zurich) Optimization for Machine Learning

and this review article:

• [BCN] L. Bottou, F. Curtis and J. Nocedal, "Optimization Methods for Large Scale Machine Learning", SIAM Review 2018.sirev-2018.pdf

Other good lecture notes covering the same topics are:

• Moritz Hardt (UC Berkeley): Convex Optimization and Approximation
• Nisheeth Vishnoi (ETH Zurich, Yale): Algorithms for Convex Optimization

The following are good textbooks on convex optimization:

• S. Boyd and L. Vandenberghe. Convex Optimization (available for free)

• G. Calafiore, L. El Ghaoui. Optimization Models. Cambridge University Press, October 2014.

Course design

Lectures

Date	Topic	Reading
21/1	Introduction, LP models 1	[MG, Chap. 1, 2.1-2.3]
23/1	LP models 2	[MG, 2.4-2.7]
28/1	Integer LP	[MG, 3.1-3.2]
30/1	Rounding LPs	[MG, 3.2-3.4]
11/2	Basics of Convexity	[MG, Ch. 4]
13/2	Simplex	[MG, Ch. 5]
18/2	Branch and Bound	[Guest Lecture: Dag Wedelin]
20/2	LP in Industry, slides	[Guest Lecture: Mattias Grönqvist, Jeppesen]
25/2	Duality theory	[MG 6.1,6.2] [AMP, 4.1-4.5]
27/2	Primal-dual algorithm	notes
4/3	Duality Examples	[Mg 8.1, 8.5], Network Flow slides, notes
6/3	Convex Optimization/Gradient Descent	[J, Chapter 1, 2]
11/3	Projected Gradient Descent and Frank Wolf Conditional Gradient Descent	[J, Chapter 3]
13/3	Non-convex Opt: Backpropagation Backprop slides, gradient descent variants, non-convex opt.

 

Homeworks

• Homework 1 (deadline  Jan. 28.) 20 points total, 10 for each problem.
• Homework 2 (deadline Feb. 11), random graph (this is a txt file with the adjacency matrix of the graph  given row by row.)
• Homework 3 (deadline March 06)
• Homework 4 (deadline March 13 ), Readme, Data

Assignments should be submitted via Fire.

Unfortunately there will be no resubmissions and all deadlines are strict!

Python and CVXOPT

For the homework assignments, you will need to use Python and the package CVXOPT.

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 CVXOPT

The documentation provides a quick introduction to CVXOPT for linear programming.

Examination form

Evaluation will be based on

• Homework assignments (50%) Exam Date and Time : March 20, 8:30 AM. Place: M-house.
  For updated examination schedules please look under the headline “Examination schedules” to the right on the page here: https://studentportal.gu.se/english/my-studies/cse/Examination/?languageId=100001&skipSSOCheck=true
• Final written in-class exam (50%) (You may bring class notes and the textbook and notes above to the exam)

Homework is not compulsory but you can get points to contribute to your final grade which is computed as follows: add the points from all your homework (points indicated in each homework assignment), then normalize to 30. Add this to the exam points (also normalized to 30) to get a total score out of 60 which is then graded in the standard way: 3: 28, 4: 36, 5: 48 for Chalmers and G: 28, VG: 48 for GU.

 

Practice Exams:

• Exam from 2018. (Note that some problems are not relevant for this year's course e.g. 1(b), (f),(g),  4(b).
• Sample Exam with solutions.

Learning objectives and syllabus

• Develop optimization models (linear and convex) for various problems.
• Solve them using the CVX programming environment.
• Develop integer constrained optimization models and understand their relation to their LP (and other) relaxations.
• Understand LP duality and how it can be applied, in particular to develop primal-dual algorithms.

Chalmers course

GU course