Math 583GB
Combinatorial Optimization

Rekha Thomas

Spring 2003, Monday/Wednesday 2:30-3:50

Combinatorial optimization is an active branch of mathematics that focusses on solving discrete optimization problems using techniques from combinatorics, linear programming, and polyhedral theory. This course will provide an overview of this subject area. Topics to be covered are:
  1. Basic polyhedral theory
  2. Linear Programming: revised simplex method, LP duality, sensitivity
  3. Complexity Theory: P vs. NP
  4. Integer Programming: Gomory's Cutting planes, Branch & Bound (Cut), Total unimodularity (transportation polytope)
  5. Min Cost Network Flow, Max Flow/Min Cut
  6. Travelling Salesman Problem (TSP): graph based heuristics (2-OPT, 4-OPT, Lin-Kernighan, local search), polyhedral combinatorics (facets, valid inequalities), Lagrangian relaxation
  7. MaxCut: SDP relaxation (approximation algorithm), LP relaxation (approximation algorithm)
  8. Matroid intersection: greedy algorithm, 2 matroid intersection (max weighted spanning tree)
  9. Topic du jour
Required book: Combinatorial Optimization, B. Korte and J. Vygen, Springer-Verlag, Berlin 2000. ISBN 3-540-67226-5

Other Recommended References:

  1. W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and A. Schrijver, Combinatorial Optimization, Wiley & Sons, 1998.
  2. G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, Wiley & Sons, 1988.
  3. L.A. Wolsey, Integer Programming, Wiley & Sons, 1998.