Discrete Optimization (MA 3502)

Vorlesung

Lectures: Prof. Dr. Peter Gritzmann
Tutorial management: Dr. Michael Ritter
Tutorials: Viviana Ghiglione, Dr. Michael Ritter

News Schedule Problem sets and solutions Students' Exercises Literature FAQ

News

  • March 09, 2015: Registration for the second examination date is now possible through TUM-Online. Please register no later than March 21st, 2015 if you want to take part in the exam. Please note that you will not be registered automatically, even you failed the first exam.
  • January 20, 2015: Unfortunately, problem 7.1 d) on sheet 7 contained a little type, the basis was wrong. An updated version has now been uploaded.
  • January 12, 2015: The information on the examination rooms has been updated. This is preliminary information, be sure to check back shortly before the exam to get the most current information on the examination rooms.
  • January 07, 2015: A friendly reminder: Please do not forget to register for the exam - you will not be able to take the exam without prior registration! Exam registration closes on January 10th, so please register until that date.
  • December 23, 2014: For those of you who could not attend today's lecture: The lecture notes and an updated version of the German lecture notes has just been posted. The Discrete Optimization Team wishes all students a merry christmas and happy holidays.
  • November 11, 2014: Today's lecture will not take place.
  • December 11, 2014: The tutorial class 4 originally scheduled for Thursday, December 11th, has to be reschuled to Thursday, December 18th. All other classes will take place as planned. TUM-Online already has the correct dates.
  • November 10, 2014: Exam registration starts on Monday, November 10th and ends on January 10th. Please make sure to register for the exam during that time. Without prior registration exam participation will not be possible!
  • October 14, 2014: The lecture today will not take place.
  • September 25, 2014: The first class will take place on Tuesday, October 7, 2014 in room MI HS 3 at 16:00. We will start by giving you some details on tutorials and organization. Registration for the tutorials will start right after the first lecture, details on the tutorial classes will be available within the coming days.

Schedule

Lectures

Day Time Room Lecturer
Tue 16:00-17:45 MI HS3 P. Gritzmann

Tutorial Classes

Group Day Time Room Tutor Dates
Group 1 Tue 12:05 - 13:50 MI 02.04.011 Viviana Ghiglione Oct 14, Oct 28, Nov 11, Nov 25, Dec 9, Dec 23, Jan 20
Group 2 Tue 12:15 - 14:00 MI 02.04.011 Viviana Ghiglione Oct 21, Nov 4, Nov 18, Dec 2, Dec 16, Jan 13, Jan 27
Group 3 Wed 16:05 - 17:50 GHB 0.01.05 (Seminarraum 2) Viviana Ghiglione Oct 15, Oct 29, Nov 12, Nov 26, Dec 10, Jan 7, Jan 21
Group 4 Thu 12:15 - 14:00 MW 1701 Michael Ritter Oct 16, Oct 30, Nov 13, Nov 27, Dec 11 Dec 18, Jan 8, Jan 22

For participation in the tutorial classes, registration on TUM-Online is mandatory. Registration starts on Tuesday, October 7th at 19:00 and is open until Monday, October 13th. Please register for one of the above groups until that date.

Lecture notes

download description
pdf introductory slides
pdf additional lecture notes in German (Jan 28, 2015)
pdf lecture notes for Oct 07, 2014
pdf lecture notes for Oct 21, 2014
pdf lecture notes for Oct 28, 2014
pdf lecture notes for Nov 04, 2014
pdf lecture notes for Nov 18, 2014
pdf lecture notes for Nov 25, 2014
pdf lecture notes for Dec 02, 2014
pdf lecture notes for Dec 09, 2014
pdf lecture notes for Dec 16, 2014
pdf lecture notes for Dec 23, 2014
pdf lecture notes for Jan 13, 2015
zip java applet to visualize Gomory Cuts (see included "readme.pdf" for instructions)
pdf lecture notes for Jan 20, 2015
pdf lecture notes for Jan 27, 2015

Problem sets and solutions

Problem Set Suggested Solutions remarks
Sheet 1: pdf suggested solutions 1 UPDATED
Sheet 2: pdf suggested solutions 2  
Sheet 3: pdf suggested solutions 3  
Sheet 4: pdf suggested solutions 4  
Sheet 5: pdf suggested solutions 5  
Sheet 6: pdf suggested solutions  
Sheet 7: pdf suggested solutions  

Students Exercises proposed in the Tutorials

Date and Group Authors Link and Comments
Nov, 11th, Group 1 F. Ackermann, M. Haslbeck Modelling
Oct, 30th, Group 4 H. Bliemel, C. Dick, J. Lohmaier LP and ILP optimality
Nov, 13th, Group 4 R. Haas, A. Klapproth, T. Kuppelwieser Diophantine equations
Nov, 25th, Group 1 D. Bruckner, A. Schaberl ILP with Diophantine System
Nov, 27th, Group 4 A. Schindler, M. Sölch Computational Complexity of ILPs
Dec, 2nd, Group 2 M. Eder, C. Gallner Optimal solutions of related LPs
Dec, 9th, Group 1 A. Schneider, C. Waldmann Unimodularity and Totally Unimodularity
Dec, 16th, Group 2 C. Wolf True/False on Unimodular and Totally Unimodular Matrices
Dec, 18th, Group 4 A. Kirschbaum, I. Garnelo Abellanas Unimodularity and the Integer Hull
Jan, 08th, Group 4 M. Kuchlbauer, M. Engesser Hilbert Bases
Jan, 20th, Group 1 K. Kessler, C. Waldmann Hilbert Bases and Gomory Cuts
Jan, 22nd, Group 4 G. Cordes, C. Stricker Gomory Cuts

Please note that these problems and the suggested solutions are not reviewed nor edited by teaching staff.

Exam

Important Information

  • There will be a written exam with a duration of 60 minutes for this lecture.
  • The exam will be closed book, nothing beyond writing utensils will be allowed for the exam. Please do not use red or green pens nor a pencil.
  • All topics covered in either the lecture or the exercise classes are relevant for the exam.
  • Registration via TUMOnline is mandatory for participation in the exam (registration for the lecture and/or the exercise classes is not sufficient)! Please do not forget to register until that date - you will not be allowed to take the exam without prior registration on TUM-Online.
  • The dates and times for the exam posted below are preliminary and subject to change. Please consult TUM-Online for the official dates.
  • Please make sure to be in the examination room at least 10 minutes prior to the scheduled starting time.
  • Bring a photo ID (passport or drivers license) and your student ID. We will check the IDs during the exam.
  • In case you have been granted any special regulations for your examination, please make sure to inform us (m..rittertum.de) right after registration and no later than January 17th, 2015. Failure to notify us by that time means you voluntarily forfeit your right to any special regulations for that exam.
  • On the doors of the examination room a list of names and seat numbers will be posted. Please find your name and locate the correct seat in the examination room. Please keep the empty rows free of luggage and other obstacles.
  • Be sure to switch off any mobile phones, calculators, tablet computers and other electronic gear and store it out of sight in your bags. Handling any kind of electronic equipment, whether switched on or not, will be considered an attempt at cheating.

Inspection (Klausureinsicht)

  • You can inspect your graded exams on Monday, April 27th at 17:00 in room MI 02.06.020.
  • Please bring a photo ID (the StudentCard is not sufficient).
  • You are allowed to take a photos of your (and only your) exam at the inspection. Please bring your own camera if you intend to do this. It will not be possible to use a xerox machines during inspection.
  • If you cannot come yourself, you can authorize one of your friends to inspect the exam for you, take photos of your exam and (if necessary) demand a revision of the grading on your behalf. To do this, please issue a written authorization for your friend explicitly stating your name and the name of the authorized person and sign it. The authorized person will have to present a photo ID. Here is a possible template text: "Hiermit erteile ich, Anne Musterfrau, Herrn Bernhard Mustermann eine Vollmacht zur Einsichtnahme in meine Klausur im Fach Discrete Optimization. Herr Mustermann ist berechtigt, meine Klausur abzufotografieren und in meinem Namen einen Antrag auf Zweitkorrektur zu stellen."
  • Applications for revised grading (Zweitkorrektur) are only possible during the inspection. If you are sending an authorized person on your behalf, we also accept such applications by email to michael.rittertum.de up to Tuesday, April 28th. After that date, grades will be finalized.
  • If you need a separate date scheduled for inspecting your exam (and have a good reason for this), please write an email to michael.rittertum.de by Monday, April 27th or just drop by Dr. Ritter's office until that date. Please note that all grades must be finalized by April 30th, 2015.

Exams and suggested solutions

  • exam 1: pdf
  • exam 1, suggested solutions: pdf
  • exam 2: pdf
  • exam 2, suggested solutions: pdf

Old Exams

For your information we are providing some old exams here. Please note that the topics covered in the lecture and in the tutorials might be different for different years. In particular, the exams are not meant to give an indication of the topics that will be relevant for this year's exams.
  • exam 1 for the winter term 2013/14: pdf
  • exam 2 for the winter term 2013/14: pdf
  • exam 1 for the winter term 2012/13: pdf
  • exam 2 for the winter term 2012/13: pdf

Examination Dates

Date Time Last Names Room Remarks
Fri, February 6, 2015 09:00 - 10:00 a.m. Ache - Zönnchen MI HS 1 see above for remarks
Wed, April 08, 2015 09:00 - 10:00 a.m. all candidates MW 1450  

Official dates and times are on https://campus.tum.de and are subject to change. Please check back regularly.

Literature

  • Gritzmann: Grundlagen der Mathematischen Optimierung, Springer, 2013
  • Cook, Cunningham, Pulleyblank, Schrijver: Combinatorial Optimization, Wiley, 1998
  • Korte, Vygen: Combinatorial Optimization, Springer, 2002
  • Nemhauser, Wolsey: Integer and Combinatorial Optimization, Wiley, 1999
  • Papadimitriou, Steiglitz: Combinatorial Optimization, Dover, 1998
  • Wolsey: Integer Programming, Wiley, 1998

FAQ

question Which help is allowed during the exam?
info No help, no books, no lecture notes - it's just you and your pen. If you need extra paper you can get some from the exam supervisors.

question How can I find the problem sets and solutions?
info They are available from this site every two weeks. Problem sets are also handed out in the tutorials.

question Where can I find office hours?
info Visit the homepage of the relevant persons or just drop by and ask.