Schedule for AMS 553.766: Combinatorial Optimization, Spring 2022.
Here is the schedule of lectures :
PART I: Combinatorial Algorithms for Classic Problems
Lecture 1 (1/25/2022): (Lecture slides, Lecture notes from class) What is Combinatorial Optimization? Motivating problems for Combinatorial Optimization (scheduling, transportation, astronomy, statistical/machine learning), Preliminaries on graph theoretic terminology and complexity of algorithms.
Lecture 2 (1/27/2022): (Lecture notes from class, Sections 3.1, 3.2 of the "4-Bill book", Sections 4.2, 4.3 in Lex Schrijver's notes) Definition of maximum flow problem, Cuts and using cuts to upper bound flow, Flow incrementing/augmenting paths, Statement of Max Flow--Min Cut theorem.
Lecture 3 (2/1/2022): (Lecture notes from class, Section 3.2 of the "4-Bill book", Sections 4.2, 4.3 in Lex Schrijver's notes) Theorem showing that max flow is reached if and only if no augmenting paths remain. Consequences: Proof of Max Flow = Min Cut theorem, Integrality of max flow when capacities are integral, The "naive" augmenting path algorithm. Bad example for showing "naive" augmenting path algorithm can take exponential (in the data) steps. Applications of flow: transportation problem, Military strategy problem (Problem 3.44 from the "4-Bill book").
Lecture 4 (2/3/2022): (Lecture notes from class, Write-up, Sections 4.4, 3.1 in Lex Schrijver's notes, Section 5.1 of the "4-Bill book") Shortest Augmenting path algorithm, Proof of O(nm^2) run time for the shortest augmenting path algorithm (see this write-up for some of the details. This write-up is inspired by Lex Schrijver's proof on page 66 of these notes). Introducing the maximum matching problem, Matchings and Vertex covers.
Lecture 5 (2/8/2022): (Lecture notes from class, Sections 3.2, 3.4 in Lex Schrijver's notes, Section 5.1, 5.2 of the "4-Bill book") Curse of the odd cycle, Bipartite graphs, Apply Max flow-Min Cut to solve maximum matchings and minimum vertex covers in bipartite graphs and prove Konig's theorem. Matchings for general graphs, M-alternating paths, M-augmenting paths, M-augmenting path theorem for maximum matchings in general graphs, Motivation of M-alternating trees as a search tool for M-augmenting paths.
Lecture 6 (2/10/2022): (Lecture notes from class, Sections 5.1, 5.2 of the "4-Bill book", Section 5.2 in Lex Schrijver's notes) Developing the tools for Edmonds' Blossom algorithm for maximum matching in non-bipartite graphs: M-alternating trees, Shrinking odd cycles, Expanding matchings from a contracted graph.
Lecture 7 (2/15/2022): (Lecture notes from class, Section 5.2 from the "4-Bill book", Sections 5.1, 5.2 in Lex Schrijver's notes) Formal statement of Edmonds' algorithm for maximum matching in general graphs. Proof of correctness of Edmonds' algorithm, Tutte-Berge formula.
Lecture 8 (2/17/2022): (Lecture notes from class, Section 3.5 in Lex Schrijver's notes) Interpreting the max flow based bipartite matching algorithm (cardinality version) in terms of M-augmenting paths. Hungarian Method for weighted bipartite matching. Running time discussion of max flow and matching algorithms. Discussion of weighted combinatorial optimization problems: minimum cost flow, maximum weighted matching in general graphs.
PART II: Polyhedral Combinatorics
Lecture 8 (2/17/2022) continued: (Lecture notes from class, Section 2.1 from Lex Schrijver's notes) Convexity, examples of convex sets: hyperplanes, halfspaces. Separating hyperplane theorem/Fundamental theorem of convexity in R^d, Expressing closed, convex sets as intersections of halfspaces.
Lecture 9 (2/22/2022): Lecture canceled.
Lecture 10 (2/24/2022): (Lecture notes from class, Section 2.2 from Lex Schrijver's notes, see also Sections 2.1 and 2.2 in these notes) Definition of polyhedra. Vertices/extreme points. Rank theorem for characterizing vertices of polyhedra. Affine independence, dimension of convex sets. Convex combinations and convex hulls.
Lecture 11 (3/1/2022): (Lecture notes from class, Section 2.3 from Lex Schrijver's notes, see also Sections 2.3.1 and 2.5.2 in these notes) Minkowski-Weyl theorem, Convex cones, Farkas' Lemma, deciding if a polyhderon is empty or not, Nonnegative combinations of an inequality system, Valid inequalities/halfspaces.
Lecture 12 (3/3/2022): (Lecture notes from class, Sections 2.3 and 2.4 from Lex Schrijver's notes, see also Section 2.5.2 in these notes) Equivalence of valid inequalities and nonnegative combinations (characterization of valid inequalities for polyhedra). Linear programming (LP), Vertex solutions to Linear Programs, motivating the dual linear program, weak duality. Proof of strong duality for linear programs. Preliminary discussion of algorithms for linear programming: simplex methods, ellipsoid/cutting plane type methods and interior point methods.
Lecture 13 (3/8/2022): (Lecture notes from class, Sections 8.1, 8.2 from Lex Schrijver's notes, Sections 6.1, 6.2, 6.5 from the "4-Bill book") Abstract combinatorial optimization problems, Faithful embeddings of combinatorial optimization problems, Philosophy of Polyhedral Combinatorics, Example: Matchings, Linear Programming (LP) and Integer Programming (IP) formulations. IP formulation for matching is not necessarily LP formulation: triangle graph has non integer vertex. Totally unimodular matrices. Vertices are integral for totally unimodular constraint matrices A, Transformations that preserve the totally unimodular property.
Lecture 14 (3/10/2022): (Lecture notes from class, Sections 8.1, 8.2, 8.3 from Lex Schrijver's notes, Section 6.5 from the "4-Bill book") Transformations that preserve the totally unimodular property. Linear programs and their duals with TUM constraint matrices. Bipartite matching polytope/TU-ness of incidence matrix of bipartite graph, intepret dual LP as the vertex cover problem, use TU-ness and LP duality to prove Konig's theorem: max-matching = min vertex cover for bipartite graphs.
Lecture 15 (3/15/2022): (Lecture notes from class, Section 8.4 from Lex Schrijver's notes, Section 6.5 from the "4-Bill book") Understanding the max flow LP, TU-ness of matrices with at most one +1 and one -1 in each column, use TU-ness and integrality of optimal solutions to get min cut from dual of max flow LP, use LP duality to derive max flow-min cut.
Lecture 16 (3/17/2022): (Lecture notes from class, Sections 25.1 and 25.2 in Lex Schrijver's "Combinatorial Optimization", Vol. A) Non-bipartite matching. Statement of matching polytope theorem that gives an LP formulation of the matching problem. Perfect matchings. Statement and proof of perfect matching polytope theorem.
Lecture 17 (3/29/2022): (Lecture notes from class, Sections 25.1 and 25.2 in Lex Schrijver's "Combinatorial Optimization", Vol. A) Finishing the proof of the perfect matching polytope theorem. Reducing the general matching problem to the perfect matching problem. Discussion of the exponential number of constraints in the LP formulation of matching using odd set inequalities.
Lecture 18 (3/31/2022): (Lecture notes from class, Section 4.4 in in these notes) A crash course on the Ellipsoid algorithm ignoring many technical details, Solve LPs with polynomial number of calls to separation oracles: reducing optimization to feasibility and solving feasibility using separation oracles.
Lecture 19 (4/5/2022): (Lecture notes from class, Section 6.7 from the "4-Bill book", Section 5.2 from this book) Recap of polyhedral combinatorics, LP and IP formulations. Discussion of obtaining an LP formulation from an IP formulation. Explicit formula for convex hull of integer points in a rational halfspace, Chvatal-Gomory cutting planes.
Lecture 20 (4/7/2022): (Lecture notes from class, Sections 6.2, 6.7 from the "4-Bill book", Sections 3.8, 5.2 from this book, Section 2.5.3 in these notes) Recap of definition of Chvatal-Gomory cutting planes. Proof of polyhedrality of the Chvatal-Gomory closure, Chvatal-Gomory closure, Sequences of CG cutting planes and relation to iterated CG closures. Statement of completeness of Chvatal-Gomory procedure and overall proof idea. Polyhedral geometry tools: faces of polyhedra, complementary slackness.
Lecture 21 (4/12/2022): (Lecture notes from class, Section 6.7 from the "4-Bill book", Section 5.2 from this book) Chvatal-Gomory rank of an inequality, Chvatal-Gomory cutting plane proof of an inequality, Rotating CG cutting plane for face to a CG cutting plane for the original polyhedron. Formal statement of the completeness of the CG procedure.
Lecture 22 (4/14/2022): (Lecture notes from class, Section 6.7 from the "4-Bill" book, Sections 1.2, 5.2 from this book) Proof of completeness of Chvatal-Gomory procedure. Disjunctions and Branch-and-cut.
Lecture 23 (4/19/2022): (Lecture notes from class, Sections 1.2, 9.2, 5.5 from this book): Branch-and-cut, branching and cutting planes from general valid disjunctions, Cut generating linear programs (CGLP). Cutting plane paradigms, branch-and-cut based on pairs of cutting plane paradigms and family of disjunctions. Discussion of complexity of branch-and-cut. High level discussion of Lenstra's branch-and-bound algorithm based on general split disjunctions for solving integer programs in polynomial time in fixed dimension.
PART III: Algorithmic geometry of numbers
Lecture 24 (4/21/2022): (Lecture notes from class, Section 9.1 from this book): Building the tools for Lenstra's algorithm: Robust version of volume reduction lemma for the ellipsoid algorithm; Lattice width of convex sets and Khinchine's flatness theorem; Norms and quadratic norms from positive definite matrices, correspondence between ellipsoids and quadratic norms, Closest Vector and Shortest Vector Problems; Volume lower bound on convex hull of integer points spanning R^n. Statement of Lenstra's algorithm.
Lecture 25 (4/26/2022): (Lecture notes from class, Section 5.2 of this survey): Discussion of Lenstra's algorithm and its running time assuming algorithms for CVP and SVP, Reducing the computation of lattice to a shortest vector problem, Transformations leading to the definition of a general lattice, restating CVP and SVP in terms of general lattices and standard Euclidean norm.
Lecture 26 (4/28/2022): (Lecture notes from class, Micciancio-Voulgaris CVP/SVP algorithm): Short discussion of lattice bases and reduced bases, Voronoi cells, 2^{O(n)} algorithms for CVP and SVP.