Instructor: Robert J. Vanderbei, ACE-42, 8-0876 rvdb@princeton.edu

Office Hours: TTh 10:30-12:00, ACE-42

TA: John Yuan, E-420, 8-5339, jhyuan@phoenix

Office Hours: W 1:00-4:00, E-420

TA: Damiano Foschi, 507 Fine Hall, 8-5795, dfoschi@math

Office Hours: M 5:00-6:00, 507 Fine Hall

Lectures: TTh 9:00-10:20, C-305

Linear programming (LP) is a branch of Optimization in which one studies the maximizimization (or minimization) of a linear function subject to linear equality and inequality constraints. The linear programming problem has wide ranging applications from diverse areas such as Economics, Computer Science, Operations Research, Medicine, Finance, Mathematics, as well as every branch of Engineering. It is also the starting point from which one studies more general constrained optimization problems.

There will be a midterm (30%), a final (30%), weekly homeworks (30%), and a project (10%). Homework will be collected each week in the Thursday lecture.

There are two texts for the course. One called AMPL: A Mathematical Programming Language can be purchase at the U-Store. The other is a set of lecture notes that can be purchased from Ruthanne Lavis in E-410.

Outline

• Examples and Definition of the Linear Programming Problem
  • Input Models
    • The Diet Problem
    • Blending Problems
    • A Scheduling Problem
  • Output Models
    • A Production Problem
  • Network Models
    • A Transportation Problem
    • An Assignment Problem
    • A Transshipment Problem
• Introduction to AMPL -- A Math Programming Language
• The Simplex Method
  • Degeneracy
  • Efficiency
• Duality
  • The Dual Problem
  • Weak Duality
  • Strong Duality
  • Complementary Slackness
  • Economic Interpretation
• The Dual Simplex Method
  • A Dual Based Phase I Algorithm
• The Simplex Method in Matrix Notation
• Sensitivity Analysis, Parametric Analysis, and the Primal-Dual Simplex Method
• Game Theory
• Regression
• The Path-Following Method
• Network Flow Problems
• Network Flow Applications
  • The Transportation Problem
  • The Assignment Problem
  • The Shortest Path Problem
• Optimal Structural Design
• Integer Programming
  • The Travelling Salesman Problem
• Quadratic Programming
  • The Markowitz Model for Portfolio Optimization
• Convex Optimization
  • The Utility Optimization Problem
  • The Facility Location Problem