TUM – TUM – Menü

Discrete Optimization (MA3502)
Vorlesung

Lecturer: Prof. Dr. P. Gritzmann
Tutorials: M.Sc. V. Ghiglione
Weekly hours: 2+1 hours
ECTS credits: 5

News Schedule Office Hours Lecture Exercise Sheets Exam Literature

News

  • 02.03.18: The inspection of the first exam will take place on March 12th at 11am in room 02.06.020.
  • 01.02.18: The complete version of the typed lecture notes has been updated.
  • 16.01.18: The solution to exercise 5.2(a) has been corrected.
  • 30.11.17: The "Dies Academicus" takes place on Thursday Dec. 7th. Therefore, lecture and the tutorial for group 4 are cancelled. Students from group 4 are welcome to join groups 1--3 instead.
  • 09.11.17: The lecture on Feb. 8th 2018 has been cancelled. As replacement there will be an additional lecture on Jan. 17th 2018 10:15--11:45 in HS3.
  • 19.10.17: The slides on organizational details can be downloaded here.
  • 19.10.17: Tutorials for Group 4 have been moved from Wednesday 14:00--16:00 to Thursday 16:00--18:00. The first meeting is on Oct. 26.
  • 19.10.17: If you wish to attend a tutorial, registration is mandatory and starts tonight at 18:00. Please register by Monday 23rd October.
  • 18.10.17: The exam dates are 23.02.2018 and 26.03.2018. Please see details in TUMonline.
  • 05.10.17: The first lecture will take place on Thursday 19th of October from 12:00 to 14:00. The registration for the tutorials will start the same day at 18:00.

Schedule

  Day Time Room Lecturer Dates
Lecture Thursday 12:15 - 13:45 MI HS 3 Prof. Dr. P. Gritzmann 19.10, 26.10, 02.11, 09.11, 16.11, 23.11, 30.11, 14.12, 21.12, 11.01, 17.01 10:15--11:45, 18.01, 25.01, 01.02, 08.02

Tutorial Day Time Room Tutor Dates
Group 01 Tuesday 10:00 - 11:45 MI 02.04.011 V. Ghiglione 24.10, 07.11, 21.11, 05.12, 19.12, 16.01, 30.01
Group 02 Wednesday 14:10 - 15:55 MI 02.04.011 V. Ghiglione 25.10, 08.11, 22.11, 06.12, 20.12, 17.01, 31.01
Group 03 Wednesday 16:10 - 17:55 MI 02.04.011 V. Ghiglione 25.10, 08.11, 22.11, 06.12, 20.12, 17.01, 31.01
Group 04 Thursday 16:00 - 18:00 MI 02.04.011 V. Ghiglione 26.10, 09.11, 23.11, 07.12, 21.12, 18.01, 01.02

Lecture

Lecture Date Content Literature
pdf 19.10.2017 Introduction  
pdf 26.10.2017 Modelling, Linear Diophantine Equations  
pdf 02.11.2017 Systems of linear Diophantine Equations  
pdf 09.11.2017 Unimodularity, Hermite Normal Form  
pdf 16.11.2017 Hermite Normal Form Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, 1998
pdf 23.11.2017 Integer Hulls, Integer Polyhedra
pdf 30.11.2017 Total Unimodularity
pdf 14.12.2017 Total Unimodularity and Applications
pdf 21.12.2017 Partition Methods
pdf 11.01.2018 Branch and Bound, Cutting Plane Methods
pdf 17.01.2018 Hilbert Bases
  18.01.2018 Hilbert Bases and Cuts No slides available
pdf 17.01.2018 Gomory Cuts
pdf 01.02.2018 Gomory Cuts

Here you can download the typed version of the lecture notes.

Exercise Sheets

  • There will be an exercise sheet every two weeks, that will be discussed in the tutorials.
  • If possible, please print the exercise sheets at home and bring them with you (there will be a few copies in the classes as well).
  • In order to make the best of the tutorials' time, have a look at the exercises in advance.
  • All sheets will be password protected. The login details will be announced in the lecture.

Exercise Sheet Date Suggested Solution Remarks
Sheet 1 19.10.17 pdf Here you find an extract from Prof. Gritzmann's lecture on the Simplex Tableau (SoSe13)
Sheet 2 06.11.17 pdf Corrected version: In the algorithm of ex. 2, the assignment k<--0 should be before the for-loop
Sheet 3 17.11.17 pdf  
Sheet 4 01.12.17 pdf  
Sheet 5 17.12.17 pdf Exercise 5.2(b) has been updated (20.12.17), solution to 5.2(a) has been corrected (16.01.18)
Sheet 6 12.01.18 pdf  
Sheet 7 25.01.18 pdf Gomory Cut Applet, Manual, Example files: txt, txt, txt

Exam

Date Time Room
Fr. 23.02.2018 15:30--16:30 MW 2001, Rudolf-Diesel-Hörsaal (5510.02.001)
Mo. 26.03.2018 15:30--16:30 102, Interims Hörsaal 2 (5620.01.102)

Important Information

  • There will be a written exam of 60 minutes.
  • All topics covered in the lecture and the exercises 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 the deadline - you will not be allowed to take the exam without prior registration on TUMonline.
  • In case you have been granted any special regulations for your examination, please make sure to inform us via mail during the registration period. Failure to notify us by that time means you voluntarily forfeit your right to any special regulations for that exam.
  • 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.
  • Please turn off mobile phones, tablets, notebooks, calculators etc. and store them in your bag. Handling any kind of electronic equipment, whether switched on or not, will be considered an attempt at cheating. Of course, the same goes for lecture notes, books, etc.
  • 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.
  • 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.
  • The grades will be published in TUMonline only.

Literature

  • Gritzmann: Grundlagen der Mathematischen Optimierung, Springer, 2013
  • Cook, Cunningham, Pulleyblank, Schrijver: Combinatorial Optimization, Wiley, 1998
  • Korte, Vygen: Combinatorial Optimization, Springer, 2002
  • Papadimitriou, Steiglitz: Combinatorial Optimization, Dover, 1998
  • Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, 1998
Additional literature will be suggested in the lectures.

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)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

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