# 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 ^{1}* 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^{1} |
[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 |