Infotech Oulu Graduate School

Introduction to Integer Programming

Lecturer: Professor Ondrej Cepek, Charles University, Prague, Czech Republic

Lectures: Monday 2nd - Friday 6th November 2009 at 9 - 12 a.m.

Exercises: Monday 2nd - Friday 6th November 2009 at 13 - 15 p.m.

Lectures and exercises:  on Monday, Tuesday and Friday in auditorium IT134, on Wednesday in auditorium IT133, and on Thursday in auditorium MN101A.

The course is worth 5 ects.

---

Course description

Aim of the course: This course is aimed at students of computer science and related fields. Its main objective is to teach the students how to formulate a real-life problem (in which the unknown quantities that have to be computed have a discrete nature) as an integer program and to give a short overview of main solving techniques. There are many commercial IP solvers which can successfully solve very large instances of important real-life problems. However, the key ingredient to such a successful use of a commercial package is a skill to formulate the problem “properly”, which in turn requires at least some knowledge of how the solver works (i.e. which solving techniques it uses). This course should provide a basic insight into these matters.

Syllabus: sorting algorithms, graph algorithms, divide and conquer algorithms, NP-hardness, approximation algorithms (see a more detailed syllabus and schedule below)

Grades: based on homework assignments and class participation

Textbook: L.A. Wolsey, Integer Programming

---

Detailed syllabus

Monday, November 2

• 3 hour lecture (Formulations): definition of an integer program, formulating IPs and binary IPs, mixed IPs, alternative formulations, ideal formulations.  Time 9 - 12. Auditorium IT134
• 2 hour exercise: formulating small “real-life” problems as IPs. Time 13 - 15. Auditorium IT134
• Homework Assignment 1

Tuesday, November 3

• 3 hour lecture (Optimality, Relaxations, Bounds): primal and dual bounds, LP relaxations, combinatorial relaxations, Lagrangian relaxations, duality.
  Time 9 - 12. Auditorium IT134.
• 2 hour exercise: computing primal and dual bounds for small IP formulations.
  Time 13 - 15. Auditorium IT134
• Homework Assignment 2

Wednesday, November 4

• 3 hour lecture (Well Solved Problems): properties of easy problems, IPs with totally unimodular matrices, minimum cost network flows, shortest paths, maximum s-t flows.
  Time 9 - 12. Auditorium IT133
• 2 hour exercise: proving unimodularity, getting an optimal solution for an IP problem using LP.
  Time 13 - 15. Lecture room IT133
• Homework Assignment 3

Thursday, November 5

• 3 hour lecture (Matchings and Assignments): augmenting paths and optimality, bipartite maximum cardinality matching, the assignment problem.
  Time 9-12. Auditorium MN101A
• 2 hour exercise: solving concrete matching and assignment problems.
  Time 13 - 15. Auditorium MN101A

Friday, November 6

• 3 hour lecture (Cutting Plane Algorithms): valid inequalities, addition of constraints, automatic reformulation, fractional cutting plane algorithm, mixed integer cuts.
  Time 9 - 12. Auditorium IT134
• 2 hour exercise: solutions to homework problems, discussion about the course.
  Time 13 - 15. Auditorium IT134

---

More information: Juha Kortelainen

---