Title:
Linear optimization and extensions
Personal Author:
Series:
Algorithms and combinatorics ; 12
Publication Information:
Berlin : Springer-Verlag, 1995
ISBN:
9783540587347
Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000003365941 | T57.74 P32 1995 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
This is a collection of classic character sketches based on specific passages of Scripture.
Table of Contents
1 Introduction | p. 1 |
1.1 Some Issues in Linear Computation | p. 7 |
1.2 Three Examples of Linear Computation | p. 13 |
1.2.1 Gargantuan Liquids, Inc | p. 13 |
1.2.2 Oil Refineries, bpd | p. 15 |
1.2.3 Save Berlin, usw | p. 20 |
2 The Linear Programming Problem | p. 25 |
2.1 Standard and Canonical Forms | p. 26 |
2.2 Matrices, Vectors, Scalars | p. 27 |
3 Basic Concepts | p. 33 |
3.1 A Fundamental Theorem | p. 36 |
3.2 Notational Conventions and Illustrations | p. 39 |
4 Five Preliminaries | p. 43 |
4.1 Bases and Basic Feasible Solutions | p. 43 |
4.2 Detecting Optimality | p. 43 |
4.3 Detecting Unboundedness | p. 44 |
4.4 A Rank-One Update | p. 45 |
4.5 Changing Bases | p. 45 |
5 Simplex Algorithms | p. 49 |
5.1 Notation, Reading Instructions, Updating | p. 50 |
5.2 Big M or How to Get Started | p. 54 |
5.3 Selecting a Pivot Row and Column | p. 56 |
5.4 Data Structures, Tolerances, Product Form | p. 58 |
5.5 Equation Format and Cycling | p. 63 |
5.6 Finiteness of a Simplex Algorithm | p. 69 |
5.7 Canonical Form | p. 71 |
5.7.1 A Worst-Case Example for a Simplex Algorithm | p. 75 |
5.8 Block Pivots and Structure | p. 77 |
5.8.1 A Generalized Product Form | p. 79 |
5.8.2 Upper Bounds | p. 82 |
6 Primal-Dual Pairs | p. 87 |
6.1 Weak Duality | p. 89 |
6.2 Strong Duality | p. 91 |
6.2.1 Economic Interpretation and Applications | p. 94 |
6.3 Solvability, Redundancy, Separability | p. 97 |
6.4 A Dual Simplex Algorithm | p. 103 |
6.4.1 Correctness, Finitenoss, Initialization | p. 105 |
6.5 Post-Optimality | p. 109 |
6.6 A Dynamic Simplex Algorithm | p. 114 |
7 Analytical Geometry | p. 121 |
7.1 Points, Linos, Subspaces | p. 124 |
7.2 Polyhedra, Ideal Descriptions, Cones | p. 131 |
7.2.1 Faces, Valid Equations, Affine Hulls | p. 134 |
7.2.2 Facets, Minimal Complete Descriptions, Quasi-Uniqueness | p. 138 |
7.2.3 Asymptotic Cones and Extreme Rays | p. 141 |
7.2.4 Adjacency I, Extreme Rays of Polyhedra, Homogenization | p. 144 |
7.3 Point Sets, Affine Transformations, Minimal Generators | p. 147 |
7.3.1 Displaced Cones, Adjacency II, Images of Polyhedra | p. 150 |
7.3.2 Carathéodory, Minkowski, Weyl | p. 155 |
7.3.3 Minimal Generators, Canonical Generators, Quasi-Uniqueness | p. 157 |
7.4 Double Description Algorithms | p. 165 |
7.4.1 Correctness and Finitenoss of the Algorithm | p. 168 |
7.4.2 Geometry, Euclidean Reduction, Analysis | p. 173 |
7.4.3 The Basis Algorithm and All-Integer Inversion | p. 180 |
7.4.4 An All-Integer Algorithm for Double Description | p. 183 |
7.5 Digital Sizes of Rational Polyhedra and Linear Optimization | p. 188 |
7.5.1 Facet Complexity, Vertex Complexity, Complexity of Inversion | p. 190 |
7.5.2 Polyhedra and Related Polytopes for Linear Optimization | p. 194 |
7.5.3 Feasibility, Binary Search, Linear Optimization | p. 197 |
7.5.4 Perturbation, Uniqueness, Separation | p. 202 |
7.6 Geometry and Complexity of Simplex Algorithms | p. 207 |
7.6.1 Pivot Column Choice, Simplex Paths, Big M Revisited | p. 208 |
7.6.2 Gaussian Elimination, Fill-In, Scaling | p. 212 |
7.6.3 Iterative Step I, Pivot Choice, Cholesky Factorization | p. 216 |
7.6.4 Cross Multiplication, Iterative Step II, Integer Factorization | p. 219 |
7.6.5 Division Free Gaussian Elimination and Cramer's Rule | p. 221 |
7.7 Circles, Spheres, Ellipsoids | p. 229 |
8 Projective Algorithms | p. 239 |
8.1 A Basic Algorithm | p. 243 |
8.1.1 The Solution of the Approximate Problem | p. 245 |
8.1.2 Convergence of the Approximate Iterates | p. 246 |
8.1.3 Correctness, Finiteness, Initialization | p. 250 |
8.2 Analysis, Algebra, Geometry | p. 253 |
8.2.1 Solution to the Problem in the Original Space | p. 254 |
8.2.2 The Solution in the Transformed Space | p. 260 |
8.2.3 Geometric Interpretations and Properties | p. 264 |
8.2.4 Extending the Exact Solution and Proofs | p. 268 |
8.2.5 Examples of Projective Images | p. 271 |
8.3 The Cross Ratio | p. 274 |
8.4 Reflection on a Circle and Sandwiching | p. 278 |
8.4.1 The Iterative Step | p. 283 |
8.5 A Projective Algorithm | p. 288 |
8.6 Centers, Barriers, Newton Steps | p. 292 |
8.6.1 A Method of Centers | p. 296 |
8.6.2 The Logarithmic Barrier Function | p. 298 |
8.6.3 A Newtonian Algorithm | p. 303 |
8.7 Coda | p. 308 |
9 Ellipsoid Algorithms | p. 309 |
9.1 Matrix Norms, Approximate Inverses, Matrix Inequalities | p. 316 |
9.2 Ellipsoid "Halving" in Approximate Arithmetic | p. 320 |
9.3 Polynomial-Time Algorithms for Linear Programming | p. 328 |
9.3.1 Linear Programming and Binary Search | p. 336 |
9.4 Deep Cuts, Sliding Objective, Large Steps, Line Search | p. 339 |
9.4.1 Linear Programming the Ellipsoidal Way: Two Examples | p. 344 |
9.4.2 Correctness and Finiteness of the DCS Ellipsoid Algorithm | p. 348 |
9.5 Optimal Separators, Most Violated Separators, Separation | p. 352 |
9.6 ¿-Solidification of Flats, Polytopal Norms, Rounding | p. 356 |
9.6.1 Rational Rounding and Continued Fractions | p. 361 |
9.7 Optimization and Separation | p. 368 |
9.7.1 ¿-Optimal Sets and ¿-Optimal Solutions | p. 371 |
9.7.2 Finding Direction Vectors in the Asymptotic Cone | p. 373 |
9.7.3 A CCS Ellipsoid Algorithm | p. 375 |
9.7.4 Linear Optimization and Polyhedral Separation | p. 378 |
10 Combinatorial Optimization: An Introduction | p. 387 |
10.1 The Berlin Airlift Model Revisited | p. 389 |
10.2 Complete Formulations and Their Implications | p. 396 |
10.3 Extremal Characterizations of Ideal Formulations | p. 405 |
10.3.1 Blocking and Antiblocking Polyhedra | p. 414 |
10.4 Polyhedra with the Integrality Property | p. 417 |
Appendices | |
A Short-Term Financial Management | p. 423 |
B Operations Management in a Refinery | p. 427 |
C Automatized Production: PCBs and Ulysses' Problem | p. 441 |
References | p. 457 |
Bibliography | p. 479 |
Index | p. 495 |