|
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.
- (Highly) Recommended book: Lex Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, 3-Volume book, Springer-Verlag 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, Prentice-Hall, 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, 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
- Lecture 11: 2/22/2022, Edmonds-Gallai Decomposition
- 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
- Lecture 14: 3/03/2022, Total Dual Integrality and Cunningham-Marsh 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: min-max 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: min-cost, 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
|
