Combinatorial Optimization, MA4502 (in English)

lecture

 

Dozent: Prof. Dr. Anusch Taraz
Übungsleitung: Dr. Michael Ritter

News Dates of lectures/exercise classes and office hours Lecture notes
Exercise sheets Literature FAQ

News

  • 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

day time room
lecture Thursdays 16:15 - 17:45 Physik HS 2

day time room dates
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

Please note that exercise class 2 will not take place on Dec 6 due to "Dies Academicus". Instead, this class will be postponed to Dec 13.

Please register for the tutorial classes until Saturday, Oct 21. You can find the exercise classes in TUM-Online. If you cannot attend any of these classes (but would like to), please email me.

Person Office hours (during semester)
Anusch Taraz nach Vereinbarung
Michael Ritter tba

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

Exam Inspection

  • 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

date time room registration remarks/downloads
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

date tutorial class author(s) download
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 notes

For 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

date download topic
Oct 18, 2012 co121018.pdf 1.1 TSP
Oct 25, 2012 co121025.pdf 1.1 TSP
1.2 Knapsack
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

Exercise sheets

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

Literature

  • 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

FAQ

question Will the tutorials be in English or in German?
info 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.

question Will the exam be in English or in German?
info 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).