__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 during the lecture! So, there are still plenty of reasons
to come to class. everything I
say |

Scribes from all lectures so far (as a single

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 of sharp formulation of disjunction,
definitions and results on polyhedra
x | 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 P, "lifting" an
inequality, disjunctive convexification, disjunctive program (DP)
_{j}(K) = Q_{j}(K) | 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: x in optimality, shortest path formulation, path
inequalities; insertion heuristics for TSP
_{t} s_{(t-1)}=0 | 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

Back to the main course page

Last modified: Thu Apr 28 17:55:44 PDT 2011