NetSys 253 Linear Optimization Methods (3) [cross-listed with EECS 261A]. Formulation, solution, and analysis of linear programming and linear network flow problems. Simplex methods, dual ascent methods, interior point algorithms and auction algorithms. Duality theory and sensitivity analysis. Shortest path, max-flow, assignment, and minimum cost flow problems. Prerequisite: Mathematics 2J or consent of instructor.

• Simplex method: degeneracy, efficiency, duality, sensitivity, implementation
• Duality: weak and strong duality, complimentary slackness
• Game theory: minimax theorem, matrix games
• Regression: L_1/L_2/L_infinity Regression, weighted least squares
• Network flow problems and applications: shortest path, maximum-flow, assignment, transportation
• Interior point methods: central path, path following, and affine scaling methods, KKT conditions
• Integer programming: branch and bound algorithm