Optimization

Core Course, 4+2

Basic Information

Lecturers:Parinya Chalermsook  and Andreas Wiese
Teaching assistant:Sandy Heydrich
Tutors:Syamantak Das
Davis Issac 
Anurag Pandey 
Daniel Vaz 
Lectures:Monday and Wednesday, 12:15 - 13:45 
Lecture Room:Lecture Hall 003 in E1 3 
Tutorials:Thursday, 8 - 10 (Anurag), first meeting: April 28
Thursday, 10 - 12 (Daniel), first meeting: April 28
Friday, 10 - 12 (Davis), first meeting: April 29
Friday, 14 - 16 (Syamantak), first meeting: April 29

All tutorials happen in Room 023 in E1 4.
First Meeting:20 April 2016 
Credits:9 credits
Grade formula:
Prerequisites:
Mailinglist:If you take the class, please sign up for the mailing list.
Exam:The final exam will take place on Wednesday, July 27th at 2pm in HS I in the building E 2.5. There will not be a mid-term exam. 

The re-exam is set tentatively on
September 30.

Announcement

  • For the exam, you are allowed to bring a A4 sheet of paper with handwritten notes (two-sided). You are not allowed to bring anything else, like e.g. calculators.
  • (new: June 6) A lecture note for today's lecture is posted. 
  • The first class is on April 20. 
  • We have a mailinglist. If you want to take the class please sign up for it. Note: this is non-binding and does not replace the official registration according to your study program.
  • For writing the scribe notes for a lecture, please use this template. An example of well-written scribe notes can be found here.
  • The tutorials on June 23/24 will take place in other rooms than usual:

    • Anurag's tutorial (Thu 8-10) will take place in room 029 in building E1.5 (MPI-SWS)
    • Daniel's tutorial (Thu 10-12) will take place in room 001 in building E1.7 (MMCI)
    • Davis' tutorial (Fri 10-12) will take place in room 029 in building E1.5 (MPI-SWS)

Description

This course has two components. In the first component, we provide an introduction to fundamental concepts and algorithmic methods for solving linear and integer linear programs. Linear optimization is a key subject in theoretical computer science. Moreover, it has many applications in practice. A lot of problems can be formulated as (integer) linear optimization problem. For example, combinatorial problems, such as shortest paths, maximum flows, maximum matchings in graphs, among others have a natural formulation as a linear (integer) optimization problem. In this component, we will closely follow the structure of the previous iterations of this course (see e.g. Summer 2015). In particular, the following topics will be covered. 

  • Polyhedral theory 
  • Simplex algorithm  
  • Ellipsoid method 
  • Network flows 

The second component of the course will focus on advanced topics in combinatorial optimization. These topics will partly address research trends in combinatorial optimization. This year, we plan to cover the following topics: Approximation Algorithms, Fixed Parameter Tractable (FPT) Algorithms, and Matroid Theory. 

Schedule

DateTopicReferenceHomeworkNote
20 AprIntroduction Slides, Notes, [BT] Chapters 1.1 and 2.1Assignment 1
25 AprFourier-Motzkin elimination, LPs in standard formSlides, [BT] Chapter 2.8Scribe notes
27 AprWeak dualitySlides, [BT] Chapters 4.1-4.3Assignment 2
2 MayFarkasz' lemma, strong dualitySlides, [BT] Chapter 4.7
4 MayComplementary slackness, vertices, extreme points, basic (feasible) solutionsSlides, [BT] Chapter 2.2Assignment 3Scribe notes
9 May Optimal solution at vertices, full rank assumption, extreme points of LPs in standard formSlides, [BT] Chapters 2.3, 2.5, and 2.6Scribe notes
11 MayDegenerate solutions, SIMPLEX algorithm: bases, basic matrices, feasible direction, reduced costs, optimality conditionSlides, [BT] Chapter 3.1Assignment 4
16 May-- No lecture --
18 MaySIMPLEX algorithm: move to new basis, full pivot stepSlides, [BT] Chapter 3.2Assignment 5Scribe notes
23 MaySIMPLEX algorithm: full tableau implementationSlides, [BT] Chapter 3.3

 

Scribe notes 1

Scribe notes 2

25 MaySIMPLEX algorithm: degenerate problems and finding initial basisSlides, [BT] Chapters 3.4 and 3.5Assignment 6
30 MayTotally Unimodular Matrices (TUM); Bipartite Matching
1 JuneTUM (continued); Network matrices; Max FlowAssignment 7
6 JuneMax Flow; Min Cut[note]
8 June Separation oracles; Ellipsoid Theorem; Min Cut revisited Assignment 8
13 JuneEllipsoid method: High-level description; statement of the volume reduction theorem; Ellipsoids[GLS]Scribe notes
15 JuneEllipsoid method: Proof of special cases. Assignment 9
20 JuneEllipsoid method: Final detail; Introduction to Semidefinite Programming 
22 JuneSemidefinite Programming (SDP)[GM]Assignment 10
27 JuneSDP for Maximum Independent Set and Perfect Graphs[GLS]
29 JuneSDP for Maximum Independent Set and Perfect GraphsAssignment 11
4 JulyMatching and Perfect Matching polytopesSlides, [S] Chapter 25

 

6 JulyApproximation AlgorithmsAssignment 12
11 JulyApproximation Algorithms
13 JulyApproximation Algorithms for MAXCUT: Randomized Partition; Local Search; SDP Rounding
18 JulyLP and SDP modeling for general CSPsNote. (warning: the note has not been proof-read) 
20 JulyLP and SDP modeling for general CSPs
25 JulyReview 
27 JulFinal Exam
30 SepRe-exam

Textbook

This lecture follows the textbook