The lectures are no longer delayed to 11:00am. From now on they will start at 10:45am as usual.
Theoretical part: the ellipsoid method; flows in graphs and totally unimodular matrices; matroid optimization; total dual integrality; and if time permits, 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; Column generation.
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.
The exam will consist of a written exam on the theory (70%) and an assigment (30%). The exam will take place on monday 1/7 or tuesday 2/7 from 14:00---17:00, depending on the availability of a room (to be announced).
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.