Menü

Discrete Optimization

### Vorlesung

 Lectures: Anusch Taraz 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.
• 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.

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

Will there be a written exam?
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.

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

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

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

How does the Homework system works for this exercises?
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.
• 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

Jan 25th, 2019
Case Studies 2019: Preliminary Meeting on Wed, Feb 6th, at 16:00 in room MI 03.06.011.