# Integer programming and polyhedral combinatorics (2WO06)

## News

The lectures are no longer delayed to 11:00am. From now on they will start at 10:45am as usual.

## Contents of the course.

Theoretical part: the ellipsoid method; flows in graphs and totally unimodular matrices; matroid optimization; total dual integrality; Lenstra's method for integer programming in finite dimension.

Applied part: using a MIP solver; the Chvatal hull; Cutting plane methods; Lagrange duality and decomposition.

We use the book `Optimization over Integers', by Bertsimas and Weismantel (Dynamic Ideas 2005, ISBN 0-9759146-2-6). The book can be ordered here.

## Examination

The exam will consist of a written exam on the theory (70%) and assigments (30%). The resit of the exam will take place on thursday 15/8 from 14:00---17:00, in MF 5.104B.

Many people have experienced difficulties using Sage on a Windows machine in a virual box. Bart Post has shared the solutions he found in this document. Thanks Bart!

The deadline for handing in the assignments is either sunday 7 juli 2013 at 18:00 or sunday 11 august 2013 at 18:00. I will check the assigments handed in before the first deadline immediately after the deadline and also given a bonus for the best solution. Those that hand in for the second deadline will have to wait until the week following 11 august for their final grade, and there will be no bonus for those assignments.

## Homework & Assignments

Section and exercise numbers refer to the book by Bertsimas and Weismantel.

Week 1: introduction. Slides. If necessary, review the LP duality theorem and the relation between polytopes and polyhedra (see e.g. this syllabus). Part 1: read section 3.4. Homework: Derive Edmonds' theorem. Part 2: read section 1.1. Homework: exercises 1.2, 1.5. See the concorde website for a history of the travelling salesman problem (and more).

Week 2: the ellipsoid method. Slides. Homework: see slides. To catch up on positive definite matrices and polyhedra, see the syllabus.

Week 3: the matroid polytope. Slides. Homework: see slides. We use course notes by Lex Schrijver found here.

Week 4: matroid intersection. Slides. Homework: see slides.

Week 5: Totally unimodular matrices. Slides. Homework: see slides.

Week 6: Total dual integrality. Slides. Homework: see slides.

Week 7: Lagrange duality. Slides. Homework: see slides.

Week 8: SAGE MILP instruction. Here is some TSP data. Assignment 1 is to write a SAGE worksheet that solves these TSP problems to optimality, or (for the larger problems) to find best possible lower and upper bounds.

Week 9: Cutting planes and the Chvatal closure. Slides. Homework: see slides.

Week 10: Branching and Khinchine's Theorem. Slides. Homework: see slides, and this syllabus. Here is Assignment 2.

Week 11: Lattice reduction and ILP. Slides. Homework: see slides.

Week 12: Exam tutorial. Here is a test exam.