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/sloan-school-of-management/15-083j-integer-programming-and-combinatorial-optimization-fall-2009
- 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.
|
|
|
|