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