CS5210-2022
Linear Programming & Combinatorial Optimization
Syllabus (topics covered in lectures + assignments):
Module-1: Introduction & Overview (2 weeks)
Linear Programs (LPs) and Integer Linear Programs (ILPs); Formulating Combinatorial Optimization Problems as ILPs: Shortest Paths, Matchings, Set Cover & Vertex Cover; RelaxationsModule-2: Geometry & Convexity (1.5 weeks)
Feasible Region of LPs & Polyhedra; Outcomes & Fundamental Theorem of LP; Convexity & Convex Combinations; Extreme Points; Convex Hulls & PolytopesModule-3: Simplex & Certificates (2 weeks)
Equivalence of LPs and Standard Equality Form; Dictionaries, Feasible Bases & Basic Feasible Solutions; Simplex Method via Dictionaries; Two Phase Simplex; Bland's Pivoting Rule; Certificates of Unboundedness & InfeasibilityModule-4: Duality (1.5 weeks)
Certificate of Optimality; Weak Duality (WD), Strong Duality (SD) and their consequences; Writing the Dual; Complementary Slackness (CS) conditions and their geometric interpretation; Applications of CS; Farkas’ LemmaModule-5: Primal-Dual Algorithms (4 weeks)
Shortest Path: WD & CS; Primal-Dual algorithm
Matchings: Finding Perfect Matchings: Egervary's Algorithm & Edmonds' Blossom Algorithm; Characterizations of the Perfect Matching Polytope; WD & CS; Primal-Dual algorithms for Minimum Cost Perfect Matching Problem: Hungarian Algorithm & Edmonds' Blossom Algorithm (Cost Version)
Vertex Cover & Set Cover: LP relaxation and its dual; CS conditions; Primal-Dual Approximation algorithmModule-6: Applications of Duality & Min-Max Theorems (2 weeks)
Integrality of Polyhedra; Totally Unimodular Matrices; Max Flow Problem & its Integrality; Flows versus Cuts; Max-Flow Min-Cut (MFMC) Theorem; Incrementing Paths and the Ford-Fulkerson Algorithm; Edmonds-Karp Algorithm (without time complexity analysis); MFMC Theorem proof via LP Duality; Konig-Egervary Theorem; Tutte-Berge Min-Max Formula/Theorem
Lecture Recordings:
Module-1: Introduction & Overview
Lecture-1 (Admin & Logistical Matters; Basic Graph Theory Terminology; Matchings & Perfect Matchings)
Lecture-2 (Matchings & Perfect Matchings; Min Cost Perfect Matching Problem; LPs & ILPs)
Lecture-3 (Min Cost Perfect Matching Problem; thru the lens of Complexity Theory: NP & co-NP Certificates)
Lecture-4 (Min Cost Perfect Matching; Bipartite Graphs; Hall's Theorem statement)
Lecture-5 (P subset of NP intersection co-NP; Matchings & Augmenting Paths)
Lecture-6 (Berge's Lemma and Maximum/Perfect Matching Algorithms; Paths versus Cuts)
Lecture-7 (The Shortest Path Problem and its ILP Formulation)
Lecture-8 (Shortest Path ILP versus Min Cost Perfect Matching ILP; st-Paths versus st-Cuts)Module-2: Geometry & Convexity
Lecture-9 (Feasible Region of LPs & Polyhedra; Feasible versus Infeasible LPs)
Lecture-10 (Feasible LPs: "Optimal" versus Unbounded; Fundamental Theorem of LP)
Lecture-11 (Line Segments, Convex Combinations & Convex Sets; Polyhedra are Convex)
Lecture-12 (Extreme Points: Geometric & Algebraic Viewpoints)
Lecture-13 (Convex Hulls & Polytopes; The Perfect Matching Polytope)Module-3: Simplex & Certificates
Lecture-14 (Equivalence of LPs; Standard Equality Form (SEF); Converting any LP into SEF LP)
Lecture-15 (The Simplex Method via Dictionaries: an "Optimal" Example)
Lecture-16 (Dictionaries; Feasible Bases & Basic Feasible Solutions)
Lecture-17 (Canonical Forms versus Dictionaries; Transforming an LP into Canonical Form)
Lecture-18 (Two Phase Simplex; Bland's Pivoting Rule; An Unbounded Example)
Lecture-19 (Certificates of Unboundedness and Infeasibility; An Infeasible Example)
Lecture-20 (A brief history of Linear Programming & the Simplex Method)Module-4: Duality
Lecture-21 (Establishing Bounds on the Optimal Value; Weak Duality (WD) and its proof for SEF LPs)
Lecture-22 (Certificate of Optimality; Writing the Dual; WD & its consequences)
Lecture-23 (Strong Duality (SD) & its consequences; SD --- proof & an example for SEF LPs)
Lecture-24 (Complementary Slackness (CS) Conditions; CS Theorem --- proof & an example)
Lecture-25 (CS example; Geometric Characterization of Optimality --- Cone of Tight Constraints)
Lecture-26 (Proof of Geometric Characterization of Optimality; A computational application of CS)Module-5: Primal-Dual Algorithms
Lecture-27 (The Shortest Path Problem: ILP, LP relaxation and Dual; Combinatorial Interpretations of WD & CS)
Lecture-28 (Designing a Primal-Dual Algorithm for the Shortest Path Problem --- Example & Intuition)
Lecture-29 (Basic Digraph terminology; Formalizing the Primal-Dual Algorithm for the Shortest Path Problem)
Lecture-30 (Recap: Berge's & Hall's results; Egervary's Algorithm for Bipartite Perfect Matching (PM) --- Intuition)
Lecture-31 (Formalizing Egervary's Algorithm; Min Cost PM Problem: ILP, LP relaxation & Dual, WD & CS)
Lecture-32 (Designing a Primal-Dual Algorithm for Min Cost Bipartite PM Problem --- Example & Intuition)
Lecture-33 (Primal-Dual Algorithm for Min Cost Bipartite PM Problem --- Formalization & Time Complexity)
Lecture-34 (Hungarian Algorithm for Min Cost Bipartite PM Problem --- Example, Formalization & Time Complexity)
Lecture-35 (A brief history of Perfect Matching Characterization Theorems & Algorithms; Tutte's Theorem)
Lecture-36 (Edmonds' Blossom Algorithm for Nonbipartite Perfect Matching --- Intuition & Examples)
Lecture-37 (Edmonds' Blossom Algorithm --- A "Big" Example --- with multiple as well as nested blossoms)
Lecture-38 (Formalizing Edmonds' Blossom Algorithm for Nonbipartite Perfect Matching)
Lecture-39 (Edmonds' Blossom Algorithm: Time Complexity; Edmonds' Perfect Matching Polytope (PMP) Theorem)
Lecture-40 (Edmonds' LP Formulation for PMP: WD & CS; Towards a Primal-Dual Algorithm for Min Cost PM)
Lecture-41 (Edmonds' Blossom Algorithm for Nonbipartite Min Cost Perfect Matching: Intuition & Example)
Lecture-42 (Edmonds' Blossom Algorithm Cost Version: Example continued, Issues & their Fixes)
Lecture-43 (Edmonds' Blossom Algorithm Cost Version: Example continued, Formalization & Time Complexity)Module-6: Applications of Duality & Min-Max Theorems
Lecture-44 (Integrality of Polyhedra; Totally Unimodular (TU) Matrices)
Lecture-45 (The Max Flow Problem and its Integrality)
Lecture-46 (st-flows versus st-dicuts; Max-Flow Min-Cut (MFMC) Theorem statement)
Lecture-47 (Incrementing Paths & the Ford-Fulkerson Algorithm)
Lecture-48 (Auxiliary Digraphs; MFMC Theorem proof; Edmonds-Karp Algorithm; MFMC LP & its Dual)
Lecture-49 (MFMC Theorem proof via LP Duality & Integrality; Konig-Egervary Theorem & Tutte-Berge Formula)
Lecture-50 (Barriers; Essential versus Inessential vertices; Proof of the Tutte-Berge Formula/Theorem)