Math 567 (Spring 2009) -- Topics covered, and Lecture Notes
| Lec # | Date | Topic(s) | Notes |
|---|---|---|---|
| 1 | Jan 13 | syllabus,overview of LP, graphical solution in 2D | |
| 2 | Jan 15 | convexity, intro to IP formulations | Lecture 2 |
| 3 | Jan 20 | uncapacitated lot sizing (ULS), piecewise linear functions | Lecture 3 |
| 4 | Jan 22 | modeling with 0-1 variables, CNF, modeling arbitrary disjunctions | Lecture 4 |
| 5 | Jan 27 | recession cones, b-MIP-r, epi- and hypo-graphs, projection, Farkas' lemma | Lecture 5 |
| 6 | Jan 29 | projection cone, comparison of formulations, sharp formulations | Lecture 6 |
| 7 | Feb 3 | TSP, Miller-Tucker-Zemlin (MTZ) and subtour formulations | Lecture 7 |
| 8 | Feb 5 | examples of sharp formulations, intro to AMPL | Lecture 8 |
| 9 | Feb 10 | Definitions and results on polyhedra | Lecture 9 |
| 10 | Feb 12 | faces, facets, pointed polyhdra, sharp formulation for general disjunction | Lecture 10 |
| 11 | Feb 17 | integral polyhedra, unimodularity and total unimodularity (TU) | Lecture 11 |
| 12 | Feb 19 | TU-ness of min-cost flow problem, total dual integrality (TDI) | Lecture 12 |
| 13 | Feb 24 | the Hiker's Tour Problem (HTP) - discussion of project | Project 1 |
| 14 | Feb 26 | generic branch-and-bound (B&B), pruning by bound, optimality, infeasibility | Lecture 14 |
| 15 | Mar 3 | B&B example, node selection strategies - BNF and DFS | Lecture 15 |
| 16 | Mar 5 | IP for sudoku, reduced cost fixing, binary and integer branching on variables and constraints | Lecture 16 |
| 17 | Mar 10 | Jeroslow's IP, Chvatal-Gomory cuts, mixed integer rounding (MIR), mixed integer Gomory (MIG) cuts | Lecture 17 |
| 18 | Mar 12 | Knapsack cover inequalities, minimal covers, lifting, separation problem | Lecture 18 |
| 19 | Mar 24 | Disjunctive cuts, Lovasz-Schrijver procedure, lift-and-project cuts for 0-1 IPs | Lecture 19 |
| 20 | Mar 26 | odd hole inequality, Disjunctive programming, facial disjunction, a theoretical cutting plane algo | Lecture 20 |
| 21 | Mar 31 | a practical cutting plane algo, rank of inequalities, semidefinite relaxation, vertex packing on Kn | Lecture 21 |
| 22 | Apr 2 | solving large IPs in practice, greedy & modified greedy heuristics for set covering, hard-to-cover meters | Lecture 22 |
| 23 | Apr 7 | heuristic for setcoving, variants of setcovering for facility location | Lecture 23 |
| 24 | Apr 9 | p-median & p-center problems, IP models, binary search, greedy heuristic, absolute p-center | Lecture 24 |
| 25 | Apr 14 | local centers, IP for ULS, min-cost flow and shortest path models for ULS, MATLAB tips for project 2 | Lecture 25 |
| 26 | Apr 16 | ULS: path inequalities, sharp formulation, multiple products case; multicommodity flow problem | Lecture 26 |
| 27 | Apr 21 | multicommodity flow - dis/aggregated formulations, tree partitioning - dynamic programming (DP) | Lecture 27 |
| 28 | Apr 23 | IPs hard for B&B, lattices, Shortest and closest vector problems (SVP, CVP), Gauss basis reduction in 2D | Lecture 28 |
| 29 | Apr 28 | Example for Gauss reduction, KZ and LLL reduction, Rangespace reformulation for IPs | Lecture 29 |