Schedule for AMS 550.766: Combinatorial Optimization, Spring 2021.
Here is the schedule of lectures :
PART I: Combinatorial Algorithms for Classic Problems
Lecture 1 (1/26/2021): (Lecture slides, Lecture notes from class, Sections 3.1, 3.2 of "4-Bill book", Section 4.2 in Lex Schrijver's notes) What is Combinatorial Optimization? Motivating problems for Combinatorial Optimization (scheduling, transportation, astronomy, statistical/machine learning), Preliminaries on Graph theoretic terminology and run time of Algorithms, Definition and example of the maximum flow problem. Cuts and using cuts to upper bound flow.
Lecture 2 (1/28/2021): (Lecture notes from class, Sections 3.2, 3.3 of the "4-Bill book", Sections 4.2, 4.3 in Lex Schrijver's notes) Recap of maximum flow problem and example, Cuts and using cuts to upper bound flow, Flow incrementing/augmenting paths, Max Flow- Min Cut theorem, Theorem showing that max flow is reached if and only if no augmenting paths remain. 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. Application of flow: transportation problem, Military strategy problem (Problem 3.44 from the "4-Bill book").
Lecture 3 (2/2/2021): (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, 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.
Lecture 4 (2/4/2021): (Lecture notes from class, Sections 5.1, 5.2 of the "4-Bill book", Section 5.2 in Lex Schrijver's notes) 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. 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 5 (2/9/2021): (Lecture notes from class, Section 5.2 from the "4-Bill book", Sections 3.5, 5.1, 5.2 in Lex Schrijver's notes) Formal statement of Edmonds' Blossom algorithm for maximum matching.Proof of correctness of Edmonds' Blossom algorithm for maximum matching, Tutte-Berge formula as a consequence. 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 6 (2/11/2021): (Lecture notes from class, Sections 2.1, 2.2 and 2.3 from Lex Schrijver's notes, see also lines 288-358 in these notes) Convexity, Separating hyperplane theorem/Fundamental theorem of convexity in R^n, examples of convex sets: hyperplanes, halfspaces, Definition of polyhedra. Vertices/extreme points, convex hull. Rank theorem for characterizing vertices of polyhedra, Minkowski-Weyl theorem, Convex cones, Farkas' Lemma, deciding if a polyhderon is empty or not.
Lecture 7 (2/16/2021): (Lecture notes from class, Sections 2.3 and 2.4 from Lex Schrijver's notes, see also Section 2.5.2 in these notes) Nonnegative combinations of an inequality system, Valid inequalities/halfspaces, 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. Abstract combinatorial optimization problems, Faithful embeddings of combinatorial optimization problems, Philosophy of Polyhedral Combinatorics, Example: Matchings.
Lecture 8 (2/18/2021): (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") Linear Programming (LP) and Integer Programming (IP) formulations. IP formulation for matching, 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, 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. 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 9 (2/23/2021): (Lecture notes from class, Sections 25.1 and 25.2 in Lex Schrijver's "Combinatorial Optimization", Vol. A) Recap of LP/IP formulations of combinatorial optimization problems. 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. Reducing the general matching problem to the perfect matching problem.
Lecture 10 (2/25/2021): (Lecture notes from class, Additional notes on CG cuts, Sections 6.7, 6.8 from the "4-Bill book", Section 4.4 in in these notes, Section 5.2 and Chapter 7 from this book) A crash course on the Ellipsoid algorithm ignoring many technical details, Solve LPs with polynomial number of calls to separation oracles, equivalence of optimization and separation (up to polynomial factors). Cutting plane method for solving integer programs; Using combinatorial insight to get cutting planes for integer programs modeling combinatorial optimization problems, examples: odd-set inequalities for matching, clique inequalities for stable set, cover inequalities for knapsack problems, Introducing Chvatal-Gomory cutting planes as a "non-combinatorial" way of getting cutting planes; convex hull of integer points in a rational halfspace, explicit formula for Chvatal-Gomory cutting plane using nonnegative multipliers; Chvatal-Gomory cutting plane sequence/proof.
Lecture 11 (3/2/2021): (Lecture notes from class, Section 6.7 from the "4-Bill book", Section 5.2 from this book, Section 2.5 in these notes) Recap of definition of Chvatal-Gomory cutting planes, CG sequences; definition of CG proof. Statement of completeness of Chvatal-Gomory procedure. Tools: Dimension of polyhedra, Faces of polyhedra. Rotating CG cut for face into a CG cut for the full polyhedron. Proof of infeasibility certificate of integer points in a polytope using CG cutting planes.
Lecture 12 (3/4/2021): (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. Proof of polyhedrality of the Chvatal-Gomory closure. Chvatal-Gomory closure and rank. Branch and bound (BB). The notion of CG proofs and BB proofs of optimality. Lower bounds on proof sizes giving lower bounds on efficiency of cutting plane or BB algorithms.
Lecture 13 (3/9/2021): (Lecture notes from class, Sections 1.2, 9.2, 5.1, 5.5 from this book): Branch and bound, Branch and Cut, Valid disjunctions, branching and cutting planes from general valid disjunctions, Cut generating linear programs (CGLP). Review of the Simplex Method for LP, Gomory's fractional cuts.
Lecture 14 (3/11/2021): (Lecture notes from class, Sections 1.2.2, 5.2.4, 5.2.5 from this book, see also the surveys here and here, and the papers here and here) Cut generating functions as generalizations of Gomory's fractional cuts. General discussion of cutting plane paradigms, branching schemes and branch-and-cut based on pairs of cutting plane paradigms and branching schemes. Discussion of complexity of pure cutting plane algorithms and pure branch-and-bound based on variable disjunctions. 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 14 continued (3/11/2021): (Lecture notes from class, LaTex lecture notes, Section 9.1 from this book): Lattices: basic definitions and examples, Theorem for the existence of a basis of a lattice.
Lecture 15 (3/16/2021): (Lecture notes from class, LaTex lecture notes, Section 9.1 from this book, and this book): Unimodular matrices connecting two bases, determinant of a lattice, Discussion of shortest vector problem and orthogonal/almost orthogonal bases, Orthogonality defect. Gram-Schmidt orthogonolization, Hadamard inequality showing defect is at least 1, Elementary column operations for bases and corresponding matrices, Normalization of a basis, Statement of Lovasz-Lenstra-Lenstra (LLL) algorithm.
Lecture 16 (3/18/2021): (Lecture notes from class, LaTex lecture notes, Section 9.1 from this book, and this book): Proof of correctness and running time of the Lovasz-Lenstra-Lenstra (LLL) algorithm. Convex Integer Optimization and high level discussion of Lenstra's branch-and-bound algorithm; Lowner-John ellipsoidal approximations, Using the ellipsoid algorithm to compute approximate Lowner-John ellipsoids.
Lecture 17 (3/23/2021): (Lecture notes from class, LaTex lecture notes, Section 9.1 from this book, and this book, Micciancio-Voulgaris CVP/SVP algorithm): Lenstra's algorithm for general convex integer optimization using ellipsoidal approximations and reduced lattice basis. Dual lattices, Flatness theorem. Short discussion of closest lattice vector problem (CVP) as special case problems with more efficient specialized algorithms running in single expoenntial time. Conjectured single exponential complexity for general problem. Equivalence of finding the lattice width of a sphere and the shortest non-zero lattice vector problem (SVP). Improving 2^O(n^3) to 2^O(n log n) using 2^O(n) algorithms for CVP and SVP.
Lecture 18 (3/25/2021): (Lecture notes from class, Micciancio-Voulgaris CVP/SVP algorithm): 2^{O(n)} algorithms for CVP and SVP.