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
| Date | Topic | Reference | Homework | Note |
|---|---|---|---|---|
| 20 Apr | Introduction | Slides, Notes, [BT] Chapters 1.1 and 2.1 | Assignment 1 | |
| 25 Apr | Fourier-Motzkin elimination, LPs in standard form | Slides, [BT] Chapter 2.8 | Scribe notes | |
| 27 Apr | Weak duality | Slides, [BT] Chapters 4.1-4.3 | Assignment 2 | |
| 2 May | Farkasz' lemma, strong duality | Slides, [BT] Chapter 4.7 | ||
| 4 May | Complementary slackness, vertices, extreme points, basic (feasible) solutions | Slides, [BT] Chapter 2.2 | Assignment 3 | Scribe notes |
| 9 May | Optimal solution at vertices, full rank assumption, extreme points of LPs in standard form | Slides, [BT] Chapters 2.3, 2.5, and 2.6 | Scribe notes | |
| 11 May | Degenerate solutions, SIMPLEX algorithm: bases, basic matrices, feasible direction, reduced costs, optimality condition | Slides, [BT] Chapter 3.1 | Assignment 4 | |
| 16 May | -- No lecture -- | |||
| 18 May | SIMPLEX algorithm: move to new basis, full pivot step | Slides, [BT] Chapter 3.2 | Assignment 5 | Scribe notes |
| 23 May | SIMPLEX algorithm: full tableau implementation | Slides, [BT] Chapter 3.3 |
| |
| 25 May | SIMPLEX algorithm: degenerate problems and finding initial basis | Slides, [BT] Chapters 3.4 and 3.5 | Assignment 6 | |
| 30 May | Totally Unimodular Matrices (TUM); Bipartite Matching | |||
| 1 June | TUM (continued); Network matrices; Max Flow | Assignment 7 | ||
| 6 June | Max Flow; Min Cut | [note] | ||
| 8 June | Separation oracles; Ellipsoid Theorem; Min Cut revisited | Assignment 8 | ||
| 13 June | Ellipsoid method: High-level description; statement of the volume reduction theorem; Ellipsoids | [GLS] | Scribe notes | |
| 15 June | Ellipsoid method: Proof of special cases. | Assignment 9 | ||
| 20 June | Ellipsoid method: Final detail; Introduction to Semidefinite Programming | |||
| 22 June | Semidefinite Programming (SDP) | [GM] | Assignment 10 | |
| 27 June | SDP for Maximum Independent Set and Perfect Graphs | [GLS] | ||
| 29 June | SDP for Maximum Independent Set and Perfect Graphs | Assignment 11 | ||
| 4 July | Matching and Perfect Matching polytopes | Slides, [S] Chapter 25 |
| |
| 6 July | Approximation Algorithms | Assignment 12 | ||
| 11 July | Approximation Algorithms | |||
| 13 July | Approximation Algorithms for MAXCUT: Randomized Partition; Local Search; SDP Rounding | |||
| 18 July | LP and SDP modeling for general CSPs | Note. (warning: the note has not been proof-read) | ||
| 20 July | LP and SDP modeling for general CSPs | |||
| 25 July | Review | |||
| 27 Jul | Final Exam | |||
| 30 Sep | Re-exam |
Textbook
This lecture follows the textbook
- [BT] Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis (available in the campus library for computer science)