Prerequisites: None
Contents:
Formulating Linear Optimization Models. Examples from production planning, scheduling, investment analysis, blending products, ridesharing, sports, healthcare, etc. Modeling problems with piecewise linear convex functions.
Solving Linear Optimization Problems. Extreme point optimality. Basic feasible solutions and the standard-form LP. The simplex method.
Linear Optimization Software. Solving linear programming problems using software tools like PuLP. Extracting useful information from the solutions.
Linear Optimization Duality. How to get bounds on the objective function? The dual Linear Program. Relationship between primal and dual linear programs. Complementary slackness and sensitivity analysis.
Network Flow Problems. Linear Programming formulations of Shortest Path, Maximum Flow, Min Cost flow, and their duals. Emphasize that most shortest path algorithms solve the dual LP. Modeling problems as shortest path problems—production planning, cyclic scheduling, etc. Maximum Flow and minimum cuts. Modeling problems such as Assignment, Baseball Elimination, Open pit mining, etc.
Algorithms for Network Flow Problems. A brief introduction to algorithms for shortest path problems. Dijkstra’s Algorithm. Practical algorithms like the A* algorithm.
References:
- Wayne Winston, Operations Research: Applications and Algorithms, 2003.
- Jon Lee, A First Course in Linear Optimization, Second Edition, Reex Press, 2013.
- Bradley, Hax, and Magnanti, Applied Mathematical Programming, 1977
- Ahuja, Magnanti, and James B. Orlin, Network Flows: Theory, Algorithms, and Applications, 1993