Fundamentals of Linear Programming
Back
I regularly teach an introductory linear programming course to Master of Engineering students at Cornell. This webpage is a reproduction of the lectures I teach for that course. The course closely follows a course packet available here as a pdf file. The recorded video lectures are available here as a YouTube playlist. I firmly believe in teaching and learning with a pencil in hand, so I write as I go along in the lecture videos. Scans of all of the material that I hand-write are also available on this webpage.
The outline for the course is fairly standard. We cover the simplex method, duality theory, network flows, and integer programming. That said, I believe the course does a good job of conveying that the simplex method is nothing more than row operations, establishing strong duality through a comparison of the first and final systems of equations in the simplex method, and demonstrating the economic interpretation of duality by tracking the row operations in the simplex method.
Course Packet
The course packet is available here as a pdf file. The course packet has gaps that we fill as we go along in the lecture videos. Some day, I may post a filled-in version of the course packet, but the version with the gaps available here and the scanned hand-written material collectively give the full picture.
Lecture Videos
The lecture videos are available here as a YouTube playlist.
Handwritten Notes
Below are the scans of the material that I hand-write during the lecture videos.
Lecture 1 - Formulating a Linear Program and Excel's Solver
Lecture 2 - Geometry of Linear Programming
Lecture 3 - Useful Linear Algebra Concepts
Lecture 4 - Introduction to the Simplex Method
Lecture 5 - A Second Example on the Simplex Method
Lecture 6 - Phase-1 Linear Program to Construct a Feasible Solution to a Linear Program
Lecture 7 - Solving a Linear Program Starting with the Feasible Solution from the Phase-1 Linear Program
Lecture 8 - Linear Programs in General Form
Lecture 9 - Unbounded Linear Programs, Multiple Optima and Degeneracy
Lecture 10 - Min-Cost Network Flow Problem
Lecture 11 - Assignment, Shortest Path and Max-Flow Problems
Lecture 12 - Gurobi as a Standalone Solver and Small Example for Calling Gurobi from Python
Lecture 13 - Calling Gurobi from Python While Creating Decision Varibles and Constraints via Loops
Lecture 14 - Introduction to Duality
Lecture 15 - Weak Duality
Lecture 16 - Strong Duality
Lecture 17 - Complementary Slackness
Lecture 18 - Economic Interpretation of the Dual Problem
Lecture 19 - Covering, Fixed Charge and Either-Or Constraints via Integer Programming
Lecture 20 - Piecewise-Linear Objective Functions via Integer Programming
Lecture 21 - Branch-and-Bound Method for Solving Integer Programs
Lecture 22 - Facility Location and Dynamic Driver Assignment Problems
Lecture 23 - Traveling Salesman Problem
Lecture 24 - Optimization under Uncertainty