Combinatorial Optimization, MA4502 (in English)
|Dozent:||Prof. Dr. Anusch Taraz|
|Übungsleitung:||Dr. Michael Ritter|
|News||Dates of lectures/exercise classes and office hours||Lecture notes|
- March 15: Registration for the second exam is now open on TUMOnline. Please register until March 25.
- March 08: The second exam is now scheduled for Thursday, April 11, at 9:00 hours.
- Feb 27: Grading for the exam is done, the grades will be published on TUMOnline soon. Exam inspection is scheduled for this Friday, March 1st, at 15:00 in room MI 02.06.020. Please bring a photo ID! More details can be found below in the exam section.
- Feb 13: The second exam for this course has been tentatively scheduled for Thursday, April 11, at 14:00 hours. Should this date be a major problem for you, please protest (via email to michael.rittertum.de) immediately. The date will not be fixed definitely until after the first exam has been graded and results have been published.
- Jan 31: A mistake in the solution to sheet 2 (exercise 2.1) has been corrected.
- Jan 08: Just a reminder: Please do not forget to register for the exam via TUMOnline. Registration will close in a few days on Jan 15, 2013.
- Dec 18: A misleading reference in exercise 5.2 has been deleted, an updated version of exercise sheet 5 is available for download.
- Nov 30: Due to popular demand, the date for the exam has been moved to Feb 25, 2013, 9:00 - 10:00 am. Registration for the exam is now possible on TUMOnline. Please register until Jan 15, 2013 if you want to take the exam.
- Oct 25: Exercise class 2 will start at 18:05, beginning Nov 08, 2012.
- Oct 18: Exercise class 2 moved to a new date. Registration for the exercises classes via TUM-Online starts at 18:00 hours on Oct 18 and is open until Saturday, Oct 21.
Dates of lectures/exercise classes and office hours
|lecture||Thursdays||16:15 - 17:45||Physik HS 2|
|exercise class 1||Wednesdays||10:15 - 11:45||MI 02.04.011||Oct 24, Nov 07, Nov 21, Dec 05, Dec 19, Jan 16, Jan 30|
|exercise class 2||Thursdays||18:05 - 19:35||MI 02.04.011||Oct 25, Nov 08, Nov 22, Dec 13, Dec 20, Jan 17, Jan 31|
|Person||Office hours (during semester)|
|Anusch Taraz||nach Vereinbarung|
- 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.
- All topics covered in either the lecture or the exercise classes are relevant for the exam.
- Registration via TUMOnline is mandatory for participation for the exam (registration for the lecture and/or the exercise classes is not sufficient!)
- Registration is open until Jan 15, 2013.
- The dates and times posted below are preliminary and subject to change.
- An inspection of the graded exams is possible on March 1st, 15:00 hours in room MI 02.06.020.
- Please remember to bring your photo ID to the inspection!
- You may authorize a fellow student of your choice to inspect your exam for you. Please write a certificate of authority stating both your full name and the full name of the authorized person and sign the certificate. The authorized person needs to present a photo ID!
- You may take photos of your (and only your) exams (if you bring a camera). Authorized persons (see previous point) may also take photos of any exam they are authorized to inspect. Please be advised that xeroxing or scanning the exams will not be possible.
- A suggested solution will be posted for download on this website and will also be available during the inspection.
Dates and Times
|Mo, Feb 25, 2013||09:00 - 10:00 hours||CH 21010 (chemistry department, Garching campus)||until Jan 15, 2013 via TUMOnline||exam sheet and suggested solutions|
|Thu, Apr 11, 2013||09:00 - 10:00 hours||MW 1050||until March 25 via TUMOnline||second (and last) attempt|
Students' Exam Problems
|Nov 07, 2012||class 1||Florian Brandl||nov-07-class1.pdf|
|Nov 07, 2012||class 1||Daniel Weißauer||nov-07-class1-2.pdf|
|Nov 08, 2012||class 2||Katharina Juranek||nov-08-class2.pdf|
|Nov 21, 2012||class 1||Martin Schwenk||nov-21-class1.pdf|
|Nov 22, 2012||class 2||Lucia Fogelstaller, Vincent Bates||nov-22-class2.pdf|
|Dec 05, 2012||class 1||Michael Hellgartner, Tanja Niels, Pia Puchner, Sefan Seichter||dec-05-class1.pdf|
|Dec 13, 2012||class 2||Fabian Klemm, Patricia Rachinger||dec-13-class2.pdf|
|Dec 19, 2012||class 1||Gabriel Guckenbiehl, Marco Ricci||dec-19-class1.pdf|
|Dec 20, 2012||class 2||Eva Bammann, Franziska Penk||dec-20-class2.pdf|
|Jan 16, 2013||class 1||Julia Baukmann, Stefan Hoch||jan-16-class1.pdf|
|Jan 17, 2013||class 2||Darya Melnik||jan-17-class2.pdf|
|Jan 30, 2013||class 1||Gabriel Guckenbiehl, Marco Ricci||jan-30-class1.pdf|
Lecture notesFor a complete set of lecture notes similar to the topics covered in this lecture see the notes of WS 2010 by Prof. Raymond Hemmecke: CombOpt.pdf
|Oct 18, 2012||co121018.pdf||1.1 TSP|
|Oct 25, 2012||co121025.pdf|| 1.1 TSP
|Nov 08, 2012||co121108.pdf|| 1.2 Knapsack
2.1 Polyhedra revisited
|Nov 15, 2012||co121115.pdf||2.2 Generating valid inequalities|
|Nov 22, 2012||co121122.pdf||2.3 Generating facet defining inequalities|
|Nov 29, 2012||co121129.pdf|| 2.3 Generating facet defining inequalities
2.4 Lift and project
|Dec 13, 2012||co121213.pdf||3. Ellipsoid Method and Separation|
|Dec 20, 2012||co121220.pdf||4. Randomised Algorithms|
|Jan 10, 2013||co130110.pdf||5. Column generation|
|Jan 17, 2013||co130117.pdf||6.1 Benders decomposition|
|Jan 24, 2013||co130124.pdf||6.2 Lagrange relaxation|
|Jan 31, 2013||co130131.pdf||7. Combinatorial counting problems|
|Feb 07, 2013||co130207.pdf||7. Combinatorial counting problems|
|date||sheet||file||suggested answers and notes|
|Oct 24/25, 2012||exercise sheet 1||sheet01.pdf||sheet01-sol.pdf|
|Nov 07/08, 2012||exercise sheet 2||sheet02.pdf||sheet02-solution.pdf|
|Nov 21/22, 2012||exercise sheet 3||sheet03.pdf||sheet03-solution.pdf|
|Dec 05/13, 2012||exercise sheet 4||sheet04.pdf||sheet04-solution.pdf|
|Dec 19/20, 2012||exercise sheet 5||sheet05.pdf||sheet05-solution.pdf|
|Jan 16/17, 2013||exercise sheet 6||sheet06.pdf||sheet06-solution.pdf|
|Jan 30/Feb 07, 2013||exercise sheet 7||sheet07.pdf||sheet07-solution.pdf|
- Cook, Cunningham, Pulleyblank, Schrijver, Combinatorial Optimization, Wiley 1998
- Korte, Vygen, Combinatorial Optimization: Theory and Algorithms, Springer 2002
- Nemhauser, Wolsey: Integer and Combinatorial Optimization 1999
- Papadimitriou, Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover 1998
- Wolsey: Integer Programming, 1998
FAQWill the tutorials be in English or in German?
There will be at least one English tutorial. The total number of tutorial classes and availability of a German tutorial are subject to participation and will be discussed during the first week of lectures. However, the exercise sheets will be available in English only. Will the exam be in English or in German?
There will be a written exam with questions in English. Answers will be accepted in both English and German (provided the answers are correct, of course).