Integer Programming (01:711:465)
Spring 2009
Time: Tuesdays and Fridays, 10:20-11:40 AM
Place: RUTCOR 139
Course webpage: http://rutcor.rutgers.edu/~dpapp/465.html
Instructor: David Papp
E-mail: dpapp at rutcor followed by dot rutgers dot edu
Please include the course number in the subject line of emails.
Office hours: Regular office hours: TBA, at RUTCOR 143.
(Check the campus map to find the building.)
I'm frequently available by appointment, too.
Announcements
- Homework 2 is posted, see below.
Class materials
January 20.
- Introduction: definition of an integer program (IP), mixed IP, and binary IP.
- LP vs IP. Recap: convex functions, convex sets, convex polyhedra.
- Simple IP models. The knapsack problem, the assignment problem, and modelling fixed charge.
January 23.
- More IP models: facility location, lot sizing, etc.
- Modelling logical constraints.
- Recommended reading: Wolsey, Ch. 1 in its entirety. (We covered more in class!)
January 27.
- More IP models: the Travelling Salesman Problem (3 formulations).
- Alternative formulations. The integer hull vs. the convex hull. Best possible formulations.
- Recommended exercises: Wolsey, Ch. 1, Problems 1, 2, 3, 4, 5, 10, 14.
January 30.
- More on alternative formulations. Comparison of formulations for the problems already discussed.
February 3.
- A crash course on Complexity Theory: optimization vs. decision problems; P, NP, NP-complete problems
- Efficient separation vs. efficient optimization: the ellipsoid method.
- HOMEWORK 1: Wolsey, Ch. 1, Problems 1, 2, 4, 10, 14. Deadline: Tuesday, February 10.
February 10.
- Total unimodularity.
- Operations preserving the TU property.
- Characterizations and recognition of TU matrices.
- IPs and LPs with TU matrices.
February 13.
- Combinatorial applications of total unimodularity.
- Networks and network flows. Minimum cost flows, maximum flows.
- The integrality lemma of network flows, and its proof using total unimodularity.
- Maximum matching and minimum vertex cover in bipartite graphs. Konig's Theorem.
- Alternative methods of proving integrality of polytopes.
February 17.
- The greedy algorithm. Matroids and submodularity.
- Recommended reading: Wolsey Chapters 2 and 3.
- HOMEWORK 2 is posted here. Deadline: February 24, Tuesday.
Email me here: dpapp at rutcor followed by dot rutgers dot edu
Please include the course number in the subject line of emails.