Integer Optimization (Integer Programming) - Lecture Notes

Math 567 (Spring 2011)  -- Topics covered, and Lecture Notes on Integer Optimization

 Note to students: The scribes posted here are exactly what I write in class during the lecture. At the same time, they may not contain everything I say during the lecture! So, there are still plenty of reasons to come to class.

Scribes from all lectures so far (as a single big file)

Lec # Date Topic(s) Scribe
1 Jan 11 syllabus, linear programming overview, convex sets and functions, piecewise linear functions Lec 1 scribe
2 Jan 13 binary IP (BIP) and MIP formulations - assignment, knapsack, fixed charge, uncapacitated lot sizing Lec 2 scribe
3 Jan 18 piecewise linear function, conjunctive normal form (CNF), modeling with 0-1 and continuous variables Lec 3 scribe
4 Jan 20 big-M and sharp formulations of arbitrary disjunction, recession cone, b-MIP-r sets, formulation of a set Lec 4 scribe
5 Jan 25 graph, epigraph, & hypograph of functions, Farkas' lemma, projection of sets to x vars, projection cone Lec 5 scribe
6 Jan 27 Assumption 1 and 2, comparing formulations, sharp formulation, vertices being integral Lec 6 scribe
7 Feb  1 Examples of sharp formulations, traveling salesman problem (TSP), soubtours, node positions Lec 7 scribe
8 Feb  3 MTZ and subtour formulation for TSP, and their comparison, sharp formulation of a disjucntion Lec 8 scribe
9 Feb  8 projection to x of sharp formulation of disjunction, definitions and results on polyhedra Lec 9 scribe
10 Feb 10 more results on polyhedra, minimal faces and facets, introduction to AMPL Lec 10 scribe
11 Feb 15 discussion of Hw4 problems, capacitated lot sizing problem on AMPL Lec 11 scribe
12 Feb 17 integral polyhedra, unimodular and totally unimodular (TU) matrices and their equivalences Lec 12 scribe
13 Feb 22 sufficient condition for total unimodularity, LP duality, total dual integrality (TDI) Lec 13 scribe
14 Feb 24 results on TDI, 0-1 solution for dual of max-flow, generic branch-and-bound (B&B), details for ILP Lec 14 scribe
15 Mar  1 pruning in B&B by optimlaity, bound, infeasibility, full example of B&B on a 4-variable binary IP Lec 15 scribe
16 Mar  3 branching strategies - Best Node first (BNF) and Depth First Search (DFS), reduced cost fixing Lec 16 scribe
17 Mar  8 TSP project, binary, integer branching, branching on hyperplane, Jeroslow IP Lec 17 scribe
18 Mar 10 Chvatal-Gomory (CG), mixed integer rounding (MIR), mixed integer Gomory (MIG) cuts, knapsack covers Lec 18 scribe
19 Mar 22 knapsack covers, extension of a cover, lifting coefficients, separation problem Lec 19 scribe
20 Mar 24 example of separation problem, disjuctive cuts, Lovasz-Schrijver (LS) procedure for 0-1 IPs Lec 20 scribe
21 Mar 29 proof of Pj(K) = Qj(K), "lifting" an inequality, disjunctive convexification, disjunctive program (DP) Lec 21 scribe
22 Mar 31 a theoretical cutting plane algorithm, "good" and "bad" instances, a practical cutting plane algo, rank of cuts Lec 22 scribe
23 Apr  5 node-packing on complete graph, inequality of "size" k has LS-rank at most k-2, semidefinite relaxation Lec 23 scribe
24 Apr  7 receiver location problem, greedy and modified greedy heuristics, t-hard to cover meters, preprocessing Lec 24 scribe
25 Apr 12 full heuristic for setcovring, IP formulation, preprocessing on constraint matrix of IP, variants of setcovering Lec 25 scribe
26 Apr 14 p-median and p-center problems, binary search for p-center, greedy algo for p-median, absolute p-center Lec 26 scribe
27 Apr 19 local centers, condition for existence of local centers, network flow model for facility location Lec 27 scribe
28 Apr 21 ULS: xt s(t-1)=0 in optimality, shortest path formulation, path inequalities; insertion heuristics for TSP Lec 28 scribe
29 Apr 26 improvement heuristics for TSP, tours and Hamiltonian tours, double-tree heuristic, Christofides' algorithm Lec 29 scribe
30 Apr 28 savings algo for TSP, 2- and 3-opt exchanges, lattices, basis reduction and decomposable knapsacks Lec 30 scribe

Scribes from all lectures so far (as a single big file)

Back to the main course page