Math 482
Course Documents & Links
Lecture Notes
Simplex Method:
Lecture 1: Introduction to Linear Programming
Lecture 2: Convex sets, feasible regions of linear programs, standard/canonical and equational forms
Lecture 3: Basic feasible solutions, pivoting
Lecture 4: Simplex tableaux, objective functions
Lecture 5: Simplex method examples (unbounded LPs, degenerate pivoting)
Lecture 6: Two-phase simplex method
Lecture 7: Pivoting rules
Lecture 8: Vertices, extreme points, and BFS
Lecture 9: Formulas for simplex tableaux
Lecture 10: Revised simplex method
Lecture 11: "Worst case scenarios" for the simplex method
Duality:
Lecture 12: Introduction to Duality
"Sensible Rules for Remembering Duals" - a short article by Arthur Benjamin that you may find usefulLecture 13: Complementary Slackness
Lecture 14: Duality & Simplex tableau
Lecture 15: Dual simplex method (+ additional example that we didn't cover in class)
Lecture 16: Finding BFS & Introduction to sensitivity analysis
Lecture 17: More sensitivity analysis
Lecture 18: Introduction to zero-sum games
Lecture 19: Optimality and duality in zero-sum games
Lecture 20: Fourier-Motzkin Elimination, Farkas' Lemma
Graph Theory:
Lecture 21: Bipartite graphs, maximum matching and minimum vertex cover problems
Lecture 22: Totally unimodular matrices, integrality of optimal solutions
Lecture 23: Introduction to networks
Lecture 24: Max-flow, min-cut theorem
Lecture 25: Directed and augmenting paths
Lecture 26: Ford-Fulkerson Algorithm
Quanta article about a new maximum-flow algorithm (optional, for-fun reading)Lecture 27: Variants on max-flow problems
Lecture 28: Minimum-cost flow problems
Lecture 29: Two-phase simplex method for minimum-cost flow problems
Primal-Dual Algorithm:
Lecture 30: Introduction to the primal-dual algorithm
Lecture 31: Finding the direction vector from the restricted primal program
Lecture 32: Finding initial feasible points, application to the Ford-Fulkerson algorithm
Integer Linear Programs:
Lecture 33: Relaxation linear programs, branch & bound method
Lecture 34: Wrapping up branch & bound, cutting plane method
Lecture 35: The traveling salesperson problem
Lecture 36: Timing constraints for TSP, approximation algorithms
Lecture 37: Greedy algorithm for vertex covers, metric TSP, end-of-semester logistics
Homework Assignments
As mentioned in the syllabus, I highly encourage typesetting assignments rather than writing by hand. You may wish to do so using Overleaf, which is free and cloud-based. In case you find it helpful, I have created a basic template for homework in this course (the TeX code is available here). You are not required to use this template or to use LaTeX.
Other Resources
"Guidelines for good mathematical writing," by Francis Su.
Detexify, a web app for identifying the LaTeX command(s) for various symbols.
Overleaf, a cloud-based LaTeX editor.