CSL856: Mathematical Programming

This course will be in three parts:
  1. Linear Optimization: Geometry of Linear Programming, Simplex method. Duality, complemetary slackness, Ellipsoid method, Interior point algorithms.
    1. Linear Programming by Vasek Chvatal
    2. Introduction to Linear Optimization by Bertsimas and Tsikilis.
  2. Convex Optimization: All students will register for the mooc CVX101 by Stephen Boyd. This course is to run from 21 Jan to March 14.
  3. Integer Programming: Valid inequlities and facets, Cutting plane algorithms, branch and bound using LP relaxations, integer polyhedra.
    1. Integer and Combinatorial Optimization by Nemhauser and Wolsey
    2. Bertsimas, Dimitris, and Andreas Schulz. 15.083J Integer Programming and Combinatorial Optimization, Fall 2009. (MIT OpenCourseWare: Massachusetts Institute of Technology), http://ocw.mit.edu/courses/sloan-school-of-management/15-083j-integer-programming-and-combinatorial-optimization-fall-2009
    3. Integer Programming: Polyhedra and Algorithms by S.O. Krumke
Class Schedule

Addl material
Jan 2
Introduction to Linear Programming

Jan 6
Overview of the simplex method, basic variables
Jan 16
Initialization, degeneracy, rules to avoid cycling.
pdf, pdf

Jan 23, 27
Duality and Complementary Slackness
Jan 29, 30
Geometric Interpretation, Farkas lemma
ppt1, ppt2
Feb 3, 5
Teh cutting stock problem

Feb 10, 12
The Ellipsoid method


Convergence analysis of newton's method

Course Evaluation
20% minor 1, minor 2, CVX101, 10% Assignments, 30% final.