TUM – TUM – Menü

Discrete Optimization (MA 3502)
lecture

Lecturer: Prof. Dr. Andreas S. Schulz
Tutorials: M.Sc. Felix Happach, Dipl.-Math. Viviana Ghiglione , M.Sc. Haakon Rød
Weekly hours: 2+1 hours
ECTS credits: 5

News Schedule Office Hours Lecture Exercise Sheets Exam Literature

News

  • 28.04.17: The grades of the retake exam are now online. Please enter your objections until May 4th, 11:59 pm.
  • 14.03.17: Registration for the retake exam which takes place on Apr 11th is open from Mar 20th until Apr 3rd.
  • 01.03.17: The grades are now online. Please enter your objections until Mar 7th, 11:59 pm.
  • 06.02.17: Please find further information on the exam below.
  • 01.02.17: Reminder: tomorrow's lecture will take place in the LRZ lecture hall HE 009.
  • 26.01.17: Attached you find the lecture notes from Discrete Optimization WS14/15 taught by Prof. Gritzmann. You may consult them to have an additional reference. Please keep in mind that topics and notations may differ from the ones of this course.
  • 25.01.17: Thanks to Franziska Moßner, who kindly volunteered to provide her notes of the blackboard, there are now up-to-date lecture notes online. We will update them after each lecture.
  • 24.01.17: There is a Java application which visualizes Gomory cuts in a very nice way. Please find a link, tutorial and example files below in the remarks of the sixth sheet.
  • 23.01.17: The sixth (and last) exercise sheet is now online. Only Exercises 6.1 and 6.2 will be discussed in the tutorials. The remaining time will be used for questions and answers.
  • 22.01.17: You should have received a mail regarding the evaluation of this course which can be done online. We would like to encourage you to use this opportunity in order to enable us to improve the lecture and tutorials for future semesters. Evaluation is open until Jan 27.
  • 18.01.17: Concerning Exercise 5.3 (definition of a graphical matroid): For those of you who did not have the lecture ADM (or already forgot about it) please check Chapter 2.3 of Grundlagen der Mathematischen Optimierung  (in german). You should have free access via the university library.
  • 17.01.17: There will be two seminars next semester which might be of interest for you: "Nonlinear Discrete Optimization" and "Advanced Methods in Combinatorial and Integer Optimization". Registration is open from Jan, 23 until Jan, 29. For more information please check the website.
  • 21.12.16: The fifth exercise sheet is now online. Exercise 5.1 covers content which will be part of the lecture on Jan 12; however, 5.2 - 5.5 should be doable with your knowledge from this year. Merry Christmas and a Happy New Year!
  • 15.12.16: There will be an additional tutorial on Wed. 21 Dec. 2016, 14.05-15:50 in BC2 0.01.05 (Hochbrück). This is to give the chance to students of Groups 2,4,5 to attend a tutorial on Sheet 4 before the holidays. The January schedule is not affected.
  • 14.12.16: The lecture on Dec 22, 2016 will be cancelled.
  • 12.12.16: The fourth exercise sheet is now online.
  • 06.12.16: The lecture on Feb 2, 2017 will be in the LRZ lecture hall H.E.009.
  • 28.11.16: The third exercise sheet is now online.
  • 18.11.16: We are looking for a scribe. Anyone who believe (s)he takes good notes in class, regardless of whether they are handwritten or in electronic form, and who is willing to share them with the instructor, is encouraged to apply. Compensation is possible. Please email Professor Schulz directly.
  • 15.11.16: Registration for the exam is now available in TUMOnline.
  • 11.11.16: The second exercise sheet is now online.
  • 31.10.16: The first exercise sheet is now online.
  • 13.10.16: The first lecture will be on Oct 20, 12:15.
  • 13.10.16: Registration for the exercise classes starts on Oct 21, 18:00 in TUMOnline.

Schedule

Event Day Time Room Lecturer Remarks
Lecture Thursday 12:15 - 13:45 MI HS 3 Prof. Dr. Andreas S. Schulz Change of location on 02.02.17: LRZ lecture hall H.E.009

Event Day Time Room Lecturer Language Dates
Group 01 Tuesday 12:00 - 13:45 MI 02.04.011 Felix Happach English 8.11., 22.11., 6.12., 20.12, 17.1, 31.1.
Group 02 Tuesday 12:00 - 13:45 MI 02.04.011 Viviana Ghiglione English 15.11., 29.11., 13.12., 10.1., 24.1., 7.2.
Group 03 Wednesday 16:05 - 17:50 BC2 0.01.05 (Hochbrück) Viviana Ghiglione English 9.11., 23.11., 21.12, 18.1., 1.2. -- (7.12. is Dies Academicus, please go to another group in this week)
Group 04 Wednesday 16:10 - 17:55 BC2 0.01.05 (Hochbrück) Viviana Ghiglione English 16.11., 30.11., 14.12., 11.1., 25.1., 8.2.
Group 05 Wednesday 14:05 - 15:50 BC2 0.01.05 (Hochbrück) Viviana Ghiglione English 16.11., 30.11., 14.12., 11.1., 25.1., 8.2.

The exercise classes are biweekly and in english by default. Details will be discussed in the first class of every group.

Office Hours

Person Office hours (during semester)
Prof. Dr. Andreas S. Schulz on appointment
M.Sc. Felix Happach on appointment
Dipl.-Math. Viviana Ghiglione on appointment
M.Sc. Haakon Rød on appointment

Lecture

Lecture Date Content Literature
Lecture 1 20.10.16 introduction to discrete optimization; examples Chapter 1 of Schrijver
Lecture 2 27.10.16 introduction to running time and complexity; complexity classes P, NP, co-NP Chapter 2 of Schrijver
Lecture 3 03.11.16 linear diophantine equations; hermite normalform; unimodular matrices; euclidean algorithm Chapters 4 and 5 of Schrijver
Lecture 4 10.11.16 fundamental concepts of polyhedral theory Chapters 7 and 8 of Schrijver
Lecture 5 17.11.16 integer hull and integer polyhedra; vertex and facet complexity Chapters 16.1 - 16.3, 10.2 and 17.1 of Schrijver
Lecture 6 24.11.16 totally unimodular matrices Chapters 19.1 - 19.3 of Schrijver
Lecture 7 01.12.16 Hilbert basis; total dual integrality Chapters 16.4, 22.1 and 22.3 of Schrijver
Lecture 8 08.12.16 -- cancelled due to sickness --  
Lecture 9 15.12.16 independent set systems, matroids Old slides: pdf
Lecture 10 22.12.16 -- cancelled --  
Lecture 11 12.01.17 introduction to cutting plane methods; Gomory-Chvátal cuts, Chvátal closure, Chvátal rank Old slides: pdf
Lecture 12 19.01.17 Gomory's cutting plane procedure; special GC-cuts Old slides: pdf
Lecture 13 26.01.17 mixed integer programming; lift and project cuts Slides: pdf
Lecture 14 02.02.17 Branch and Bound Slides: pdf
Lecture 15 09.02.17 Dynamic Programming; Local Search Slides: pdf

Lecture notes of Franziska Moßner: pdf.

Lecture notes from WS14/15: pdf.

Exercise Sheets

  • There will be an exercise sheet every two weeks which will be discussed in the exercise classes.
  • If possible, please print the sheets at home and bring them with you (there will be a few copies in the classes as well).
  • Please have a look at the exercises in advance and try to solve them such that we can discuss problems and solution approaches in the classes.
  • Students can present their solution (approaches) or solve the (remaining) exercises in groups in the tutorials. The tutorials are not intended to just copy the sample solution from the blackboard!
  • All sheets will be password protected. The login details will be announced in the lecture.
  • The suggested solutions are not necessarily complete solutions (with all computational details etc.), just solution hints.
  • As of the second problem set there will be a computational exercise on each sheet. This exercise will not be discussed in the tutorials. However, there will be a suggested solution. In case you have questions concerning the computational exercise, please contact Haakon Rød.
  • Unfortunately, uploaded python files (.py) are automatically converted to .txt files. Please make sure to rename the python files (just delete the .txt ending) before trying to run them.

Exercise Sheet Dates Suggested Solution Remarks Files
Sheet 1: pdf 08.11.16 - 16.11.16 Solution 1: pdf typo in 1.4 b) corrected, additional hint for 1.5 a)  
Sheet 2: pdf 22.11.16 - 30.11.16 Solution 2: pdf   Solutions to 2.5: intro.py, introlp.py
Sheet 3: pdf 06.12.16 - 14.12.16 Solution 3: pdf   input1.txt, input2.txt, input3.txt, sudoku-framework.py, Solution to 3.5: sudoku.py
Sheet 4: pdf 20.12.16 - 11.01.17 Solution 4: pdf typo in 4.2 corrected inputtsp.txt, tsp-framework.py, Solution to 4.5: see tspexplicit-framework.py below
Sheet 5: pdf 17.01.17 - 25.01.17 Solution 5: pdf typos corrected; book  by Peter Gritzmann (free access via university library) tspexplicit-framework.py, Solution to 5.5: tspexplicit.py
Sheet 6: pdf 31.01.17 - 08.02.17 Solution 6: pdf Visualization of Gomory cuts with Java Java file, tutorial, Example files: txt, txt, txt

Exam

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.
  • The registration for the (first) exam is open from 15.11.16 until 15.1.17.
  • 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 TUMOnline.
  • The dates and times for the exam posted below are unofficial and subject to change. Please consult TUMOnline for the official dates.
  • 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 exam will look different than previous exams you might know. Instead of writing your name etc. on the coversheet, you will receive a personal QR code on your exam after we checked your ID.
  • The grades will be published in TUMOnline only.
  • There will not be an exam inspection on a fixed date, but your (corrected) exam will be scanned and uploaded to TUMOnline (of course you will only be able to see your own exam and not the ones of other students).
  • You will find a link beneath your exam grade in TUMOnline (in the yellow remark line) which will direct you to an online exam inspection form. This link is unique, so you will only be able to view your own exam. As a verification you will be asked to enter your student ID number with leading zero. Once the grades are online, you will have one week in order to inspect your exam and enter potential objections.
  • Registration for the (second) exam is open from 20.03.17 until 03.04.17.

Examination Dates

Date Time Room Registration
15.02.17 16:00 - 17:00 MI HS 1 15.11.16 - 15.01.17
11.04.17 14:00 - 15:00 MI HS 1 20.03.17 - 03.04.17

Official dates and times are on TUMOnline and are subject to change. Please check back regularly.

Literature

The lecture is based on the books:

  • Schrijver: Theory of Linear and Integer Programming, Wiley
  • Nemhauser, Wolsey: Integer and Combinatorial Optimization, Wiley, 1999

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.