Combinatorial Optimization (MA4502)
|Lectures:||Dr. Michael Ritter|
|Tutorial management:||Dr. Michael Ritter|
|Tutorials:||Dr. Michael Ritter|
|News||Schedule||Problem sets and solutions||Literature||FAQ|
- 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.
|Tue||16:05-17:35||MI HS3||M. Ritter|
Tutorial ClassesThe 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 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|
Lecture notes and slides
|lecture notes, last updated on July 14th, 2015|
|slides for April 14th, 2015|
|slides for April 21st, 2015|
|slides for April 28th, 2015|
|slides for May 2015 lectures|
|slides for June 2nd, 2015|
|slides for June 9th, 2015|
|slides for June 16th, 2015|
|slides for June 23th, 2015|
| Python code for the knapsack problem (rename to
|slides for June 30th, 2015|
|slides for July 7th, 2015|
Problem sets and solutions
|Problem Set||Suggested Solutions||remarks|
|Sheet 1:||suggested solutions 1|
|Sheet 2:||suggested solutions 2|
|Sheet 3:||suggested solutions 3|
|Sheet 4:||suggested solutions 4|
|Sheet 5:||suggested solutions 5|
|Sheet 6:||suggested solutions 6|
|Sheet 7:||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 Minkowskis Theorem|
|July 16th, Group 2||Stefan Jaax, Julius Zwirner||Heuristics for the Partition Problem|
- 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.
- 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 ExamsFor 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:
- suggested solutions for exam 1 for the winter term 2012/13:
- exam 2 for the winter term 2012/13:
- suggested solutions for exam 2 for the winter term 2012/13:
|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|
|Mon, Sept. 21st, 2015||15:00 - 16:00||all candidates||Interimshörsaal 2|
- 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