Combinatorial Optimization (MA4502)

Vorlesung

Lectures: Dr. Michael Ritter
Tutorial management: Dr. Michael Ritter
Tutorials: Dr. Michael Ritter

News Schedule Problem sets and solutions Literature FAQ

News

  • August 31st, 2015: The date for the repeat exam has been set to September 21st, 15:00 - 16:00. Please register via TUMOnline until September 14th, 2015.
  • June 2, 2015: Room change: Today's lecture will take place at LRZ HE 009 in the LRZ building next to the MI building. Please note that no food or drinks are allowed in that room.
  • May 26, 2015: No lectures will take place today (TUM wide).
  • May 20, 2015: Exam registration on TUMOnline has started. Please remember to register for the exam, you will not be able to take the exam otherwise. The registration will close on June 30th, 2015.
  • April 21, 2015: Lectures will start at 16:05 starting on April 28.
  • March 26, 2015: Lectures will start in the first week of the semester on April 14th, tutorials will presumably start in the second week. Registration for the lecture on http://campus.tum.de is recommended to be notified in case of any changes on short notice, but it is not mandatory. I will talk about contents, organizational matters and tutorials during the first class on April 14th.

Schedule

Lectures

Day Time Room Lecturer
Tue 16:05-17:35 MI HS3 M. Ritter

Tutorial Classes

The schedule for the tutorial classes can be found below. Please note that tutorials will not take place on June 4th or 5th due to the public holiday on June 4th. Instead, there will be tutorial in the following week.

Group Day Time Room Tutor Dates
Group 1 Thu 10:05 - 11:50 MI 02.04.011 Michael Ritter Apr 23, May 7, May 21, Jun 11, Jun 18, Jul 2, Jul 16
Group 2 Thu 12:05 - 13:50 MI 00.09.022 Michael Ritter Apr 23, May 7, May 21, Jun 11, Jun 18, Jul 2, Jul 16
Group 3 Fri 10:05 - 11:50 MI 02.04.011 Michael Ritter Apr 24, May 8, May 22, Jun 12, Jun 19, Jul 3, Jul 16

Unfortunately, the last Friday tutorial (originally scheduled for Friday, July 17th) cannot take place on that day. You are invited to attend one of the Thursday tutorials on July 16th instead.

Lecture notes and slides

download description
pdf lecture notes, last updated on July 14th, 2015
pdf slides for April 14th, 2015
pdf slides for April 21st, 2015
pdf slides for April 28th, 2015
pdf slides for May 2015 lectures
pdf slides for June 2nd, 2015
pdf slides for June 9th, 2015
pdf slides for June 16th, 2015
pdf slides for June 23th, 2015
txt Python code for the knapsack problem (rename to knapsack.py, then call with python3 knapsack.py)
pdf slides for June 30th, 2015
pdf slides for July 7th, 2015

Problem sets and solutions

Problem Set Suggested Solutions remarks
Sheet 1: pdf suggested solutions 1  
Sheet 2: pdf suggested solutions 2  
Sheet 3: pdf suggested solutions 3  
Sheet 4: pdf suggested solutions 4  
Sheet 5: pdf suggested solutions 5  
Sheet 6: pdf suggested solutions 6  
Sheet 7: pdf suggested solutions 7  

Students Exam Problems

Date and Group Authors Link and Comments
May 7th, Group 1 InYoung Choi, Stefan Heidekrüger, Andreas Stöger Clique Partitioning
May 8th, Group 3 Thiemo Taube, Jonathan Roth Modelling
May 21st, Group 1 Sarah Braun, Anja Kirschbaum, Christina Gallner The Order Polytope
May 21st, Group 2 Annika Treyer, Martin Sperr, Lukas Thiele Stable Sets and Bipartite Subgraphs
May 22nd, Group 3 Tobias Reinerth, Antonia Ache Graph Coloring
June11th, Group 1 Alexander Healey, Daniel Schmidt gen. Waldschmidt Minimum Vertex Cover
June11th, Group 2 Franziska Zimmermann, Christian Kreipl Triangle-Free Graphs
June12th, Group 3 Erchis Ariunjargal, Daniel Schaden Lifting for the Knapsack Problem
June18th, Group 1 Felix Happach, Florian Nitzl, Christian Treubel Vertex Cover Approximation
June18th, Group 2 Franziska Eberle, Alexandra Steil The "Next Fit" Algorithm for Bin Packing
June19th, Group 3 Jeongseok Seo, Seyed Reza Sefidgar Steiner Tree Approximation
July 2nd, Group 1 Kristof Bauer Set Cover Approximation
July 2nd, Group 2 Susanne Huber, Ricarda Reppermund Approximation
July 16th, Group 1 Sandro Kiehl, Manuel Frieß Column Generation using Minkowski’s Theorem
July 16th, Group 2 Stefan Jaax, Julius Zwirner Heuristics for the Partition Problem

Please note that these problems and the suggested solutions are not reviewed nor edited by teaching staff.

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)! Registration starts on Monday, August 31st, 2015 and ends on September 14th, 2015. Please do not forget to register until that date - you will not be allowed to take the exam without prior registration on TUM-Online. Please note that you will have to register for the repeat exam regardless of your participation in the original exam.
  • The dates and times for the exam posted below are preliminary 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) until the registration end date. 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.

Inspection (Klausureinsicht)

  • You can inspect your graded exams on Friday, October 9th at 10:00 in room MI 02.04.011.
  • Please bring a photo ID (the StudentCard is not sufficient and also not required).
  • You are allowed to take 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 his/her photo ID. Here is a possible template text: "Hiermit erteile ich, Anne Musterfrau, Herrn Bernhard Mustermann eine Vollmacht zur Einsichtnahme in meine Klausur im Fach Combinatorial Optimization. Herr Mustermann ist berechtigt, meine Klausur abzufotografieren und in meinem Namen einen Antrag auf Zweitkorrektur zu stellen." If you can only provide your friend with such a document of authorization as an email printout (instead of the original document), please also send it to michael.rittertum.de.
  • Applications for revised grading (Zweitkorrektur) are only possible during the inspection. If you are sending an authorized person on your behalf, I also accept such applications by email to michael.rittertum.de up to Monday, October 12th. 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 prior to the scheduled inspection date. I will then contact you to offer a date for a separate inspection. Please note that grades will have to be finalized soon.

Old Exams

For your information we are providing some old exams here. Please note that the topics covered in the lecture and in the tutorials might be different for different years (and will be somewhat different from 2012 this year). In particular, the exams are not meant to give an indication of the topics that will be relevant for this year's exams.
  • exam 1 for the winter term 2012/13: pdf
  • suggested solutions for exam 1 for the winter term 2012/13: pdf
  • exam 2 for the winter term 2012/13: pdf
  • suggested solutions for exam 2 for the winter term 2012/13: pdf

Examination Dates

Date Time Last Names Room Remarks Exam Sheet
Wed, July 29th, 2015 09:00 - 10:00 a.m. all candidates Interimshörsaal 1 see above for remarks pdf
Mon, Sept. 21st, 2015 15:00 - 16:00 all candidates Interimshörsaal 2    

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

Literature

  • Papadimitriou, Steiglitz: Combinatorial Optimization, Dover, 1998
  • Korte, Vygen: Combinatorial Optimization, Springer, 2002
  • Schrijver: Combinatorial Optimization (volumes A-C), Springer, 2003
  • Nemhauser, Wolsey: Integer and Combinatorial Optimization, Wiley, 1999
  • Cook, Cunningham, Pulleyblank, Schrijver: Combinatorial Optimization, Wiley, 1998
  • Wolsey: Integer Programming, Wiley, 1998
  • Gritzmann: Grundlagen der Mathematischen Optimierung, Springer, 2013

FAQ