Math 510: Linear Programming and Network Flows

Colorado State University, Fall 2022

Instructor: Henry Adams
Email: henry dot adams at colostate dot edu
Office: Weber 120

Lectures: TR 9:30-10:45am, in Clark C360
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, max flow and min cut, integer linear programming, Farkas lemma, ellipsoid method, interior point methods, total unimodularity, optimal transport, sparsity-promoting L¹ norm, quadratic programming.

Goals: Students will become fluent with the main ideas and the language of linear programming, and will be able to communicate these ideas to others.

Syllabus: Here is the course syllabus.

Course notes: Here are Henry's course notes as a PDF (or as a Notability source code file).

Mini-projects

Mini-project 1: The first mini-project is due on Thursday, October 13. Please see the Mini-project 1 description.
Mini-project 2: The second mini-project is due on Thursday, December 8. Please see the Mini-project 2 description.

Videos

The following videos are from Fall 2020.

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 23	Class overview	[Video 1]
Aug 25	Introduction to linear programming	[Video 1, Video 2]

Aug 30	Polytopes, cubes, and cross-polytopes	[Video 3, Link]
Sep 1	Examples; Spontaneous introduction to SVM	[Video 4, Video 5, Video 6]

Sept 6	Examples	[Video 6, Video 7, Video 9]
Sept 8	Integer linear programming	[Video 9, Video 10, Video 11, Video 13]

Sept 13	Integer linear programming	[Video 12, Link]
Sept 15	Equational from of a linear program	[Video 14]

Sept 20	Basic feasible solutions, Convex polyhedra	[Video 15, Video 16]
Sept 22	Work on mini-project

Sept 27	Work on mini-project
Sept 29	Work on mini-project

Oct 4	The simplex method	[Video 17, Video 18]
Oct 6	The simplex method	[Video 19, Video 20]

Oct 11	The simplex method	[Video 21, Video 22]
Oct 13	The simplex method; Duality of linear programming	[Video 23, Video 24, Video 25], First mini-project due

Oct 18	Duality of linear programming	[Video 26, Video 27, Video 28]
Oct 20	Farkas lemma, Waylon Jepsen presentation	[Video 29, Video 30]

Oct 25	Class cancelled
Oct 27	Farkas lemma, The ellipsoid method	[Video 31, Video 32, Video 33, Video 35]

Nov 1	The ellipsoid method, Interior point methods	[Video 36, Video 37, Video 38]
Nov 3	Maximum matchings and minimum vertex covers	[Video 39, Video 40, Video 41]

Nov 8	Totally unimodular matrices and König's theorem	[Video 42, Video 43]
Nov 10	Max-flow and min-cut	[Video 44, Video 45, Video 46]

Nov 15	Optimal transport	[Video 47, Video 48]
Nov 17	Applications: Optimal transport and Kantarovich-Rubenstein duality	[Video 49, Associated blog post]
Fall Recess, Nov 21-25
Nov 29	The sparsity-promoting L¹ norm	[Associated notes]
Dec 1	Class cancelled

Dec 6	Cutting planes; Branch-and-bound and dynamic programming	[Associated notes 1, Associated notes 2]
Dec 8	Convex optimization	[Associated video], Second mini-project due