TUM – TUM – Menü

Combinatorial Optimization (MA 4502), SoSe 2017
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

  • (10/16) Your grades will be online in the next days (most likely on Tuesday). You have the chance of reviewing your exam on Oct. 20th from 2-3pm in MI 02.06.020.
  • (09/05) Grades are online since yesterday. The first exam (including solutions) can be found further down on this web page; see section EXAM. You may review your exam on Sept. 7th from 3-4pm in MI 02.04.011.
  • (09/01) Your grades will be online in the next days (most likely on Monday). You have the chance of reviewing your exam on Sept. 7th from 3-4pm in MI 02.04.011.
  • (07/14) The PDFs of the two exams from last year can now be found further down on this webpage (see EXAM section).
  • (06/19) The exams are scheduled (see below). TUMOnline registration for the first exam closes on June 30th! TUMOnline registration for the second exam closes on Sept. 25th.
  • (06/19) In order to make up for some of the missed class meetings, from now on (i.e., starting this Friday, June 23) we will meet from 12:00pm (noon) till 2:00pm.
  • (05/11) There won't be lectures on May 26th (Christi Himmelfahrt) and on June 16th ("Brückentag" after Christi Himmelfahrt and Fronleichnam). They will be given at a later date (which will be announced later).
  • (05/08) The ebook version of the course text is now available here here. Please log in via your institutional credentials.
  • (04/25) The first lecture and exercise groups start in the second week of the semester (i.e.,on May 4th and May 5th, respectively). Signing up for the exercises (via TumOnline) is not mandatory, but would help you to find out which of the groups are rather full.

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.

Lectures

Day Time Room
Fri 12:00-14:00 MI HS 3

Exercises

Group Day Time Room Date
1 (Group 3 in TumOnline) Thu 12-14 00.09.022  May 4th, May 18th, June 1st, June 29th, July 13th, July 27th 
2 Thu 16-18 02.08.011  May 4th, May 18th, June 1st, June 29th, July 13th, July 27th 

Slides

  • Lecture 1: pdf
  • Lecture 2: pdf
  • Lecture 3: pdf
  • Lecture 4: pdf
  • Lecture 5: pdf
  • Lecture 6: pdf
  • Lecture 7: pdf
  • Lecture 8: pdf
  • Lecture 9: pdf
  • Lecture 10+11: pdf

Problem sets and solutions

Problem Set Suggested Solutions Remarks
Sheet 1 pdf pdf
Sheet 2 pdf pdf
Sheet 3 pdf pdf
Sheet 4 pdf pdf
Sheet 5 pdf pdf
Sheet 6 pdf pdf

Exam

No auxiliary material may be used during the exams.

  • First Exam: August 17th, 2017 (14:00-15:00 in Interimshoersaal 1)

    Registration for the exam is required via TUMOnline: May 5th-June 30th, 2017. (De-registration until August 10th.)

    Here is the first exam with solutions: pdf.

  • Second Exam: October 13th, 2017 (14:00-15:00 in Interimshoersaal 1)

    Here is the second exam with solutions: pdf.

    Registration for the exam is required via TUMOnline: Sept. 11th-Sept. 25th, 2017. (De-registration until Oct. 6th.)
  • Here are the two exams from last year: pdf, pdf.
  • Course Text

  • Lee: A First Course in Combinatorial Optimization, Cambridge Texts in Applied Mathematics, 2004
  • Several copies of this book are available in the library (they are available at the Stammgelaende, but can be ordered also from Garching). The ebook version is available here (select INSTITUTION LOGIN, select TU Muenchen, then use your mytum credentials).

    Additional 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
  • 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. Andreas S. Schulz
    Mathematics of Operations Research
    (affiliated member of M9)

    News

    March 2017
    February 2017
    Case Studies 2017 registration deadline: March 5th, 2017
    January 2017
    Case Studies 2017 pre-meeting and registration information
    January 2017
    preliminary Summer 2017 course program is available