Advanced Linear Programming

Graduate

By presenting results and their proofs, the student will acquire a solid understanding of the theory, algorithms and applications of linear programming. This course is a prerequisite for more advanced courses on integer programming, combinatorial optimization and networks flows. Topics emphasized include: formulations of linear programming problems, convex sets and convex functions, separation theorem, Farkas' lemma, duality theory, economic interpretation of duality, optimality conditions, primal and dual simplex algorithms, cycling, sensitivity analysis, interior-point methods and central path, primal-dual methods, convergence results.