Discrete Optimization (MA 3502)
|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|
- 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.
|Tue||16:00-17:45||MI HS3||P. Gritzmann|
|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 4||Thu||12:15 - 14:00||MW 1701||Michael Ritter|| Oct 16, Oct 30, Nov 13, Nov 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|
|additional lecture notes in German (Jan 28, 2015)|
|lecture notes for Oct 07, 2014|
|lecture notes for Oct 21, 2014|
|lecture notes for Oct 28, 2014|
|lecture notes for Nov 04, 2014|
|lecture notes for Nov 18, 2014|
|lecture notes for Nov 25, 2014|
|lecture notes for Dec 02, 2014|
|lecture notes for Dec 09, 2014|
|lecture notes for Dec 16, 2014|
|lecture notes for Dec 23, 2014|
|lecture notes for Jan 13, 2015|
|java applet to visualize Gomory Cuts (see included "readme.pdf" for instructions)|
|lecture notes for Jan 20, 2015|
|lecture notes for Jan 27, 2015|
Problem sets and solutions
|Problem Set||Suggested Solutions||remarks|
|Sheet 1:||suggested solutions 1|
|Sheet 2:||suggested solutions 2|
|Sheet 3:||suggested solutions 3|
|Sheet 4:||suggested solutions 4|
|Sheet 5:||suggested solutions 5|
|Sheet 6:||suggested solutions|
|Sheet 7:||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|
- 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.
- 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
Old ExamsFor 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:
- exam 2 for the winter term 2013/14:
- exam 1 for the winter term 2012/13:
- exam 2 for the winter term 2012/13:
|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|
- 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
FAQWhich help is allowed during the exam?
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. How can I find the problem sets and solutions?
They are available from this site every two weeks. Problem sets are also handed out in the tutorials. Where can I find office hours?
Visit the homepage of the relevant persons or just drop by and ask.