|News||Dates of lectures/exercise classes||Lecture notes||Problem sheets||Literature||FAQ|
- 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.
- 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 notesThe course will roughly follow the outline of the course in previous years.
- lecture notes of last year's course taught by Prof. Hemmecke
- Old lecture notes in German: these include a first chapter about complexity theory and NP-completeness.
|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||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|
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.
- 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 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?
- 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.