CS 586/IE 519: Combinatorial Optimization, Spring 2022


Course Summary

The course will cover a selection of topics in combinatorial optimization. The emphasis will be on polyhedral theory, structural results and their applications to designing algorithms. Specific topics to be covered include: matchings and their applications, connectivity properties of graphs, matroids and optimization including matroid intersection and union, submodular set functions and applications, arborescences and branchings, and basics of multi-flows.


Administrative Information

Lectures: Tue, Thu 11-12.20pm in Siebel Center 0216. Zoom link for online lectures during first week. Requires you to log in via Illinois credentials for security purposes

Recordings:  Mediaspace channel

Instructor:  Chandra Chekuri, 3228 Siebel Center, (chekuri at)

Teaching Assistant:  Calvin Beideman, (calvinb2 at)

Office Hours (Chandra): TBA

Office Hours (Calvin): Wednesday 4:00-5:00 PM link

Grading Policy: 50% homework, 30% exams (2 x 15%), 20% project.

Attendance policy: at least 60% of lectures for a grade.

Prerequisites: This is a graduate level class. Official prerequisites: familiarity with linear programs (IE 411 or equivalent), algorithms (CS 374 or equivalent), and graph theory (MATH 412 or equivalent). Most important is mathematical maturity and comfort with formal proofs and arguments and interest in the topic. Consult the instructor if you have questions.

Covid-19 and mental health support at UofI: Diminished mental health, including significant stress, mood changes, excessive worry, substance/alcohol abuse, or problems with eating and/or sleeping can interfere with optimal academic performance, social development, and emotional wellbeing. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings at no additional cost. If you or someone you know experiences any of the above mental health concerns, it is strongly encouraged to contact or visit any of the University's resources provided below. Getting help is a smart and courageous thing to do -- for yourself and for those who care about you.
Counseling Center: 217-333-3704, 610 East John Street, Champaign, IL 61820
McKinley Health Center: 217-333-2700, 1109 South Lincoln Avenue, Urbana, Illinois 61801
University wellness center
Please do not hesitate to contact the instructor if you need help or assistance.

College of Engineering Syllabus Statements: See here for important information and regulations regarding academic integrity, disability accommodations, FERPA rights, religious observances, and sexual misconduct reporting.

Anti-racism and inclusivity: Official statement. Be kind, respectful, and professional to everyone and expect the same from others.

Department of Computer Science values and code of conduct and CS Cares Committee

References

Electronic versions of several books from Cambridge University, Springer, Wiley and other publishers are available free to Univ of Illinois students via the library.

 


 

Piazza, Gradescope (YV6ZPR)  


Homework

Lectures

Scribbles on iPad for each lecture can found at link. Change lecture number to obtain the relevant one.
  • Lecture 1: 1/18/2022, Introduction
    • Chapter 1 of class notes
    • Preface of Schrijver's book
  • Lecture 2: 1/20/2022, Non-bipartite matching, Tutte-Berge formula and Edmonds algorithm for max cardinality matching
    • Chapter 2 of class notes and references
  • Lecture 3: 1/25/2022, Basics of Polyhedra and LP
    • Chapter 3 of class notes
    • Schrijver's book on linear and integer programming (Chapters 7, 8)
    • Schrijver's book on combinatorial optimization (Chapters 4, 5)
  • Lecture 4: 1/27/2022, Continue previous topic
  • Lecture 5: 2/1/2022, Integer polyhedra, Totally Unimodular Matrices
    • Chapter 4 of class notes
    • Schrijver's book on linear and integer programming (Chapters 16, 19)
    • Schrijver's book on combinatorial optimization (Chapter 5)
  • Lecture 6: 2/3/2022, Applications of TUM matrices (bipartite matching, s-t flows/cuts, interval graphs)
  • Lecture 7: 2/8/2022, Network flow algorithms: a quick overview
    • Chapter 6 of class notes
    • Chapter 4 in Schrijver's notes
    • Chapter 2 in Kent Quanrud's notes
    • Network Flow Algorithms by David Williamson
    • Schrijver's book (Chapters 9 to 13)
    • Network flows book by Ahuja, Magnanti, Orlin
  • Lecture 8: 2/10/2022, Connectivity in Graphs and Gomory-Hu Trees
    • Chapter 7 in notes
    • Chapter 15 in Schrijver's book
    • Chapter 3 in Williamson's network flow algorithms book
  • Lecture 9: 2/15/2022, Matching Polytopes
    • Chapter 8 in notes
    • Chapter 25 in Schrijver's book
  • Lecture 10: 2/17/2022, Primal-Dual for Min-Cost Bipartite Matching
    • Chapter 9 in notes
  • Lecture 11: 2/22/2022, Edmonds-Gallai Decomposition
    • Chapter 8 in notes
  • Lecture 12: 2/24/2022, Primal-dual for Min-cost Perfect Matching in Non-bipartite graphs
    • Chapter 9 in notes
    • Chapter 11 in Korte-Vygen book has an elaborate description and discussion of implementation issues
    • Jan Vondrak's lecture notes based on alternating forest description. Also Chapter 5 of book by Cook etal.
  • Lecture 13: 3/01/2022, T-joins and applications
    • Chapter 12 in notes
  • Lecture 14: 3/03/2022, Total Dual Integrality and Cunningham-Marsh Theorem
    • Chapter 11 in notes
  • Lecture 15: 3/08/2022, Introduction to Matroids
    • Chapter 13 in notes
    • What is a matroid? A survey by James Oxeley on the structural aspects of matroids.
  • Lecture 16: 3/10/2022, Matroid Polytope
    • Chapter 13 in notes
  • Midterm 1: 3/22/2022
  • Lecture 16: 3/24/2022, Further aspects of matroids, intro to matroid intersection
    • Chapters 13, 14 in notes
  • Lecture 17: 3/24/2022, Further aspects of matroids, intro to matroid intersection
    • Chapters 13, 14 in notes
  • Lecture 18: 3/29/2022, Matroid intersection: min-max result for max cardinality indep set via algorithm
    • Chapter 14 in notes
  • Lecture 19: 3/31/2022, Matroid intersection polytope
    • Chapter 14 in notes
  • Lecture 20: 4/05/2022, Matroid Union and Applications
    • Chapter 15 in notes
  • Lecture 21: 4/07/2022, Arborescences: min-cost, polytope, arc disjoint packing
    • Chapters 16 in notes
  • Lecture 22: 4/14/2022, Submodular functions and Polymatroids
    • Chapter 17 in notes
  • Lecture 23: 4/19/2022, Greedy algorithm for polymatroids and submodular function minimization
    • Chapter 17 in notes
  • Lecture 24: 4/21/2022, Continuous extensions of submodular functions
    • Chapter 18 in notes
    • Shaddin Dughmi's survey
  • Lecture 25: 4/26/2022, Two theorems on graphs: orientation and dijoins
  • Lecture 26: 4/28/2022, Submodular Flow and Applications
    • Chapter 21 notes
  • Midterm 2: 5/02/2022