| |
| |
| |
| Introduction | |
| |
| |
| |
| Minicases and Exercises | |
| |
| |
| |
| The Linear Programming Problem | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Basic Concepts | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Five Preliminaries | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Simplex Algorithms | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Primal-Dual Pairs | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Analytical Geometry | |
| |
| |
| |
| Points, Lines, Subspaces | |
| |
| |
| |
| Polyhedra, Ideal Descriptions, Cones | |
| |
| |
| |
| Faces, Valid Equations, Affine Hulls | |
| |
| |
| |
| Facets, Minimal Complete Descriptions, Quasi-Uniqueness | |
| |
| |
| |
| Asymptotic Cones and Extreme Rays | |
| |
| |
| |
| Adjacency I, Extreme Rays of Polyhedra, Homogenization | |
| |
| |
| |
| Point Sets, Affine Transformations, Minimal Generators | |
| |
| |
| |
| Displaced Cones, Adjacency II, Images of Polyhedra | |
| |
| |
| |
| Carath�odory, Minkowski, Weyl | |
| |
| |
| |
| Minimal Generators, Canonical Generators, Quasi-Uniqueness | |
| |
| |
| |
| Double Description Algorithms | |
| |
| |
| |
| Correctness and Finiteness of the Algorithm | |
| |
| |
| |
| Geometry, Euclidean Reduction, Analysis | |
| |
| |
| |
| The Basis Algorithm and All-Integer Inversion | |
| |
| |
| |
| An All-Integer Algorithm for Double Description | |
| |
| |
| |
| Digital Sizes of Rational Polyhedra and Linear Optimization | |
| |
| |
| |
| Facet Complexity, Vertex Complexity, Complexity of Inversion | |
| |
| |
| |
| Polyhedra and Related Polytopes for Linear Optimization | |
| |
| |
| |
| Feasibility, Binary Search, Linear Optimization | |
| |
| |
| |
| Perturbation, Uniqueness, Separation | |
| |
| |
| |
| Geometry and Complexity of Simplex Algorithms | |
| |
| |
| |
| Pivot Column Choice, Simplex Paths, Big M Revisited | |
| |
| |
| |
| Gaussian Elimination, Fill-In, Scaling | |
| |
| |
| |
| Iterative Step I, Pivot Choice, Cholesky Factorization | |
| |
| |
| |
| Cross Multiplication, Iterative Step II, Integer Factorization | |
| |
| |
| |
| Division Free Gaussian Elimination and Cramer's Rule | |
| |
| |
| |
| Circles, Spheres, Ellipsoids | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Projective Algorithms | |
| |
| |
| |
| A Basic Algorithm | |
| |
| |
| |
| The Solution of the Approximate Problem | |
| |
| |
| |
| Convergence of the Approximate Iterates | |
| |
| |
| |
| Correctness, Finiteness, Initialization | |
| |
| |
| |
| Analysis,Algebra,Geometry | |
| |
| |
| |
| Solution to the Problem in the Original Space | |
| |
| |
| |
| The Solution in the Transformed Space | |
| |
| |
| |
| Geometric Interpretations and Properties | |
| |
| |
| |
| Extending the Exact Solution and Proofs | |
| |
| |
| |
| Examples of Projective Images | |
| |
| |
| |
| The Cross Ratio | |
| |
| |
| |
| Reflection on a Circle and Sandwiching | |
| |
| |
| |
| The Iterative Step | |
| |
| |
| |
| AProjectiveAlgorithm | |
| |
| |
| |
| Centers, Barriers, Newton Steps | |
| |
| |
| |
| A Method of Centers | |
| |
| |
| |
| The Logarithmic Barrier Function | |
| |
| |
| |
| A Newtonian Algorithm | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Ellipsoid Algorithms | |
| |
| |
| |
| Matrix Norms, Approximate Inverses, Matrix Inequalities | |
| |
| |
| |
| Ellipsoid "Halving" in Approximate Arithmetic | |
| |
| |
| |
| Polynomial-Time Algorithms for Linear Programming | |
| |
| |
| |
| Deep Cuts, Sliding Objective, Large Steps, Line Search | |
| |
| |
| |
| Linear Programming the Ellipsoidal Way: Two Examples | |
| |
| |
| |
| Correctness and Finiteness of the DCS Ellipsoid Algorithm | |
| |
| |
| |
| Optimal Separators, Most Violated Separators, Separation | |
| |
| |
| |
| �-Solidification of Flats, Polytopal Norms, Rounding | |
| |
| |
| |
| Rational Rounding and Continued Fractions | |
| |
| |
| |
| Optimization and Separation | |
| |
| |
| |
| �-Optimal Sets and �-Optimal Solutions | |
| |
| |
| |
| Finding Direction Vectors in the Asymptotic Cone | |
| |
| |
| |
| A CCS Ellipsoid Algorithm | |
| |
| |
| |
| Linear Optimization and Polyhedral Separation | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Combinatorial Optimization: An Introduction | |
| |
| |
| |
| The Berlin Airlift Model Revisited | |
| |
| |
| |
| Complete Formulations and TheirImplications | |
| |
| |
| |
| Extremal Characterizations of Ideal Formulations | |
| |
| |
| |
| Polyhedra with the IntegralityProperty | |
| |
| |
| |
| Exercises | |
| |
| |
| Appendices | |
| |
| |
| |
| Short-Term Financial Management | |
| |
| |
| |
| Solution to the Cash Management Case | |
| |
| |
| |
| Operations Management in a Refinery | |
| |
| |
| |
| Steam Production in a Refinery | |
| |
| |
| |
| The Optimization Problem | |
| |
| |
| |
| Technological Constraints, Profits and Costs | |
| |
| |
| |
| Formulation of the Problem | |
| |
| |
| |
| Solution to the Refinery Case | |
| |
| |
| |
| Automatized Production: PCBs and Ulysses' Problem | |
| |
| |
| |
| Solutions to Ulysses'Problem | |
| |
| |
| Bibliography | |
| |
| |
| Index | |