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.2.1 Faces, Valid Equations, Affine Hulls.- 7.2.2 Facets, Minimal Complete Descriptions, Quasi-Uniqueness.- 7.2.3 Asymptotic Cones and Extreme Rays.- 7.2.4 Adjacency I, Extreme Rays of Polyhedra, Homogenization.- 7.3 Point Sets, Affine Transformations, Minimal Generators.- 7.3.1 Displaced Cones, Adjacency II, Images of Polyhedra.- 7.3.2 Carathéodoiy, Minkowski, Weyl.- 7.3.3 Minimal Generators, Canonical Generators, Quasi-Uniqueness.- 7.4 Double Description Algorithms.- 7.4.1 Correctness and Finiteness of the Algorithm.- 7.4.2 Geometry, Euclidean Reduction, Analysis.- 7.4.3 The Basis Algorithm and All-Integer Inversion.- 7.4.4 An All-Integer Algorithm for Double Description.- 7.5 Digital Sizes of Rational Polyhedra and Linear Optimization.- 7.5.1 Facet Complexity, Vertex Complexity, Complexity of Inversion.- 7.5.2 Polyhedra and Related Polytopes for Linear Optimization.- 7.5.3 Feasibility, Binary Search, Linear Optimization.- 7.5.4 Perturbation, Uniqueness, Separation.- 7.6 Geometry and Complexity of Simplex Algorithms.- 7.6.1 Pivot Column Choice, Simplex Paths, Big M Revisited.- 7.6.2 Gaussian Elimination, Fill-In, Scaling.- 7.6.3 Iterative Step I, Pivot Choice, Cholesky Factorization.- 7.6.4 Cross Multiplication, Iterative Step II, Integer Factorization.- 7.6.5 Division Free Gaussian Elimination and Cramer’s Rule.- 7.7 Circles, Spheres, Ellipsoids.- 7.8 Exercises.- 8 Projective Algorithms.- 8.1 A Basic Algorithm.- 8.1.1 The Solution of the Approximate Problem.- 8.1.2 Convergence of the Approximate Iterates.- 8.1.3 Correctness, Finiteness, Initialization.- 8.2 Analysis, Algebra, Geometry.- 8.2.1 Solution to the Problem in the Original Space.- 8.2.2 The Solution in the Transformed Space.- 8.2.3 Geometric Interpretations and Properties.- 8.2.4 Extending the Exact Solution and Proofs.- 8.2.5 Examples of Projective Images.- 8.3 The Cross Ratio.- 8.4 Reflection on a Circle and Sandwiching.- 8.4.1 The Iterative Step.- 8.5 A Projective Algorithm.- 8.6 Centers, Barriers, Newton Steps.- 8.6.1 A Method of Centers.- 8.6.2 The Logarithmic Barrier Function.- 8.6.3 A Newtonian Algorithm.- 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.4.1 Linear Programming the Ellipsoidal Way: Two Examples.- 9.4.2 Correctness and Finiteness of the DCS Ellipsoid Algorithm.- 9.5 Optimal Separators, Most Violated Separators, Separation.- 9.6 ?-Solidification of Flats, Polytopal Norms, Rounding.- 9.6.1 Rational Rounding and Continued Fractions.- 9.7 Optimization and Separation.- 9.7.1 ?-Optimal Sets and ?-Optimal Solutions.- 9.7.2 Finding Direction Vectors in the Asymptotic Cone.- 9.7.3 A CCS Ellipsoid Algorithm.- 9.7.4 Linear Optimization and Polyhedral 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.4 Formulation of the Problem.- B.5 Solution to the Refinery Case.- C Automatized Production: PCBs and Ulysses’ Problem.- C.l Solutions to Ulysses’ Problem.