Discrete Optimization (MA 3502)
|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|
|News||Schedule||Office Hours||Lecture||Exercise Sheets||Exam||Literature|
- 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.
|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|
|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.|
|Person||Office hours (during semester)|
|Dipl.-Math. Viviana Ghiglione||on appointment|
|M.Sc. Felix Happach||on appointment|
|M.Sc. Haakon Rød||on appointment|
|Prof. Dr. Andreas S. Schulz||on appointment|
|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:|
|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:|
|Lecture 12||19.01.17||Gomory's cutting plane procedure; special GC-cuts||Old slides:|
|Lecture 13||26.01.17||mixed integer programming; lift and project cuts||Slides:|
|Lecture 14||02.02.17||Branch and Bound||Slides:|
|Lecture 15||09.02.17||Dynamic Programming; Local Search||Slides:|
- 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:||08.11.16 - 16.11.16||Solution 1:||typo in 1.4 b) corrected, additional hint for 1.5 a)|
|Sheet 2:||22.11.16 - 30.11.16||Solution 2:||Solutions to 2.5: intro.py, introlp.py|
|Sheet 3:||06.12.16 - 14.12.16||Solution 3:||input1.txt, input2.txt, input3.txt, sudoku-framework.py, Solution to 3.5: sudoku.py|
|Sheet 4:||20.12.16 - 11.01.17||Solution 4:||typo in 4.2 corrected||inputtsp.txt, tsp-framework.py, Solution to 4.5: see tspexplicit-framework.py below|
|Sheet 5:||17.01.17 - 25.01.17||Solution 5:||typos corrected; book by Peter Gritzmann (free access via university library)||tspexplicit-framework.py, Solution to 5.5: tspexplicit.py|
|Sheet 6:||31.01.17 - 08.02.17||Solution 6:||Visualization of Gomory cuts with Java||Java file, tutorial, Example files: , ,|
- 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.
|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|
LiteratureThe lecture is based on the books:
- Schrijver: Theory of Linear and Integer Programming, Wiley
- Nemhauser, Wolsey: Integer and Combinatorial Optimization, Wiley, 1999