|Lectures:||Prof. Dr. Andreas Schulz|
|Tutorial Management:||Dr. Andreas Alpers|
|Tutorials:||Dr. Andreas Alpers|
|News||Content||Schedule||Slides||Problem sets and solutions||Exam||Literature||Links|
- October 19th: The grades are now official. Exam solutions have been uploaded (see below). This is the last entry for this course. All the best, your combinatorial optimization team.
- October 12th: Your grade for Exam 2 is available on TUM Online. Exam review (Klausureinsicht) is scheduled for Tuesday 18th, 15:00-16:00 in 02.04.039.
- August 17th: The grades are now official.
- August 10th: Your grade for Exam 1 is available on TUM Online. Exam review (Klausureinsicht) is scheduled for Wednesday 17th, 14:00-15:00 in 02.04.011.
- July 31st: Lecture Notes 11 (slides8.pdf) have been updated.
- July 17th: There is an extra lecture on July 25th, at 1pm in HS 3.
- July 17th: Prof. Schulz holds a seminar on Advanced Topics in Combinatorial Optimization in the coming semster; see here for more information. Partcipants need to enroll between July 18 and July 24 (see here for enrollment details).
- May 21st: There will be no lectures on May 27th (they will be given at a later date).
- April 29th: There will be no lectures on May 6th. Classes for exercise group 2 will be moved from May 5th to May 12.
- April 25th: Updated links; see bottom of this webpage.
ContentThis course covers important and modern aspects of combinatorial, discrete and integer optimization that are not considered elsewhere in the curriculum. Topics include the equivalence of separation and optimization, primal separation, augmentation algorithms and local search, the strength of formulations, extended formulations, test sets and Graver bases, mixed-integer programming, robust optimization, and submodular functions.
|Fri||12:15-13:45||MI HS 3|
|Group 1||Wed||2:00-3:30 pm||02.08.011||20.4., 4.5., 18.5., 1.6., 15.6., 29.6., 13.7.|
|Group 2||Thu||4:00-5:30 pm||02.08.011||21.4., 12.5., 19.5., 2.6., 16.6., 30.6., 14.7.|
|Group 3||Wed||4:00-5:30 pm||03.06.011||27.4., 4.5., 18.5., 1.6., 15.6., 29.6., 13.7.|
- Pulleyblank's Top 10 List:
- Lecture Notes 1:
- Lecture Notes 2:
- Lecture Notes 3:
- Lecture Notes 4: From Michel Goemans (MIT), further reading Link 1 and Link 2
- Lecture Notes 5: Recap of ellipsoid method as well as polarity and equivalence of optimization and separation, Separation of odd cycle inequalities for the stable set polytope , Extended polymatroids and submodular function minimization (Chapter 10 in [Grötschel, Lovasz, Schrijver], especially Pages 304-311)
- Lecture Notes 6: Slides from Cliff Stein (Columbia)
- Lecture Notes 7: A.S. Schulz, On the relative complexity of 15 problems related to 0/1-integer programming, Chapter 19 in W.J. Cook, L. Lovász, J. Vygen (eds.): Research Trends in Combinatorial Optimization, Springer, 2009, pp. 399-428
- Lecture Notes 8:
- Lecture Notes 9: , Additional lecture notes from Michael Ritter
- Lecture Notes 10:
- Lecture Notes 11:
- Lecture Notes 12:
Problem sets and solutions
- Papadimitriou, Steiglitz: Combinatorial Optimization, Dover, 1998
- Korte, Vygen: Combinatorial Optimization, Springer, 2002
- Schrijver: Combinatorial Optimization (volumes A-C), Springer, 2003
- Nemhauser, Wolsey: Integer and Combinatorial Optimization, Wiley, 1999
- Cook, Cunningham, Pulleyblank, Schrijver: Combinatorial Optimization, Wiley, 1998
- Wolsey: Integer Programming, Wiley, 1998
- Gritzmann: Grundlagen der Mathematischen Optimierung, Springer, 2013
- Grötschel, Lovasz, Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer, 1993