CS5210-2024
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; 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