|Lectures:||Prof. Dr. Nicole Megow|
|Tutorial management:||Dr. Fidaa Abed and Dr. Michael Ritter|
|Tutorials:||Dr. Fidaa Abed and Dr. Michael Ritter|
- April 26, 2016: Exam results for the retake exam are now on TUM-Online. The inspection date has been set to Wednesday, April 27th, 17:00 - 17:30 at room MI 02.06.020. Please see below for details on the inspection.
- March 24, 2016: Due to construction works the exam on April 6th, 2016, has been moved to a different room. The exam will now take place in MW0350, the examination time remains unchanged.
- December 17, 2015: Due to sickness today's tutorial of group 4 will have to be cancelled. We will try to offer a replacement tutorial after the christmas break.
- December 1, 2015: Exam registration has started and is live on TUM-Online. If you want to take the exam for this course, registration via TUM-Online is mandatory, the registration deadline is January 15th, 2016. Please note that failure to register in time means you will not be able to take the exam. Registration for the second exam date will be separately. In particular, if you only plan to take the exam on the second possible date, you do not need to register (or show up) for the first exam date.
|Tue||16:00-17:30||MI HS3||Prof. N. Megow|
Tutorial ClassesHere are the preliminary dates and times for the tutorial classes. All of this is still subject to change depending on the availability of teaching staff and rooms and on the preferences of the participants. If you cannot make it to any of these dates, please let me know at michael.rittertum.de as soon as possible.
|Thursday, group 4||12:15 - 14:00||MW 1701|| Oct 22, Nov 5, Nov 19, Dec 10,
|Tuesday, group 1||12:00 - 13:45||MI 02.04.011||Oct 20, Nov 3, Nov 17, Dec 1, Dec 15, Jan 12, Jan 26|
|Tuesday, group 1.5||12:00 - 13:45||MI 02.04.011||Nov 10, Nov 24, Dec 8, Dec 22, Jan 19, Feb 2|
|Wednesday, group 2||14:00 - 15:45||MI 02.04.011||Oct 21, Nov 4, Nov 18, Dec 2, Dec 16, Jan 13, Jan 27|
|Wednesday, group 3||16:15 - 18:00||Seminarraum 105, Garching-Hochbrück||Oct 21, Nov 4, Nov 18, Dec 2, Dec 16, Jan 13, Jan 27|
Scribbles from the lecture
|Introduction and modeling of ILPs (October 13th, 2015)|
|Integer hull of polyhedra (October 20th, 2015)|
|Total Dual Integrality (October 27th, 2015)|
|Totally unimodular matrices (November 3rd, 2015)|
|Characterizations of totally unimodular matrices (November 10th, 2015)|
|Complexity of ILP (November 17th, 2015)|
|Cutting planes (November 24th, 2015)|
|Branch and Bound & DP (December 1st, 2015)|
|Cutting planes algorithm (December 8th, 2015)|
|Cover inequalities for Knapsack, cutting plane algorithm TSP (December 15th, 2015)|
|Comb inequalities for TSP, column generation (December 22th, 2015)|
|Lagrangean Relaxation (January 12th, 2016)|
|Approximation algorithms, metric TSP (January 19th, 2016)|
|Gap reduction: TSP, LP-rounding: vertex cover (January 27th, 2016)|
|Randomized rounding: Max SAT (February 2nd, 2016)|
Problem sets and solutionsThe problems on the sheets are roughly ordered by increasing difficulty and/or time requirements. We will usually use the first half of the problems for the students presentations and discussions and the second half for the hands-on problem session.
|Problem Set||Suggested Solutions||remarks|
|Sheet 1:||suggested solutions 1||Oct 15th (fixed a typo in 1.3)|
|Sheet 2:||suggested solutions 2|
|Sheet 3:||suggested solutions 3|
|Sheet 4:||suggested solutions 4|
|Sheet 5:||suggested solutions 5||Dec 22nd: complete solutions|
|Sheet 6:||suggested solutions 6|
|Sheet 7:||suggested solutions 7|
- 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 unofficial 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 (michael.rittertum.de) right after registration and no later than February 10th, 2016. 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. Of course, the same goes for lecture notes, books, etc.
Exam Inspection (Klausureinsicht)
- You can inspect your graded exams on Wednesday, April 27th, 17:00 to 17:30 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 machine 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 to verify his/her identity. 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 on the same day (Wednesday, April 27th). 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 before the inspection takes place. Please note that all grades must be finalized by Friday April 29th, 2016.
|Thu, February 18th, 2016||13:30 - 14:30||all candidates||MI HS 1|
|Wed, April 06, 2016||15:30 - 16:30||all candidates||MW0350|
- Nemhauser, Wolsey: Integer and Combinatorial Optimization, Wiley, 1999
- Schrijver: Theory of Linear and Integer Programming, Wiley
- Wolsey: Integer Programming, Wiley, 1998
- Bertsimas, Tsitsiklis: Introduction to Linear Optimization, Athena, 1997
FAQWhere can I find office hours?
Visit the homepage of the relevant persons or just drop by and ask.