Math 588. Optimization in Networks Instructor Syllabus

OVERVIEW: This is a rigorous introduction to linear programming, network flows and related topics of combinatorial optimization. There is some overlap with Math 482 and Math 412, but the basic material from these classes will be presented more quickly and concisely. Network flow theory is a subject that lies at the cusp among several fields of inquiry, including applied mathematics, engineering, and management.

TOPICS:

• Simplex algorithm: Geometry of Linear Programs, Interpretation of the Dual Simplex Algorithm, Computational Aspects, Dantzig-Wolfe Decomposition, the Ellipsoid Algorithm.
• Minimum Spanning Trees: Greedy Algorithm, Kruskal's, Prim's and Sollins's Algorithms, Relation between Spanning Trees and Matroids.
• Maximum flows: Basic ideas, Max-Flow Min-Cut Theorem, Preflow-Push algorithm, Polymatroidal Network Flow.
• Minimum cost flows: Primal-Dual Algorithm, Out-of-Kilter Algorithm, Relaxation Algorithm, Polynomial Algorithms, Repeated and Enhanced Capacity Scaling Algorithms.
• Branch-and-Bound and Dynamic Programming: Integer Linear Programming, Application to a Flowshop Scheduling Problem.

TEXT: Selected chapters from Combinatorial Optimization, C. H. Papadimitriou, K. Steiglitz (Dover edition), and Network Flows, R. K. Ahuja, T. L. Magnati, J. B. Orlin, (Prentice Hall). Some material may be used from The Art of Combinatorics, Vol. III, D. B. West.