TUM – TUM – Menü

 

 
Combinatorial Optimization, MA4502 (in English)

lecture

 

Dozent: Prof. Dr. Anusch Taraz
Übungsleitung: Dipl.-Math. Felix Schmiedl

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

News

  • Oct 9: The grades for the exam haven been published on TUMOnline.
  • Oct 7: The exam inspection is scheduled for Monday, October 14, at 10:00 in room MI 02.06.020. Please bring a photo ID! More details can be found below in the exam section.
  • Aug 7: The grades for the exam haven been published on TUMOnline. The exam inspection is scheduled for Wednesday, August 14, at 10:00 in room MI 02.06.020. Please bring a photo ID! More details can be found below in the exam section.
  • Jul 16: There will be an extra tutorial on Thursday, Jul 25 at 10:00 hours in room 02.04.011, where you can ask questions regarding the material covered in the lecture and exercise lasses.
  • Jul 16: The exams from last semester are now online.
  • May 29: The time of the exam has been changed to 11:00 hours.
  • May 15: The date of the exam has been fixed.
  • Apr 18: The room for exercise class 2 has been changed to MI 02.08.020!
  • Apr 17: Added Lecture notes for required bachelor courses.
  • Apr 16: Starting April 23rd, the lecture will begin at 16:00 hours.

Dates of lectures/exercise classes and office hours

day time room
lecture Tuesday 16:00 - 17:30 MI 00.07.014

day time room dates
exercise class 1 Thursday 16:00 - 17:30 MI 03.10.011 Apr 18, May 2, May 16, Jun 6, Jun 13, Jun 27, Jul 11
exercise class 2 Friday 12:15 - 13:45 MI 02.08.020 Apr 19, May 3, May 17, Jun 7, Jun 14, Jun 28, Jul 12

Person Office hours (during semester)
Anusch Taraz by appointment
Felix Schmiedl by appointment

Exam

Important Information

  • All topics covered in the lecture and 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!)
  • The dates and times posted below are preliminary and subject to change.

Dates and Times

date time room registration remarks
Tue, July 30, 2013 11:00 Interims HS 2 until June 30, 2013 via TUMOnline first attempt
Wed, Oct 2, 2013 12:00 MI HS 2 Sep 2 - Sep 16, 2013 via TUMOnline second (and last) attempt

Exam Inspection

  • An inspection of the graded exams is possible on October 14, 10: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 available during the inspection.

Lecture notes

For a complete set of lecture notes similar to the topics covered in this lecture see the notes of WS 2010/2011 by Prof. Raymond Hemmecke: CombOpt 2010 or of WS 2012/2013 by Prof. Anusch Taraz: CombOpt 2012.

date download topic
Apr 16, 2013 pdf 1. Approximation algorithms (TSP hardness)
Apr 23, 2013 pdf 1. Approximation algorithms (heuristics for the TSP)
Apr 30, 2013 pdf 1. Approximation algorithms (Knapsack: dyn programming and FPTAS)
May 07, 2013 pdf 2. Methods to strengthen an ILP-formulation (Polyhedral geometry revisited)
May 14, 2013 pdf 2. Methods to strengthen an ILP-formulation
July 02, 2013 pdf 6.1 Benders decomposition
July 09, 2013 pdf 6.2 Lagrange relaxation
July 16, 2013 pdf 6.2 Subgradient plus Branch and Bound

Lecture notes by Prof. Taraz for the required bachelor courses ADM and Linear Optimization can be found on the websites of the courses or as a single pdf file here: ADM 2011 and CaLo 2010.

Exercise sheets

date sheet file suggested answers
Apr 18/19 exercise sheet 1 sheet01.pdf sheet01-sol.pdf
May 2/3 exercise sheet 2 sheet02.pdf sheet02-sol.pdf
May 16/17 exercise sheet 3 sheet03.pdf sheet03-sol.pdf
Jun 6/7 exercise sheet 4 sheet04.pdf sheet04-sol.pdf
Jun 13/14 exercise sheet 5 sheet05.pdf sheet05-sol.pdf
Jun 27/28 exercise sheet 6 sheet06.pdf sheet06-sol.pdf
Jul 11/12 exercise sheet 7 sheet07.pdf sheet07-sol.pdf

Old Exams

exam file suggested answers
WS12/13 first exam12-1.pdf exam12-1-sol.pdf
WS12/13 second exam12-2.pdf exam12-2-sol.pdf
SS 13 first exam13-1.pdf exam13-1-sol.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).

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.