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 group project.
Assignments: 30%. (Three assignments, each worth 10%)
In-class Tests: 40%. (Two tests, each worth 20%)
-----> Tentatively planned(may change slightly): Test 1 on Feb. 27th, Test 2 on April 3rd.
Project: 30%.
Assignments:
- Assignment 1, you only need to solve 5 out of 8 problems, due date: Feb 13th.
- Assignment 2, will be out, due date: Mar. 13th.
- Assignment 3, will be out, due date: April 10th.
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)
Tentative topics:
- Polyhedra combinatorics and LP duality, integral polytopes, total unimodularity. (5-6 Lectures)
- General matching and matching polytopes. T-joins. (8 Lectures)
- Matroid theory: greedy and matroid intersection. (2-3 Lectures)
- Ellipsoid method, separation and optimization. (3 Lectures)
- Submodular optimization. (5 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. Here is the planned lecture list, subject to change.
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: Shrijver 2.2.
- Lecture 4: Farkas' Lemma, review of Linear programming: duality and complementary slackness. Totally unimodular matrices and integer polyhedron.
Reference: Shrijver 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:
- Lecture 6:
- Lecture 7:
- Lecture 8:
- Lecture 9:
- Lecture 10: