Linear optimization and extensions

Başlık:

Yazar:

Padberg, M. W.

ISBN:

9783540658337

Ek Yazar:

Padberg, M. W.

Edition:

2nd, rev. and expanded ed.

Yayım Bilgisi:

Berlin ; New York : Springer, c1999.

Fiziksel Tanım:

xx, 501 p. : ill. ; 24 cm.

Series:

Algorithms and combinatorics, 12

Series Title:

Algorithms and combinatorics, 0937-5511 ; 12

Konu Terimleri:

Linear programming.

Doğrusal programlama.

Mathematical optimization.

Matematiksel optimizasyon.

Mevcut:*

Library	Materyal Türü	Barkod	Yer Numarası	Durum
Searching... Pamukkale Merkez Kütüphanesi	Kitap	0020648	T57.74.P3 1999	Searching... Unknown

I was pleasantly surprised when I was asked by Springer-Verlag to prepare a second edition of this volume on Linear Optimization and Extensions, which - not exactly contrary to my personal expectations - has apparently been accepted reasonably weIl by the global optimization community. My objective in putting this book together was originally - and still is - to detail the major algorithmic ideas in linear optimization that have evolved in the past fifty years or so and that have changed the historical optimization "landscape" in substantial ways - both theoretically and computationally. While I may have overlooked the importance of some very recent developments - the work by Farid Alizadeh which generalizes linear programming to "sem i-definite" programming is perhaps a candidate for one of my omissions - I think that major new breakthraughs on those two fronts that interest me - theory and computation - have not occurred since this book was published originally. As a consequence I have restricted myself to a thorough re-working of the original manuscript with the goal of making it more readable. Of course, I have taken this opportunity to correct a few "Schönheitsfehler" of the first edition and to add some illustrations. The index to this volume has been extended substantially - to permit a hurried reader a quicker glance at the wealth of topics that were covered nevertheless already in the first edition. As was the case with the first edition, Dr.

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

Mevcut:*

Bound With These Titles

On Order

Özet

Özet

Table of Contents