COMP/MATH 552 : Combinatorial Optimization

Instructor: Yaqiao Li

Contact: yaqiao dot li at mail dot mcgill dot ca

Office Hours: Monday 3:00 - 4:00 pm, or by appointment

Office: McConnell 303

Term: Winter 2018, Jan. 08 - Apr. 16.

Lectures: Tuesdays and Thursdays 08:35 - 09:55 am in McConnell 103

Study Break: March 5 - 9, no lectures.

Teaching Assistant: Mashbat Suzuki

Contact: mashbat dot suzuki at mail dot mcgill dot ca

Office Hours: Thursday 11:00 am - 1:00 pm.

Office: McConnell 303

Course outline

Prerequisites:

Math 350 (Graph theory and Combinatorics) or COMP 362 or equivalent. This course is intended for graduate students and senior undergraduate students in math or computer science.
The main prerequisite is mathematical maturity, with basic knowledge in graphs and linear algebra. The exposure to some algorithms (e.g. shortest path, minimal spanning tree, bipartite matching, max flow - min cut) is preferable, though not essentially required. It is important that you feel comfortable or are ready to work with rigorous mathematical reasoning.

Course description:

Combinatorial optimization is a branch of mathematics that studies optimization over a finite set that usually can be described by a graph or other combinatorial object. It has wide application in sciences and engineering.
This is an introductory course on combinatorial optimization. Our focus will NOT be on modelling practical problems, but on structure and theory behind those problems and algorithms. The course mainly consists of: polyhedral combinatorics and application in general matching theory; matroids; equivalence of optimization and separation; and submodular optimization. A recurring theme in this course is to see individual problems are unified in general theory.
See tentative topics for things that are planned to be covered. Topics (certainly also interesting and important!) that won't be covered include but not limited to: heuristic algorithms, approximation algorithms, semidefinite programming, complexity, etc.

Evaluation:

There are no formal mid-term or final exams. Evaluation will be made through assignments, in-class tests and a final project.
Assignments: 30%. (Three assignments, each worth 10%)
In-class Tests: 40%. (Two tests, each worth 20%) : Test 1 on Feb. 22nd, Test 2 take home.
Project: 30%.

Assignments:

Assignment 1, due date: Feb 13th.
Assignment 2, due date: Mar. 13th.
Assignment 3, due date: April 10th.

Projects:

On the history of combinatorial optimization (till 1960). A. Schrijver;
Polyhedral Combinatorics and Combinatorial Optimization. A. Schrijver
Strongly Polynomial and Combinatorial Algorithms in Optimization. E. Tardos. ICM 1990.
Combinatorial Optimization: A Survey. M. Grotschel and L. Lovasz. 1993.
Semidefinite Programming and Combinatorial Optimization. M. Goemans. Mathematical Programming 1997.
[claimed by Ying Jie Qian] A short proof of the Berge - Tutte Formula and the Gallai - Edmonds Structure Theorem. D.West. European J. Combin. 2011.
Maximum matchings via Gaussian elimination. M. Mucha and P. Sankowski. FOCS 2004
[claimed by Harsh Singh] The primal-dual method for approximation algorithms and its application to network design problems. M. Goemans and D. Williamson. 1997.
Note: this is a book chapter, you can choose some parts from it to present.
Matching, matroids, and extensions. W. Cunningham. Mathematical programming 2002
[claimed by Johannes Brustle] Smallest compact formulation for the permutahedron. M. Goemans. Math. Program. 2015.
Exponential Lower Bounds for Polytopes in Combinatorial Optimization. S. Fiorini, S. Massar, S. Pokutta, H. Raj Tiwary, and R. de Wolf. J. ACM 2015.
The matching polytope has exponential extension complexity. T. Rothvoss. J. ACM 2017.
Variations For Lovasz' Submodular Ideas. K. Berczi and A. Frank. 2008.
A simple combinatorial algorithm for submodular function minimization. S. Iwata and J. Orlin. SODA 2009.
[claimed by Gautam Rayaprolu] A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint. Yuval Filmus and Justin Ward. FOCS 2012.
Flows, Cuts and Integral Routing in Graphs - an Approximation Algorithmist's Perspective. J. Chuzhoy. ICM 2014.
0/1 Polytopes with Quadratic Chvatal Rank. T. Rothvoss and L. Sanita. OR 2016.
[proposed by Salomon Bendayan] "Neural" computation of decisions in optimization problems. JJ Hopfield and David W. Tank. Biological cybernetics, 1985.
Artificial neural networks for combinatorial optimization. Potvin, Jean-Yves and Smith, Kate A. Handbook of metaheuristics 2003.
[proposed by Bobak Hamed-Baghi] Maximum matchings via Gaussian elimination. M. Mucha and P. Sankowski. FOCS 2004.

Course references:

There is no one single text book. The main references will be the following (increasing level) together with other materials that will be issued with the lectures.

A Course in Combinatorial Optimization by A. Schrijver. (A concise write up)
Combinatorial Optimization by W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver. (Recommended. You can buy it from McGill bookstore)
Combinatorial Optimization by B. Korte and J. Vygen. (Discussed many concrete problems)
Geometric algorithms and combinatorial optimization by M. Grotschel, L. Lovasz, and Alexander Schrijver. (Great book! Maybe you can find it online)
Some open problems in combinatorial optimization.

Topics:

Polyhedra combinatorics and LP duality, integral polytopes, total unimodularity. (5-6 Lectures)
General matching algorithms and matching polytopes. (5-6 Lectures)
Extension complexity. (2 Lectures)
Matroid theory: greedy and matroid intersection. (2-3 Lectures)
Submodular functions and optimization. (3 Lectures)
Ellipsoid method. (1-2 Lectures)

It should be noted that the topics are subject to change depending on the interest of the audience, and longer or shorter treatment of specific topics.

Lectures:

Lecture 1: Course overview.
Reading material(for fun, you can find them online): 1. On the history of combinatorial optimization (till 1960), by A. Schrijver; 2. Combinatorial Optimization: A Survey, by M. Grotschel and L. Lovasz.
Lecture 2: Convex set, hyperplane separation theorem, definition of a polyhedron, vertices of a polyhedron, characterization of vertices.
Reference: Schrijver, 2.1, 2.2.
Lecture 3: Proved bounded polyhedron is equivalent to a polytope. The proof used hyperplane separation and polar.
Reference: Schrijver 2.2.
Lecture 4: Farkas' Lemma, review of Linear programming: duality and complementary slackness. Totally unimodular matrices and integer polyhedron.
Reference: Schrijver 2.3, 2.4. 8.1, 8.2. CCPS appendix on LP.
Reading (for fun): Three Puzzles on Mathematics, Computation, and Games. This is the ICM 2018 plenary lecture by Gil Kalai.
Lecture 5: Hoffman-Kruskal theorem. Examples of totally unimodular matrices: incidence matrices of bipartite graphs, incidence matrices of directed graphs, network matrices. Seymour's theorem: network matrices are (roughly) building blocks of totally unimodular matrices. Totally unimodularity can be checked in polytime.
Reference: Schrijver 8.2, 8.3, 8.4, CCPS 6.5.
P.Seymour's paper: Decomposition of regular matroids, J. Comb. Theory, Series B, 1980.
Lecture 6: Proved Tutte's theorem: network matrices are totally unimodular. Derive max-flow-min-cut using totally unimodular incidence matrices of directed graphs. Some basic notions: max independent set, min vertex cover, max matching, min edge cover. Gallai's theorem: sum of max matching and min edge cover equals to the number of vertices of a connected graph. Bipartite matching polytope and its description as a polyhedron.
Reference: CCPS 6.5., Schrijver 8.3, 8.4.
Lecture 7: Derive Konig's theorem using LP and bipartite graph's incidence matrix is totally unimodular: min-max formula for max matching in bipartite graphs. Fundamental theorem of matching due to Berge: if a matching M is not maximal then there exists M-augmenting path. 1st proof of Tutte-Berge (due to Lovasz): min-max formula for max matching of general graphs.
Reference: Schrijver 3.2, 5.1, 8.3. CCPS 5.1.
Lecture 8: Shrinking odd cycles: 2nd proof of Tutte-Berge.
Reference: CCPS 5.1.
Lecture 9: Comparison of two proofs of Tutte-Berge. Edmonds' blossom algorithm for perfect matching and maximal matching of general graphs.
Reference: CCPS 5.2.
Lecture 10: Primal-dual algorithm (Hungarian algorithm) for minimal weight perfect matching of bipartite graphs. Edmonds' characterizations for perfect matching polytopes and matching polytopes of general graphs.
Reference: CCPS 5.3.
Lecture 11: Reduction of the max-weight matching into max-weight perfect matching.
Introduction of extension complexity. Examples: permutahedron and spanning tree polytope both have compact formulation. Matching polytope and Travelling salesman polytope both have exponential extension complexity. Yannakakis' theorem: extension complexity of a polytope equals to the nonnegative rank of the slack matrix.
Reference: CCPS 5.3 for max-weight matching.
Lecture notes for extension complexity, and you can check references therein.
Lecture 12: Complete the proof of Yannakakis' theorem.
Introduction of matroids, basic examples, matroids are the structure behind the greedy algorithm.
Reference: For proof of Yannakakis' theorem, see previous lecture note. For matroids, see Schrijver 10.1, 10.3.
Lecture 13: Edmonds' matroid intersection theorem: max-cardinality independent set in the intersection of two matroids can be found in polytime, and there is a duality characterization of the max-cardinality in terms of ranks of matroids.
Reference: Schrijver 10.4, 10.5.
Lecture 14: Test 1.
Lecture 15(by Mashbat): Introduction to SDP, 1/2 Approximation to Max Cut. Analysis of Goemans-Williamson algorithm.
Reference: Mash's notes 1.
Lecture 16(by Mashbat): Application of SDP.
Reference: Mash's notes 2.
Lecture 17: Two equivalent definitions of submodular functions, concavity, basic examples. Matroids and their rank functions.
Reference: Lecture notes.
Lecture 18: Three ways to define Lovasz extension: expectation, its analytic expansion, and optimal value of an LP over the base polyhedron. submodularity and convexity. Maximizing a monotone submodular function with a cardinality constraint: greedy algorithm gives (1-1/e)-approximation.
Reference: Lecture notes.
Lecture notes by Alejandro Toriello on Lovasz extension and base polyhedron;
Lecture notes by Pravesh Kothari on Lovasz extension;
Lecture notes by Yaron Singer on greedy algorithm.
Lecture 19: Multilinear extension and continuous greedy algorithm for monotone submodular welfare maximization achieving (1-1/e)-approximation.
Reference: Lecture notes by Yaron Singer.
[Original paper] Optimal approximation for the submodular welfare problem in the value oracle model. Jan Vondrak. STOC 2008.
Lecture 20: Ellipsoid method.
Reference: Lecture notes by Pravesh Kothari.
[book] Geometric algorithms and combinatorial optimization. M. Grotschel, L. Lovasz, and Alexander Schrijver.
Lecture 21: guest lecture by Bruce Reed.
Reference: Lecture notes 1 on perfect graphs and Shannon capacity. Lecture notes 2 on GLS algorithm for optimizing over perfect graphs.
Lecture 22: presentation by Gautam Rayaprolu and Bobak Hamed-Baghi.
Lecture 23: presentation by Ying Jie Qian.
Lecture 24: presentation by Johannes Brustle.
Lecture 25: presentation by Salomon Bendayan.
Lecture 26: presentation by Harsh Singh.