Discrete Optimization (MA 3502)
lecture

Lectures: Prof. Dr. Nicole Megow
Tutorial management: Dr. Fidaa Abed and Dr. Michael Ritter
Tutorials: Dr. Fidaa Abed and Dr. Michael Ritter

News

  • 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.

Schedule

Lectures

Day Time Room Lecturer
Tue 16:00-17:30 MI HS3 Prof. N. Megow

Tutorial Classes

Here 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.

Day Time Room Dates
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
Thursday, group 4 12:15 - 14:00 MW 1701 Oct 22, Nov 5, Nov 19, Dec 10, Dec 17, Jan 14, Jan 28

Group 4: Due to the Dies Academicus on December 3rd, the tutorial scheduled for that day will be held one week later on December 10th instead.

Registration for the tutorials will start on Tuesday, October 13th at 18:00 and close on Friday, October 16th. You must register for one of the tutorials during that time in order to participate in the tutorials. (However, the tutorials are recommended, but optional.)

The tutorials usually start with a 15 minute recap session. This time is additional to the usual 90 minutes and a voluntary extra offer, you are free to arrive at the tutorial only after these first 15 minutes if you are not interested in the recap. The rest of the tutorials will be devoted to problem presentations by the students and to hands-on problem sessions where you work on the problems in small groups.

Scribbles from the lecture

download description
pdf Introductory slides
pdf Introduction and modeling of ILPs (October 13th, 2015)
pdf Integer hull of polyhedra (October 20th, 2015)
pdf Total Dual Integrality (October 27th, 2015)
pdf Totally unimodular matrices (November 3rd, 2015)
pdf Characterizations of totally unimodular matrices (November 10th, 2015)
pdf Complexity of ILP (November 17th, 2015)
pdf Cutting planes (November 24th, 2015)
pdf Branch and Bound & DP (December 1st, 2015)
pdf Cutting planes algorithm (December 8th, 2015)
pdf Cover inequalities for Knapsack, cutting plane algorithm TSP (December 15th, 2015)
pdf Comb inequalities for TSP, column generation (December 22th, 2015)
pdf Lagrangean Relaxation (January 12th, 2016)
pdf Approximation algorithms, metric TSP (January 19th, 2016)
pdf Gap reduction: TSP, LP-rounding: vertex cover (January 27th, 2016)
pdf Randomized rounding: Max SAT (February 2nd, 2016)

Problem sets and solutions

The 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: pdf suggested solutions 1 UPDATED Oct 15th (fixed a typo in 1.3)
Sheet 2: pdf suggested solutions 2  
Sheet 3: pdf suggested solutions 3  
Sheet 4: pdf suggested solutions 4  
Sheet 5: pdf suggested solutions 5 UPDATED Dec 22nd: complete solutions
Sheet 6: pdf suggested solutions 6  
Sheet 7: pdf suggested solutions 7  

To see how the TSP can be solved using Lagrangian relaxation and 1-trees take a look at our TSP game.

Exam

Important Information

  • 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.

Examination Dates

Date Time Last Names Room
Thu, February 18th, 2016 13:30 - 14:30 all candidates MI HS 1
Wed, April 06, 2016 15:30 - 16:30 all candidates MW0350

Official dates and times are on https://campus.tum.de and are subject to change. Please check back regularly.

Literature

  • 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

FAQ

question Where can I find office hours?
info Visit the homepage of the relevant persons or just drop by and ask.