Linear Programming

A good understanding of the theory and algorithms of linear programming is essential for understanding integer programming. Integer programming is a much harder problem than linear programming, and neither the theory nor the computational aspects of integer programming are as developed as they are for linear programming. So, first of all, the theory of linear programming serves as a guide and motivating force for developing results for integer programming. Computationally, linear programming algorithms are very often used as a subroutine in integer programming algorithms to obtain upper bounds on the value of the integer program. This chapter considers the duality theory of linear programming, which provides necessary and sufficient optimality conditions. It presents algorithms for solving linear programs, and finally deals with subgradient optimization.