# Math 510: Linear Programming and Network Flows

## 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 |