Department of Computer Science & Engineering

Description: Optimization problems appear in abundance in different branches of engineering as well as in business and economics; the simplest of these are linear optimization (aka linear programming) problems. There is a rich theory underlying linear optimization that provides invaluable insight for optimization problems in general. Furthermore, this theory ties neatly with optimization problems arising from combinatorial structures (such as shortest paths, network flows, min cost matchings) and is thus useful in developing algorithms for such problems.The goal of this course is to provide a rigorous treatment of linear optimization, and of its application in developing efficient algorithms for a few important combinatorial optimization problems. An additional learning outcome is for the students to practice and improve their proof writing skills.

CourseContent: I. Linear and Integer Programs (2 weeks)Formulating real world problems as linear and integer linear programs, formulating combinatorial optimization problems as integer linear programs, recap of important concepts in linear algebraII. Geometry of Polyhedra (2 weeks)Feasible region of LPs and polyhedra, Convexity, Extreme points, Faces and facetsIII. Solving linear programs (3 weeks)Possible outcomes (infeasibility, unboundedness, and optimality) and their certificates, bases and canonical forms, the Simplex method and its geometric interpretation, the ellipsoid method and separation oracles.IV. Duality (2 weeks)Weak duality, strong duality, complementary slackness, Farkas’ LemmaV. Combinatorial Optimization (4-5 weeks)Primal-dual method for exact and approximation algorithms, Shortest paths, Minimum cost perfect matchings, Max-Flow Min-Cut Theorem, Totally Unimodular MatricesVI. Additional topics (if time permits)Interior-point methods, Randomized/Online algorithms for LPs, Integer Programs, Convex Optimization, Matroids, T-joins, Applications to Game Theory.

TextBooks:Guenin, Konemann & Tuncel. A gentle introduction to optimization. Cambridge University Press, 2014.

ReferenceBooks:1) Cook, Cunningham, Pulleyblank and Schrijver. Combinatorial Optimization. Wiley-Interscience, 1998.2) Schrijver. Combinatorial Optimization. Springer, 2003.3) Grotschel, Lovasz and Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1993.4) Luenberger and Ye. Linear and Nonlinear Programming. Springer, 2008.5) Nocedal and Wright. Numerical Optimization. Springer, 2006.6) Research articles as chosen by the instructor.

Prerequisite:CS1200 / MA2130