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 multiflows.
Administrative Information
Lectures: Tue, Thu 1112.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:005: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.
Covid19 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: 2173333704, 610 East John Street, Champaign, IL 61820
McKinley Health Center: 2173332700, 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.
Antiracism 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.
 (Highly) Recommended book: Lex Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, 3Volume book, SpringerVerlag 2003;
also available as a CD.
 Lex Schrijver, Theory of Linear and Integer Programming (Paperback), Wiley, 1998
 B. Korte and J. Vygen,
Combinatorial Optimization: Theory and Algorithms,Algorithms and Combinatorics 21
Springer, Berlin Heidelberg New York, 2006.
 L. Lau, R. Ravi and M. Singh, Iterative Methods in Combinatorial Optimization, Cambridge University Press, 2011.
 Andras Frank, Connections in Combinatorial Optimization, Oxford University Press, 2011.
 J. Lee, A
First Course in Combinatorial Optimization, Cambridge University
Press, 2004.
 W.
Cook, W. Cunningham, W. Pulleyblank and A. Schrijver, Combinatorial Optimization, Wiley, 1997.

C. Papadimitriou and K. Steiglitz, Combinatorial Optimization:
Algorithms and Complexity, PrenticeHall, 1982.

E.L. Lawler, Combinatorial Optimization: Networks and Matroids,
Holt, Rinehart and Winston, 1976.

G. Nemhauser and L. Wolsey, Integer and Combinatorial
Optimization, John Wiley & Sons, 1988.
 Book in progress by Gallier and Quaintance on geometry, LP etc.
 Notes. Compiled, edited, and updated version of lecture notes from Chandra's course, Spring 2010.
 Lecture notes from Michel Goemans:
Advanced topics (2020)
and first course (2017)
 Lecture notes from Jan Vondrak's course.
 Lex Schrijver's notes from 2017.
 Constantine Caramanis's video lectures .
 Wiki on open problems in combinatorial optimization from the Egervary Research Group.
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, Nonbipartite matching, TutteBerge 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, st 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 GomoryHu 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, PrimalDual for MinCost Bipartite Matching
 Lecture 11: 2/22/2022, EdmondsGallai Decomposition
 Lecture 12: 2/24/2022, Primaldual for Mincost Perfect Matching in Nonbipartite graphs
 Chapter 9 in notes
 Chapter 11 in KorteVygen 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, Tjoins and applications
 Lecture 14: 3/03/2022, Total Dual Integrality and CunninghamMarsh Theorem
 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
 Midterm 1: 3/22/2022
 Lecture 16: 3/24/2022, Further aspects of matroids, intro to matroid intersection
 Lecture 17: 3/24/2022, Further aspects of matroids, intro to matroid intersection
 Lecture 18: 3/29/2022, Matroid intersection: minmax result for max cardinality indep set via algorithm
 Lecture 19: 3/31/2022, Matroid intersection polytope
 Lecture 20: 4/05/2022, Matroid Union and Applications
 Lecture 21: 4/07/2022, Arborescences: mincost, polytope, arc disjoint packing
 Lecture 22: 4/14/2022, Submodular functions and Polymatroids
 Lecture 23: 4/19/2022, Greedy algorithm for polymatroids and submodular function minimization
 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
 Midterm 2: 5/02/2022
