UBC Combinatorial Optimization CPSC 536S, Winter term 1, 2022
Course Outline
We give a thorough introduction to the field of combinatorial optimization. The course follows the `polyhedral approach' to combinatorial optimization. We begin with an introduction to polyhedral combinatorics which is then the theme for designing algoirithms for combinatorial problems. We will sample topics from classical combinatorial optimization problems including minimum cost arborescence, maximum weight matching, T-joins, matroid intersection, perfect matrices and virtual private network problem. We also expect to devote some time to approximation algorithms for problems such as the travelling salesman problem and maximum cut.
The course will be more theoretically focused as opposed to numerical. Hence a reasonable mathematical background (say in linear algebra) is recommended.
Instructor
Bruce Shepherd Email: fbrucesh@cs.ubc.ca Webpage: bshepherd.ca Office hours: Tuesday (1:30-3:00). Or by appointment (zoom or in-person possible).
Lectures
Time: Monday and Wednesday at 1:00 - 2:30 Orchard Commons 4068
Teaching Assistant
Abner Turkieltaub Office hours: Wednesdays 11:30-12:30. Or by appointment (zoom or in-person possible)
Grading
Course grades will be based upon: 4 assignments (15% each); last assignment during exam period, 3 in-class quizzes (10% each), 2 in-class semi-surprise quizzes (5% each).
Quiz Dates.
last Wednesdays of September, October, November
What we've done so far
Week 1.
Wednesday
Polyhedra Approach for Solving Generic Combinatorial Optimization Problems.
Background reading:
- For graph theory: Bondy and Murty
- Primer on Complexity Theory.
Week 2.
Monday
A Combinatorial Min-Max Theorem for Shortest Paths. Detecting negative cycles in Undirected versus Directed networks.
Wednesday
- Network Design Problems. Connectivity in Directed Graphs: branchings and arborescences.
- Structure of branchings and arborescences.
- Reductions between minimum arborescences and maximum branchings
- Overview of Algorithm for maximum branching. (Reading: Korte-Vygen).
Background reading:
- Korte-Vygen.
Week 3.
Monday, September 19
No classes due to Queen's FuneralWednesday
- Proof of Correctness of the Maximum Branching Algorithm. (and of Key Structural Lemma).
Week 4.
Monday Sep 26
- Edmonds Arborescence Packing Theorem.
- Uncrossing Lemma.
- Thomassen's Conjecture.
Wednesday, September 28
- Intro to Convexity. Elementary proof of Separating Hyperplane Theorem.
- Multi-coloured simplices.
- Quiz.
Week 5.
Monday Oct 3
- Polyhedral basics. Characteristic (recession) cones, affine hull, dimension
- Polyhedral Decomposition Theorem.
- Swift intro to LP Duals and Complementary Slackness
Wednesday Oct 5
- Characterizations of polyhedral faces (and vertices).
- Intro to Polyhedral Combinatorics. Valid inequalities for stable set polytope.
Week 6.
Monday Oct 10. Thanksgiving
Wednesday Oct 12
- The Edge Constraint Relaxation for stable set polytope.
- Stable set polytopes for bipartite graphs
- Separation and Optimization.
- Separation for network st-flows (and multi-flows) in the path variable formulation.
Week 7.
Monday Oct 17
- Polytime algorithms, and encoding complexity of optimal solutions for LP. Cramer's Rule.
- Totally Unimodular Matrices.
- Total Dual Integrality (TDI).
- Edge-node incidence matrices of bipartite graphs.
Wednesday Oct 19
- TUM formulation for bipartite matchings
- Edge-Node Incidence Matrices (ENIM) of Digraphs are TUM.
- Formulating Flows using ENIM of Digraphs.
- More TUM Matrices: The Network Matrices.
Week 8.
Monday Oct 24
- Intro to Matroids. The Greedy Algorithm.
- Examples of Matroids (Graphic, Partition, Laminar, Linear).
Wednesday Oct 26
- Matching Matroids and Gammoids
- Matroid Structure. Submodularity, circuits, unique circuit property.
- Quiz.
Week 9.
Monday Oct 31
- Rank Constraints for Combinatorial Optimization (and integer programming)
- Matroid Polytope
Wednesday Nov 2
- Facets and Defining Systems.
- The Matroid Polytope Theorem.
- Introduction to Matroid Intersection Theorem. Examples.
- Bipartite Exchange Graph
Week 10.
Monday Nov 7
- Frank's Exchange Lemma
- (Algorithmic) Proof of Matroid Intersection.
- Polyhedral description for common indpendent sets.
Wednesday Nov 9
- STUDY BREAK.
Week 11.
Monday Nov 14
- Matroid Partitioning Theorem
- Matroid Projection Theorem
- Applications, including Matroid Colouring.
Wednesday Nov 16
- Di-cuts and Dijoins.
- Statement of Lucchessi-Younger Theorem.
- Clutters and Blockers.
- Introduction to Crossing Families and Submodular Flows
- Modelling Lucchessi-Younger and Flow Problems.
Week 12.
Monday Nov 21
- Proof of Edmonds-Giles Theorem.
Wednesday Nov 23
- Dual of Lucchessi-Younger. Integral and fractional Packings of Dijoins.
- Lehman's Theorem of Ideal Matrices and Blockers.
- Maximum Cadinality Matchings in General Graphs (intro and Tutte-Berge Formula).
- Brief discussion of local search.
Week 13.
Monday Nov 28
- M-Augmenting Paths
- Algorithm for Maximum Cadinality Matchings in General Graphs (and proof of Tutte-Berge formula).
Wednesday Nov 30
- Minimum Cost (Weighted) Matchings in General Graphs (Intro).
- Quiz
Week 14.
Monday Dec 5
- Minimum Cost (Weighted) Matchings in General Graphs The Algorithm.
- Runing the Minimum Cost Perfect Matching Algorithm
- The Postman Problem and Eulerian Circuits
- Quiz
Wednesday Dec 7
- T-joins.
- Negative Cost Cycles in Undirected Graphs