Introduction / 1: |
Some Issues in Linear Computation / 1.1: |
Three Examples of Linear Computation / 1.2: |
Gargantuan Liquids, Inc / 1.2.1: |
Oil Refineries, bpd / 1.2.2: |
Save Berlin, usw / 1.2.3: |
The Linear Programming Problem / 2: |
Standard and Canonical Forms / 2.1: |
Matrices, Vectors, Scalars / 2.2: |
Basic Concepts / 3: |
A Fundamental Theorem / 3.1: |
Notational Conventions and Illustrations / 3.2: |
Five Preliminaries / 4: |
Bases and Basic Feasible Solutions / 4.1: |
Detecting Optimality / 4.2: |
Detecting Unboundedness / 4.3: |
A Rank-One Update / 4.4: |
Changing Bases / 4.5: |
Simplex Algorithms / 5: |
Notation, Reading Instructions, Updating / 5.1: |
Big M or How to Get Started / 5.2: |
Selecting a Pivot Row and Column / 5.3: |
Data Structures, Tolerances, Product Form / 5.4: |
Equation Format and Cycling / 5.5: |
Finiteness of a Simplex Algorithm / 5.6: |
Canonical Form / 5.7: |
A Worst-Case Example for a Simplex Algorithm / 5.7.1: |
Block Pivots and Structure / 5.8: |
A Generalized Product Form / 5.8.1: |
Upper Bounds / 5.8.2: |
Primal-Dual Pairs / 6: |
Weak Duality / 6.1: |
Strong Duality / 6.2: |
Economic Interpretation and Applications / 6.2.1: |
Solvability, Redundancy, Separability / 6.3: |
A Dual Simplex Algorithm / 6.4: |
Correctness, Finitenoss, Initialization / 6.4.1: |
Post-Optimality / 6.5: |
A Dynamic Simplex Algorithm / 6.6: |
Analytical Geometry / 7: |
Points, Linos, Subspaces / 7.1: |
Polyhedra, Ideal Descriptions, Cones / 7.2: |
Faces, Valid Equations, Affine Hulls / 7.2.1: |
Facets, Minimal Complete Descriptions, Quasi-Uniqueness / 7.2.2: |
Asymptotic Cones and Extreme Rays / 7.2.3: |
Adjacency I, Extreme Rays of Polyhedra, Homogenization / 7.2.4: |
Point Sets, Affine Transformations, Minimal Generators / 7.3: |
Displaced Cones, Adjacency II, Images of Polyhedra / 7.3.1: |
Carathéodory, Minkowski, Weyl / 7.3.2: |
Minimal Generators, Canonical Generators, Quasi-Uniqueness / 7.3.3: |
Double Description Algorithms / 7.4: |
Correctness and Finitenoss of the Algorithm / 7.4.1: |
Geometry, Euclidean Reduction, Analysis / 7.4.2: |
The Basis Algorithm and All-Integer Inversion / 7.4.3: |
An All-Integer Algorithm for Double Description / 7.4.4: |
Digital Sizes of Rational Polyhedra and Linear Optimization / 7.5: |
Facet Complexity, Vertex Complexity, Complexity of Inversion / 7.5.1: |
Polyhedra and Related Polytopes for Linear Optimization / 7.5.2: |
Feasibility, Binary Search, Linear Optimization / 7.5.3: |
Perturbation, Uniqueness, Separation / 7.5.4: |
Geometry and Complexity of Simplex Algorithms / 7.6: |
Pivot Column Choice, Simplex Paths, Big M Revisited / 7.6.1: |
Gaussian Elimination, Fill-In, Scaling / 7.6.2: |
Iterative Step I, Pivot Choice, Cholesky Factorization / 7.6.3: |
Cross Multiplication, Iterative Step II, Integer Factorization / 7.6.4: |
Division Free Gaussian Elimination and Cramer's Rule / 7.6.5: |
Circles, Spheres, Ellipsoids / 7.7: |
Projective Algorithms / 8: |
A Basic Algorithm / 8.1: |
The Solution of the Approximate Problem / 8.1.1: |
Convergence of the Approximate Iterates / 8.1.2: |
Correctness, Finiteness, Initialization / 8.1.3: |
Analysis, Algebra, Geometry / 8.2: |
Solution to the Problem in the Original Space / 8.2.1: |
The Solution in the Transformed Space / 8.2.2: |
Geometric Interpretations and Properties / 8.2.3: |
Extending the Exact Solution and Proofs / 8.2.4: |
Examples of Projective Images / 8.2.5: |
The Cross Ratio / 8.3: |
Reflection on a Circle and Sandwiching / 8.4: |
The Iterative Step / 8.4.1: |
A Projective Algorithm / 8.5: |
Centers, Barriers, Newton Steps / 8.6: |
A Method of Centers / 8.6.1: |
The Logarithmic Barrier Function / 8.6.2: |
A Newtonian Algorithm / 8.6.3: |
Coda / 8.7: |
Ellipsoid Algorithms / 9: |
Matrix Norms, Approximate Inverses, Matrix Inequalities / 9.1: |
Ellipsoid "Halving" in Approximate Arithmetic / 9.2: |
Polynomial-Time Algorithms for Linear Programming / 9.3: |
Linear Programming and Binary Search / 9.3.1: |
Deep Cuts, Sliding Objective, Large Steps, Line Search / 9.4: |
Linear Programming the Ellipsoidal Way: Two Examples / 9.4.1: |
Correctness and Finiteness of the DCS Ellipsoid Algorithm / 9.4.2: |
Optimal Separators, Most Violated Separators, Separation / 9.5: |
?-Solidification of Flats, Polytopal Norms, Rounding / 9.6: |
Rational Rounding and Continued Fractions / 9.6.1: |
Optimization and Separation / 9.7: |
?-Optimal Sets and ?-Optimal Solutions / 9.7.1: |
Finding Direction Vectors in the Asymptotic Cone / 9.7.2: |
A CCS Ellipsoid Algorithm / 9.7.3: |
Linear Optimization and Polyhedral Separation / 9.7.4: |
Combinatorial Optimization: An Introduction / 10: |
The Berlin Airlift Model Revisited / 10.1: |
Complete Formulations and Their Implications / 10.2: |
Extremal Characterizations of Ideal Formulations / 10.3: |
Blocking and Antiblocking Polyhedra / 10.3.1: |
Polyhedra with the Integrality Property / 10.4: |
Appendices |
Short-Term Financial Management / A: |
Operations Management in a Refinery / B: |
Automatized Production: PCBs and Ulysses' Problem / C: |
References |
Bibliography |
Index |
Introduction / 1: |
Some Issues in Linear Computation / 1.1: |
Three Examples of Linear Computation / 1.2: |