409 - Discrete Optimization - Spring 2022

Course information

• Class schedule: MWF 12:30 - 1:20 in JHN175
  
• Instructor:
  Thomas Rothvoss, rothvoss@uw.edu.
  Office hour: We 10:00am - 11:00am in Padelford C440
• TAs:
  
  • Joseph David, jdavid5@uw.edu. Office hour: Tuesdays 1pm-2pm on Zoom (https://washington.zoom.us/j/92344808073)
    
  • Ravil Mussabayev, ravmus@uw.edu. Office hour: Friday 9am-10am on Zoom (https://washington.zoom.us/j/94705022020)
• Topics to be covered: computational complexity, minimum spanning trees, shortest paths, max flow problems, min cost flow problems, matchings, traveling salesman problem, integrality of polytopes.
• Prerequisites : This course requires a good working knowledge of Math 407 (Linear Programming) and Math 308 (Linear Algebra).
  
• Grading: The grade will be a convex combination of the performance in the submitted problem sets (20%; lowest scoring assignment is dropped), the mid term exam (30%) and the final exam (50%).
• Problem sets: Problem sets will be posted each Friday; due date is the following Friday 11pm via GradeScope.
  Late policy: GradeScope will accept submissions until Monday 11pm. Every student is allowed 5 late days in total. So you are allowed to submit for example 5 assignments up to 24h late or one assignment 3 days late and another one 2 days late. No prior approval required. Simply submit to GradeScope when you are done. If you submit late and you are out of late days the submission counts 0.
  Collaboration policy: You are allowed (in fact encouraged) to discuss the homework problems in groups. However, you are required to write up solutions on your own. Absolutely identical submission will be considered as a violation of this policy.
  
• Lecture notes for the course are available here
• Discussion forum: Other than in office hours, you may ask questions on course content and homework on the course discussion forum on Piazza.

Covered material

1. Monday, Mar 28, 2022: Course logistics; Section 1.1 Algorithms and Complexity; Section 1.1.1 Complexity theory and NP-hardness
2. Wednesday, Mar 30, 2022: Section 1.2 Graph Theory (undirected graphs)
3. Friday, April 1, 2022: Section 1.2 Graph Theory (directed graphs) and Section 1.3 TSP
4. Monday, April 4, 2022: Section 2 Minimum Spanning Trees (finished with Def of connected components)
5. Wednesday, April 6, 2022: Section 2 Minimum Spanning Trees (finished)
6. Friday, April 8, 2022: Shortest Paths (until beginning of correctness proof of Dijkstra's algorithm)
7. Monday, April 11: Shortest Paths (correctness proof of Dijkstra's algorithm; Moore-Bellman-Ford algorithm)
8. Wednesday, April 13: Correctness of Moore-Bellman-Ford. Detecting of negative cost cycles.
9. Friday, April 15: Finding negative cost cycle. Introduction to Network Flows.
10. Monday, April 18: Residual graphs, Ford-Fulkerson, s-t MinCut is upper bound on MaxFlow
    
11. Wednesday, April 20: Proof of MaxFlow=MinCut Theorem. Edmonds-Karp algorithm
    
12. Friday, April 22: Running time analysis of Edmonds-Karp
13. Monday, April 25: Bipartite matchings, Koenigs Theorem
14. Wednesday, April 27: Hall's Theorem. Started with linear programming chapter (polyhedra, convexity, convex hull)
    
15. Friday, April 29: Cont. linear programming
16. Monday, May 2: Farkas Lemma
17. Wednesday, May 4: MIDTERM
18. Friday, May 6: Strong Duality Theorem. Discussion of LP algorithms (skipped the section on the gradient-descent based method)
    
19. Monday, May 9: Connection of LPs to discrete optimization. Integer programs and integer hull (skipped the direct proof of the integrality of the bipartite matching LP, Lemma 48)
    
20. Wednesday, May 11: Intro to total unimodularity
21. Friday, May 13: Criterion for checking TU'ness. Application to bipartite matching
22. Monday, May 16: Application to flows. TUness of node-edge incidence matrices of directed graphs. TUness of matrices with consecutive-ones property
23. Wednesday, May 18: Finished TU chapter. Begin Branch & Bound chapter.
    
24. Friday, May 20: Finished B & B chapter. Started with matchings in general graphs
25. Monday, May 23: Augmenting paths for matchings
26. Wednesday, May 25: Contracting M-blossoms
27. Friday, May 27: Finished chapter on matchings in non-bipartite graphs. Started chapter on Knapsack problem
28. Monday, May 30: NO CLASS --- MEMORIAL DAY
29. Wednesday, June 1: A dynamic program for Knapsack. A (1-epsilon)-approximation algorithm for Knapsack
30. Friday, June 3: OFFICE HOUR IN JHN175
    

Problem sets

• Homework 1. Due: Friday, April 8, 11pm on GradeScope.
• Homework 2. Due: Friday, April 15, 11pm on GradeScope.
• Homework 3. Due: Friday, April 22, 11pm on GradeScope.
• Homework 4. Due: Friday, April 29, 11pm on GradeScope.
• Homework 5. Due: Friday, May 13, 11pm on GradeScope.
• Homework 6. Due: Friday, May 20, 11pm on GradeScope.
• Homework 7. Due: Friday, May 27, 11pm on GradeScope.
• Homework 8. Due: Friday, June 3, 11pm on GradeScope.
  

Midterm exam

• Wednesday, May 4, 2022, in class, i.e. 12:30-1:20pm in JHN 175. You may bring one sheet of notes (printed on one side or handwritten on both sides).

Final exam

• Thursday, June 9, 2022, 8:30am - 10:20am in JHN 175. You may bring one sheet of notes (printed on one side or handwritten on both sides).

Text books

• "Combinatorial Optimization" by Cook, Cunningham,Pulleyblank, Schrijver: Contains most topics that are also covered in class (plus many more). A very readable, though quite expensive book.
  
• "Computational complexity" by Arora and Barak: State of the art book for complexity theory. From the topics covered in class, this book contains only the small complexity part. A preliminary version is available for free here.

Corrections to the lecture notes (since the March 23 version)

• Chapter 1: Def spanning tree: Added that T is subgraph of G. Def directed graph: Added "i != j". Number of tours in a complete undirected graph is 1/2*(n-1)! and not (n-1)! For Stirling approximation replaced 2^.. by e^.. For TSP added n >= 3.
  
• Chapter 2: Before Lemma 3: replaced "more than 2 paths" -> "more than one path"
  
• Chapter 3: Expanded the alternative exposition of the correctness proof of Dijkstra's algorithm. Lemma 16: some "paths" are "walks" and a "cycle" is a "closed walk" . Also cleaned up what n means in this context. Added footnote to Dijkstra and MBF correctness covering the case that some node is not reachable from s.
  
• Chapter 4: Lemma 21: added ``gamma >= 0''. In Def of flow augmentation need to change f(e^-1) instead of f(e) for backward edges. Replaced the proof that augmenting flow along P indeed gives a feasible s-t flow. Removed the (t,a) edge in the example. In correctness proof of Edmonds-Karp, one index i' changed to i.
• Chapter 5. Replace $x = A_I^{-1}x$ by $x = A_I^{-1}b_I$ in description of simplex. Cleaned up other linear algebra expressions in the simplex section. Replaced "circuit" by "cycle". Fixed the example 2-dim. LP.
• Chapter 6. Added detail in TU'ness of matrices with consecutive-ones property. Cor 56 b) label should be c)
  
• Chapter 7. First constraint in B & B example should be -4x_1 + 6x_2 <= 9 instead of -x_1 + 6x_2 <= 9
• Chapter 8. Added condition to Def of M-flower. Some smaller tweaks throughout the chapter. In Lemma 72+73 added that B should be M-blossom (was only implicit before). Expanded proof of Lemma 73 and added two figures.