TUM – TUM – Menü

 

 
Discrete Optimization

Vorlesung

 

Lectures: Anusch Taraz
Exercises: Oliver Cooley

News Dates of lectures/exercise classes Lecture notes Problem sheets Literature FAQ

%SBICON% Ca. 33% aller Hilfskräfte in der Mathematik im Sommersemester 2011 werden aus Studienbeiträgen finanziert.

Exam

  • The exam will take place on Tuesday 24th July at 13:00 in Interimshörsaal 1. Please arrive on time.
  • The exam will last 60 minutes.
  • Please bring your student card (Studentenausweis) and personal ID (Lichtbildausweis) to the exam.
  • You will not be allowed to bring any devices or materials other than pens into the exam.
  • As preparation, you can download the exam and the resit exam from 2011.
  • Your grades will be announced via TUMOnline.
  • You will have the opportunity to view your corrected exam booklet on Wednesday 1st August from 14:00 to 15:00 in room MI 02.04.011. Please bring your student card.
  • Model solutions for the first exam are now in the display case around the corner from corridor MI 02.04 (between the corridor and the main hall of the MI building).
  • The re-sit exam will take place on Thursday 27th September at 09:00 in Interimshörsaal 2.
  • You can now register online for the re-sit exam. You must register by 17.9.2012.
  • The viewing of corrected re-sit exams will be on Friday 28th September at 10:00 in MI 02.06.020.

News

  • This course will be given in English.
  • First lecture on April 17.
  • See the entry in the Handbook of modules
  • The registration for exercise groups runs from 17.4 21:00 until 20.4.23:59 on TUM-Online.
  • Please note that the new exercise group 5 has replaced the old group 2. Those registered to group 2, please re-register for a different group.
  • Those who were on the waiting list for group 3 have now been moved to the new group 4.
  • Please note the correction to Exercise Sheet 3, Problem 1a: property (ii) should include the condition that F is convex.
  • Please note the correction to Exercise Sheet 5, Problem 2: We must assume that K is a pointed cone.
  • Corrected homeworks for sheets 2 and 4 can now be collected from the cupboard at the end of corridor MI 02.04 (through the glass door and immediately on the left).
  • Please note the room change for group 5 on Friday 13th July.

Dates of lectures/exercise classes and office hours

Type Day Time Room Teacher/Tutor first lecture Revision Class
Lecture Tuesday 16:15 - 17:45 MI HS 3 Taraz April 17  
Exercise group 1 Friday 12:15-13:45 MI 02.06.011 Cooley April 27 July 20, 12:15-13:45, MI 02.06.011
Exercise group 2 - - - - group cancelled  
Exercise group 3 Wednesday 10:15-11:45 MI 01.06.011 Cooley April 25 July 18, 10:15-11:45, MI 01.06.011
Exercise group 4 Wednesday 10:15-11:45 MI 01.06.011 Cooley May 2 July 18, 10:15-11:45, MI 01.06.011
Exercise group 5 Friday 14:15-15:45 MI 02.04.011 (MI 02.08.020 on 13.7.) Cooley May 4 July 20, 12:15-13:45, MI 02.06.011

Content of the course

  • Linear Diophantine systems of equations
  • Integer hulls and integer polyhedra
  • Cutting plane methods
  • Branch-and-Bound algorithms

Lecture notes

The course will roughly follow the outline of the course in previous years.

Mitschriften und Folien aus der Vorlesung

Datum Datei Themen
17.04.2012 lecture 1 0. Introduction
1. Linear Diophantine systems of equations: 0-1.2
24.04.2012 lecture 2 1. Linear Diophantine systems of equations:1.3-1.15
08.05.2012 lecture 3 1. Linear Diophantine systems of equations: 1.16-1.19
15.05.2012 lecture 4 2. Integer hulls and integer polyhedra: 2.1-2.10
22.05.2012 lecture 5 2. Integer hulls and integer polyhedra: 2.11-2.17
05.06.2012 lecture 6 2. Integer hulls and integer polyhedra: 2.18-2.24
12.06.2012 lecture 7 2. Integer hulls and integer polyhedra: Proof of 2.23, 2.25
19.06.2012 lecture 8 3. Hilbert bases and cutting plane methods: 2.26, 2.27, 3.1-3.6
26.06.2012 lecture 9, part 1 lecture 9, part 2 3. Hilbert bases and cutting plane methods: 3.4-3.13
03.07.2012 lecture 10 3. Hilbert bases and cutting plane methods: 3.14-3.19
10.07.2012 lecture 11 3. Hilbert bases and cutting plane methods: 3.20-3.25

Problem sheets

Problem sheets Comments Solution outlines Supplementary sheets
Sheet 1   Solutions 1
Sheet 2   Solutions 2  
Sheet 3   Solutions 3  
Sheet 4   Solutions 4  
Sheet 5   Solutions 5  
Sheet 6   Solutions 6  
Revision Sheet      

Cover Sheet for Homework:

Please print out the Cover Sheet, fill it out and attach it to the front of your homework before handing it in.

Grade Bonus for homework:

There will be a grade bonus on the final exam for consistent participation in the exercise classes. The regulations are as follows:
  • In order to be eligible for the grade bonus, you must be successfully registered to an exercise group in TUMOnline. A place on the waiting list is not sufficient.
  • If you make a reasonable attempt at 80% of the problems on the problem sheets, you will receive a bonus of one grade step on a successfully completed final exam (1.3 becomes 1.0, 1.7 becomes 1.3, 2.0 becomes 1.7 etc).
  • A reasonable attempt consists of a recognisable attempt at solving the problem mathematically. It need not necessarily constitute a correct solution. The marker will decide whether a question has been reasonably attempted.
  • Solutions to exercises must be handed in on time. The deadline for submission of exercises is determined by the exercise group to which you are registered in TUMOnline.
  • Multiple choice exercises do not count towards the 80% - only the regular exercise questions.
  • The grade on a failed exam (4.3, 4.7, 5.0) cannot be improved.
  • A 1.0 grade cannot be further improved.
  • The grade bonus applies to both exams (first and re-sit) in this semester. It does not apply to any Discrete Optimization exams in future semesters.

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 there be a written exam?
info Yes. Some information about the exams can be found under this link. We will inform you via this web-page as soon as the schedule of the exam is fixed.

question Do I have to register for the exam?
info Yes, you have to register via TUM-Online. A "how-to" can be downloaded here (pdf)

question Which auxiliary material am I allowed to use during the exam?
info None, except for writing utensils.

question Am I automatically signed in the repetition exam if I failed the first?
info No.

question How does the Homework system works for this exercises?
info As following:
  • You will get an exercise sheet every two weeks within your exercises class or via this web-page (see Exercise sheets).
  • Within the classes the exercises should be discussed within groups to get first drafts of ideas for solutions.
  • At home you should carefully write down full solutions in teams of 2 to 3 students.
  • After your class you have one week to finish your homework.
  • After finishing your homework you drop it in the "Discrete optimization"-marked letter box in the basement of the MI-building.
  • Please, write your full name and the number of your exercise class on your homework.
  • The corrected homework will be returned to you in the following exercise class.

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.