MTH 305/505 Monsoon 2014

Announcements

  • Assignment 2 has been posted here. The due date is Monday, Sep. 15, by 3:00PM. Please submit to Sneha Bhatia (TA). 
  • Assignment 1 has been posted here. The due date is Friday, Aug. 22, before class time. Please submit by email to Dr. Saket Anand. 

Classroom and Time

C-22, Tue, Fri: 9:30-11:00 

Textbooks: 

  1. Jiri Matousek, Bernd Gartner,"Understanding and Using Linear Programming", Springer, 2007 - (MG)
  2. Dimitris Bertsimas, John Tsitsiklis, "Introduction to Linear Optimization", Athena Scientific, 1997 - (BT)

 

Instructors

  Office Hours
 Saket Anand
Wed 1600-1700 or by appointment
 Rajiv Raman
Wed 1600-1700

TA

  Office Hours
 Sneha Bhatia
Mon 1400-1500

Lectures

 Date What we covered  
 Material
 Aug 5  
 Introduction to the course. History and applications of linear programming. Basic definitions. Two exercises in modelling problems as linear programs.
 Slides.
BT-Ch-1.1 - 1.3
MG-Ch-1, MG-Ch-2
 Aug 8
Word Problem to LP formulationBT-Ch-1.2, MG-Ch-2
 Aug 12 Linear Equations, Gaussian elimination, Solution space. Slides 
BT-Ch-1.5, MG-Ch-1.3, MG-Ch-4.1
Related Gilbert Strang's video lectures 
Geometry of linear equations
Elimination with Matrices
Solving Ax=b
Independence, Basis and dimension
The four fundamental subspaces
 Aug 19Continued from last class
Geometry of linear equations and linear inequalities    
 
 Aug 26Geometry of Linear Programs 
Solving LPs graphically 
Fourier-Motzkin Elimination

 BT-Ch-2, MG-Ch-4
 Aug 29
 Simplex Algorithm: Definition of the tableau and examples.
 
 Sep 2
 Simplex algorithm - dealing with unboundedness, infeasibility
 
 Sep 5
 Simplex algorithm: Cycling
 
 Sep 9
 Two-phase Simplex: examples.
 
 Sep 12
 Linear Programming Duality
 
 Sep 16
 LP Duality cond... Weak duality, strong duality, complementary slackness.
 
 Sep 19
 Application of LP Duality: Equilibrium in Zero-sum games.
 
 Sep 30
 Polyhedra, Polytopes,  Extreme points, basic solutions, basic feasible solutions. Proof of equivalence of definitions of extreme point, vertex and basic feasible solution.
 
 Oct 7
Continued proof of equivalence of extreme points, vertex and basic feasible solution. Dependence of basic solutions on the form of the LP.
 
Oct 8
 Proof that an LP has an extreme point if and only if it does not contain a line,  Optimality of extreme points.   
 
 Oct 10
 Development of simplex algorithm: Feasible directions,reduced cost.
 
 Oct 14
Problems with degeneracy, simplex algorithm.
 
 Oct 17
 Revised simplex algorithm and simplex tableau implementation.
 
 Oct 28
 Simplex Tableau implementation.
 
 Oct 31
 Proof of convergence of simplex with lexicographic pivoting rule.
 
 Nov 4
 Proof of convergence of Simplex. Example where simplex takes exponential time: Klee-Minty cubes.
 
 Nov 7    
 Proof of strong duality via Simplex. Proof of Farkas Lemma via Simplex. Application of Farkas Lemma: Markov Chains
 
 Nov 11
 Separating hyperplanes and proof of strong duality via separating hyperplane.
 
 Nov 14
 The Khachiyan-Grigoriadis algorithm for solving zero-sum games.
 
 Nov 18
 Network flows and matchings
 
 Nov 21
 Applications