max planck institut
mpii logo Minerva of the Max Planck Society


Integer Programming, Winter 2014/2015

Andreas Karrenbauer

Time: Tuedays, 2:15 pm to 3:45 pm
First meeting: First Tuesday of the Winter 2014/2015 term, i.e., October 21.
Room: 024 on the ground floor of the MPI building (E1.4)
Prerequisites: Optimization core course
Content: Integer Programming is a powerful tool to model and solve optimization problems. You will learn how to model abstract and real-world problems as Integer Programs.
Credits: The course is worth 5 credit points, wich will be awarded for passing a final oral exam. There will be assignments due every other week, which consist of theoretical and practical exercises. These exercises will be graded and discussed in a tutorial. Admission to the final exam is subject to achieving 50% of the points over all assignments.
Textbook: Integer Programming by Laurence A. Wolsey.
Teaching assistant: Max John
Tutorial: Wednesday, 10-12, rotunda 3rd floor, every 2 weeks (first meeting Nov, 06)
News for students:
  • If you want to participate in the course, please register to our mailinglist and to HISPOS.
  • Tutorial slot has changed. We are meeting on Wednesday, 10-12 in the rotunda in the 3rd floor.
  • Date and place of the oral exam is fixed. Please find your personal slot in the mail I sent to you.
Handout: The slides of all lectures are condensed in the handout.
Scribe Notes: You can also gain points by writing lecture notes of single lectures. In order to do so, you have to use our template. You gain 40γ points for the notes of one lecture, hereby γ denotes the quality factor between 0 and 1. Please submit your notes by sending a zipped package that contains everything such that your tex code compiles and the pdf to Max not later than one week after the lecture that you took notes for.

Exam The exam will take place on Thursday, February 19, in room 309a of the MPII.
Date Topic References Homework Notes
Oct 21 Introduction to Integer Programming Chapter 1 in [W] Exercise Sheet 1 lp file Solution 1 Slides
Oct 28 Relaxation and Bounds Chapter 2 in [W] Slides
Nov 04 Integer Polyhedra Chapter 3 in [W] Exercise Sheet 2 pgm-file Solution 2 Slides
Nov 11 Total Unimodularity and Network Flows Chapter 3 in [W] Slides
Nov 18 Matchings and Assignments, Dynamic Programming Chapter 4,5 in [W] Exercise Sheet 3 Solution 3 Slides
Nov 25 Branch and Bound Chapter 7 in [W] Slides
Dec 02 Cutting Planes Chapter 8 in [W] Exercise Sheet 4 lp-file Solution 4 Slides
Dec 09 Cutting Planes Chapter 8 in [W] Slides
Dec 16 Strong Valid Inequalities Chapter 9 in [W] Exercise Sheet 5 Solution 5 Slides
Jan 06 Branch-and-Cut Chapter 9 in [W] Exercise Sheet 6 large-lp debug-lp Slides
Jan 13 Lagrangian Duality Chapter 10 in [W] Slides
Jan 20 Column Generation Chapter 11 in [W] Exercise Sheet 7 Slides
Jan 27 Heuristics Chapter 12 in [W] Slides
Feb 03 Semidefinite Programming Slides

More Courses of the Algorithms and Complexity Group