Math 510: Linear Programming and Network Flows
.png)
Colorado State University, Fall 2020
Instructor: Henry Adams
Email: henry dot adams at colostate dot edu
Office: Weber 120 (but not coming to campus Fall 2020)
Office Hours: At the end of class, or by appointment
Lectures: TR 9:30-10:45am online.
Textbook:
Understanding and Using Linear Programming by Jiří Matoušek and Bernd Gärtner.
This book is freely available as a PDF to CSU students if you login on the CSU library webpage.
Overview: Optimization methods, linear programming, simplex algorithm, duality, sensitivity analysis, minimal cost network flows, transportation problem.
Mode of instruction: This class will be 100% online.
Syllabus: Here is the course syllabus.
Course notes: Here are Henry's course notes as a PDF (or as a Notability source code file).
Homework
Homework 1 (LaTeX Source) is due Tuesday, September 22.Homework 2 (LaTeX source) is due Tuesday, October 27.
Homework 3 (LaTeX source) is due Tuesday, December 8.
Exams
The optional midterm (LaTeX Source) is due Friday, October 16.Here are the midterm solutions.
The optional final is on Monday, December 14.
Videos
Linear Programming 1: An introduction
Linear Programming 2: An analogy between linear programming and linear algebra
Linear Programming 3: Polytopes, cubes, and cross-polytopes
Linear Programming 4: Example application - Healthy diet
Linear Programming 5: Example application - Fitting a line
Linear Programming 6: Example application - Separation of points
Linear Programming 7: Example application - Cutting paper rolls
Linear Programming 8: Example application - Largest disk in a polygon
Linear Programming 9: An introduction to integer linear programming
Linear Programming 10: Integer linear programming remarks
Linear Programming 11: Maximum weight matching
Linear Programming 12: Minimum vertex cover
Linear Programming 13: Maximum independent set
Linear Programming 14: Equational form
Linear Programming 15: Basic feasible solutions - Algebra
Linear Programming 16: Basic feasible solutions - Geometry
Linear Programming 17: The simplex method
Linear Programming 18: The simplex method - Unboundedness
Linear Programming 19: The simplex method - Degeneracy
Linear Programming 20: The simplex method - Infeasibility
Linear Programming 21: The simplex method - In general
Linear Programming 22: The simplex method - Computational remarks
Linear Programming 23: The simplex method - Pivot rules
Linear Programming 24: The simplex method - Efficiency
Linear Programming 25: Duality of linear programming
Linear Programming 26: Proof of weak duality
Linear Programming 27: Optimality is no harder than feasibility
Linear Programming 28: Dualization recipe
Linear Programming 29: A physical interpretation of strong duality
Linear Programming 30: Farkas lemma
Linear Programming 31: A variant of the Farkas lemma
Linear Programming 32: Proof of strong duality from the Farkas lemma
Linear Programming 33: Other algorithms besides the simplex method
Linear Programming 34: Polynomial and strongly polynomial algorithms
Linear Programming 35: Ellipsoid Method I
Linear Programming 36: Ellipsoid Method II
Linear Programming 37: Interior point methods
Linear Programming 38: Interior point methods - The central path
Linear Programming 39: Interior point methods - The primal-dual central path
Linear Programming 40: Matchings and Hall's theorem
Linear Programming 41: Vertex covers and König's theorem
Linear Programming 42: Totally unimodular matrices
Linear Programming 43: Total unimodularity and König's theorem
Linear Programming 44: Maximum flow
Linear Programming 45: Minimum cut
Linear Programming 46: Minimum cut and total unimodularity
Linear Programming 47: Optimal transport
Linear Programming 48: Optimal transport and linear programming
Linear Programming 49: Optimal transport and Kantarovich-Rubenstein duality
Linear Programming 50: The sparsity-promoting L1 norm
Linear Programming 51: The sparsity-promoting L1 norm and neighborly polytopes
Linear Programming 52: Cutting planes
Linear Programming 53: Branch and bound
Schedule
| Date | Class Topic | Remark |
| Aug 25 | Class overview | [Logistical notes] |
| Aug 27 | Introduction to linear programming | |
| Sep 1 | Polytopes, cubes, and cross-polytopes | |
| Sep 3 | Examples | |
| Sept 8 | Examples | |
| Sept 10 | Examples | |
| Sept 15 | Integer linear programming | |
| Sept 17 | Integer linear programming | |
| Sept 22 | Basic feasible solutions, Convex polyhedra | |
| Sept 24 | The simplex method | |
| Sept 29 | The simplex method | |
| Oct 1 | The simplex method | |
| Oct 6 | Duality of linear programming | |
| Oct 8 | Duality of linear programming | |
| Oct 13 | Optional Midterm | |
| Oct 15 | Farkas lemma | |
| Oct 20 | Class cancelled | |
| Oct 22 | The ellipsoid method | |
| Oct 27 | The ellipsoid method | |
| Oct 29 | Interior point methods | |
| Nov 3 | Maximum matchings and minimum vertex covers | |
| Nov 5 | Totally unimodular matrices and König's theorem | |
| Nov 10 | Max-flow and min-cut | |
| Nov 12 | Optimal transport | |
| Nov 17 | Coffee with grandpa! | |
| Nov 19 | Applications: Optimal transport and Kantarovich-Rubenstein duality | [Associated blog post] |
Fall Recess, Nov 23-27 | ||
| Dec 1 | The sparsity-promoting L1 norm | [Associated notes] |
| Dec 3 | Class cancelled | |
| Dec 8 | A cutting-plane algorithm for integer linear programs | [Associated notes] |
| Dec 10 | Branch-and-bound and dynamic programming | [Associated notes] |
Optional Final Exam, Monday December 14 |
||
| 9:40-11:40am, Online | ||