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; Relaxations
Module-2: Geometry & Convexity (1.5 weeks)
Feasible Region of LPs & Polyhedra; Outcomes & Fundamental Theorem of LP; Convexity & Convex Combinations; Extreme Points; Convex Hulls & Polytopes
Module-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 & Infeasibility
Module-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’ Lemma
Module-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 algorithm
Module-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 Boring Administrative Matters; Basic Graph Theoretical Terminology
Lecture-2 Basic Graph Theoretical Terminology; Matchings & Perfect Matchings
Lecture-3 Formulating our first Integer Linear Program (ILP) --- for the Minimum Cost Perfect Matching Problem
Lecture-4 Linear Programs (LPs); Integer Linear Programs (ILPs) & their (LP) relaxations; Complexity Classes NP, co-NP and P
Lecture-5 Decision Problems vs Optimization Problems; NP & co-NP certificates; Bipartite graphs (and their significance in the context of matchings)
Lecture-6 The Maximum Matching Problem; Alternating Paths/Cycles & Augmenting Paths; Berge's Lemma
Lecture-7 The Shortest Path Problem; the prominent role of Cuts; st-paths vs st-cuts
Lecture-8 Formulating an ILP for the Shortest Path Problem by leveraging st-cuts; Maximum Matching Problem vs the Maximum Stable Set Problem