Simplex methods stem from a basic operation, called pivot algebra, whereas interior point methods are based on the use of penalty functions. This course will cover the simplex method in detail, emphasizing both mathematical foundations as well as computational considerations for effective computer implementations. A brief introduction to interior point methods will also be given. In addition to covering these two algorithms, the course will discuss theoretical aspects of linear programming, such as polyhedral theory, duality theory, optimality conditions, convexity, degeneracy, and convergence theory, as well as sensitivity analysis. Additional topics include network flows problems and large scale optimization.
Objectives Develop an appreciation for the importance and broad applicability of linear programming.
Become comfortable modeling problems as linear programs. Learn the basic mathematical theory of linear programming. Gain a detailed understanding of the simplex algorithm. Achieve a strong understanding of duality. Learn to interpret solutions to linear programs and how to perform sensitivity analysis.