Linear Optimization and Extensions

1 Introduction.- 1.1 Minicases and Exercises.- 2 The Linear Programming Problem.- 2.1 Exercises.- 3 Basic Concepts.- 3.1 Exercises.- 4 Five Preliminaries.- 4.1 Exercises.- 5 Simplex Algorithms.- 5.1 Exercises.- 6 Primal-Dual Pairs.- 6.1 Exercises.- 7 Analytical Geometry.- 7.1 Points, Lines, Subspaces.- 7.2 Polyhedra, Ideal Descriptions, Cones.- 7.3 Point Sets, Affine Transformations, Minimal Generators.- 7.4 Double Description Algorithms.- 7.5 Digital Sizes of Rational Polyhedra and Linear Optimization.- 7.6 Geometry and Complexity of Simplex Algorithms.- 7.7 Circles, Spheres, Ellipsoids.- 7.8 Exercises.- 8 Projective Algorithms.- 8.1 A Basic Algorithm.- 8.2 Analysis, Algebra, Geometry.- 8.3 The Cross Ratio.- 8.4 Reflection on a Circle and Sandwiching.- 8.5 A Projective Algorithm.- 8.6 Centers, Barriers, Newton Steps.- 8.7 Exercises.- 9 Ellipsoid Algorithms.- 9.1 Matrix Norms, Approximate Inverses, Matrix Inequalities.- 9.2 Ellipsoid “Halving” in Approximate Arithmetic.- 9.3 Polynomial-Time Algorithms for Linear Programming.- 9.4 Deep Cuts, Sliding Objective, Large Steps, Line Search.- 9.5 Optimal Separators, Most Violated Separators, Separation.- 9.6 ?-Solidification of Flats, Polytopal Norms, Rounding.- 9.7 Optimization and Separation.- 9.8 Exercises.- 10 Combinatorial Optimization: An Introduction.- 10.1 The Berlin Airlift Model Revisited.- 10.2Complete Formulations and Their Implications.- 10.3 Extremal Characterizations of Ideal Formulations.- 10.4 Polyhedra with the Integrality Property.- 10.5 Exercises.- Appendices.- A Short-Term Financial Management.- A. 1 Solution to the Cash Management Case.- B Operations Management in a Refinery.- B.l Steam Production in a Refinery.- B.2 The Optimization Problem.- B.3 Technological Constraints, Profits and Costs.- B.4Formulation of the Problem.- B.5 Solution to the Refinery Case.- C Automatized Production: PCBs and Ulysses’ Problem.- C.l Solutions to Ulysses’ Problem.