Linear optimization and extensions

de M. W. Padberg

This book offers a comprehensive treatment of linear programming as well as of the optimization of linear functions over polyhedra in finite dimensional Euclidean vector spaces. An introduction surveying fifty years of linear optimization is given. Here are the book's main topics. Simplex algorithms and their derivatives, the duality theory of linear programming. Polyhedral theory, pointwise and linear descriptions of double description algorithms, Gaussian elimination with and without division, the complexity of simplex steps. Projective algorithms, the geometry of projective algorithms, Newtonian barrier methods. Ellipsoid algorithms in perfect and in finite precision arithmetic, the equivalence of linear optimization and polyhedral separation. The foundations of mixed integer programming. The book can serve both as a graduate textbook and as a text for advanced topics classes or seminars. Exercises as well as several case studies are included.