CSL856: Mathematical Programming

This course
will be in
three parts:
 Linear Optimization:
Geometry of Linear Programming, Simplex method. Duality, complemetary
slackness, Ellipsoid method, Interior point algorithms.
 Linear Programming by Vasek Chvatal
 Introduction to Linear Optimization by Bertsimas and
Tsikilis.
 Convex Optimization:
All students will register for the mooc CVX101
by Stephen Boyd. This course is to run from 21 Jan to March 14.
 Integer Programming:
Valid inequlities and facets, Cutting plane algorithms, branch and
bound using LP relaxations, integer polyhedra.
 Integer and Combinatorial Optimization by Nemhauser and
Wolsey
 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/sloanschoolofmanagement/15083jintegerprogrammingandcombinatorialoptimizationfall2009
 Integer Programming: Polyhedra and Algorithms by S.O. Krumke

Class
Schedule




Date

Topics

Slides

Addl
material

Jan 2

Introduction to
Linear Programming

pdf


Jan 6

Overview of the simplex method, basic variables

pdf 

Jan 16

Initialization, degeneracy, rules to avoid cycling.

pdf, pdf


Jan 23, 27

Duality and Complementary Slackness

pdf 

Jan 29, 30

Geometric Interpretation, Farkas lemma

ppt1, ppt2 

Feb 3, 5

Teh cutting stock problem



Feb 10, 12

The Ellipsoid method


pdf


Convergence analysis of newton's method


pdf

Course Evaluation

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



