TUM – TUM – Menü
Combinatorial Optimization (MA 4502), SoSe 2016
Vorlesung

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

News

  • 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.

Content

This 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.

Schedule

Lectures

Day Time Room
Fri 12:15-13:45 MI HS 3

Exercises

Group Day Time Room Date
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.
Exercises for Group 3 on June 1st will be held in room 02.06.20.

Slides

Problem sets and solutions

Problem Set Suggested Solutions Remarks
Problem Set 1: pdf pdf
Problem Set 2: pdf pdf A typo in Exercise 2.1 has been corrected.
Problem Set 3: pdf pdf  
Problem Set 4: pdf pdf A remark has been in added in the solution of Exercise 4.4.
Problem Set 5: pdf pdf  
Problem Set 6: pdf pdf  
Problem Set 7: pdf pdf Exercise 7.4. has been been simplified.

Exam

  • First Exam: August 5th (8:30-9:30 in Interimshoersaal 1) pdf

Registration for the exam is required via TUMOnline: May 15th-June 30th. (De-registration until one week before August 5th.)

  • Second Exam: October 10th (14:30-15:30 in 1450, Willy-Messerschmitt-Zeichensaal) pdf

No auxiliary material may be used during the exams.

Literature

  • 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

Links

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Stefan Weltge
Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

News

April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.