Linear and Integer Programming

Introductory Material 

• Introduction to Linear Programming.

• The Diet Problem.
• Linear Programming Formulations.
  
• Tutorials on using GLPK (AMPL), Matlab, CVX and Microsft Excel.
• The Simplex Algorithm (basics).

• Handling unbounded problems
• Degeneracy
• Geometry of Simplex
• Initializing Simplex.
• Cycling and the Use of Bland's rule.

• Duality: dual variables and dual linear program.
• Strong duality theorem.
• Complementary Slackness. 
• KKT conditions for Linear Programs.
• Understanding the dual problem: shadow costs.
• Extra: The revised simplex method.

• Advanced LP formulations: norm optimization.
• Least squares, and quadratic programming.
• Applications #1: Signal reconstruction and De-noising.
• Applications #2: Regression.

• Integer Linear Programming.
• Integer vs. Real-valued variables.
• NP-completeness: basic introduction.
• Reductions from Combinatorial Problems (SAT, TSP and Vertex Cover).
• Approximation Algorithms: Introduction.

• Branch and Bound Method
• Cutting Plane Method

• Applications: solving puzzles (Sudoku), reasoning about systems and other applications.
• Classification and Machine Learning

• Shalom Ruben - Mechanical Engineering
• Sriram Sankaranarayanan - Department of Computer Science