+612 9045 4394
Linear Optimization and Extensions : Algorithms and Combinatorics - Manfred W. Padberg

Linear Optimization and Extensions

Algorithms and Combinatorics


Published: July 1999
Ships: 7 to 10 business days
7 to 10 business days
RRP $278.99
or 4 easy payments of $48.19 with Learn more
if ordered within

Other Available Formats (Hide)

  • Paperback View Product Published: 15th December 2010

Introduction.- The Linear Programming Problem.- Basic Concepts.- Five Preliminaries.- Simplex Algorithms.- Primal-Dual Pairs.- Analytical Geometry.- Projective Algorithms.- Ellipsoid Algorithms.- Combinatorial Optimization: An Introduction Appendices.- Short-Term Financial Management.- Operations Management in a Refinery.- Automatized Production: PCBs and Ulysses' Problem.- References.- Bibliography.

From the reviews of the second edition: "Do you know M.Padberg's Linear Optimization and Extensions (second edition, Springer-Verlag, Berlin, 1999)? If you teach a course on linear programming then you should know it. It is a successful book on LP with many application driven exercises. Now here is the continuation of it, discussing the solutions of all its exercises and with detailed analysis of the applications mentioned. Tell your student about it. ... For those who cherish the original textbook (students and lecturers) this is an extremely valuable sequel. For those who strive for good exercises and case studies for LP this is an excellent volume." Peter Hajnal, Acta Scientiarum Mathematicarum, Vol. 69, 2003 "Linear Optimization and Extensions - Problems and Solutions - is a solution manual for another book, released in 2000 ... . The book is a very well planned and written. ... For professors and interested students, the book can also serve as a source of advanced exercises. ... the book will prove invaluable not only for students, but also for professionals in industry and universities. This is certainly an important addition to the literature of the area of linear programming." (Carlos Oliveria, SIGACT News, Vol. 35 (4), 2004)

Introductionp. 1
Some Issues in Linear Computationp. 7
Three Examples of Linear Computationp. 13
Gargantuan Liquids, Incp. 13
Oil Refineries, bpdp. 15
Save Berlin, uswp. 20
The Linear Programming Problemp. 25
Standard and Canonical Formsp. 26
Matrices, Vectors, Scalarsp. 27
Basic Conceptsp. 33
A Fundamental Theoremp. 36
Notational Conventions and Illustrationsp. 39
Five Preliminariesp. 43
Bases and Basic Feasible Solutionsp. 43
Detecting Optimalityp. 43
Detecting Unboundednessp. 44
A Rank-One Updatep. 45
Changing Basesp. 45
Simplex Algorithmsp. 49
Notation, Reading Instructions, Updatingp. 50
Big M or How to Get Startedp. 54
Selecting a Pivot Row and Columnp. 56
Data Structures, Tolerances, Product Formp. 58
Equation Format and Cyclingp. 63
Finiteness of a Simplex Algorithmp. 69
Canonical Formp. 71
A Worst-Case Example for a Simplex Algorithmp. 75
Block Pivots and Structurep. 77
A Generalized Product Formp. 79
Upper Boundsp. 82
Primal-Dual Pairsp. 87
Weak Dualityp. 89
Strong Dualityp. 91
Economic Interpretation and Applicationsp. 94
Solvability, Redundancy, Separabilityp. 97
A Dual Simplex Algorithmp. 103
Correctness, Finitenoss, Initializationp. 105
Post-Optimalityp. 109
A Dynamic Simplex Algorithmp. 114
Analytical Geometryp. 121
Points, Linos, Subspacesp. 124
Polyhedra, Ideal Descriptions, Conesp. 131
Faces, Valid Equations, Affine Hullsp. 134
Facets, Minimal Complete Descriptions, Quasi-Uniquenessp. 138
Asymptotic Cones and Extreme Raysp. 141
Adjacency I, Extreme Rays of Polyhedra, Homogenizationp. 144
Point Sets, Affine Transformations, Minimal Generatorsp. 147
Displaced Cones, Adjacency II, Images of Polyhedrap. 150
Carathéodory, Minkowski, Weylp. 155
Minimal Generators, Canonical Generators, Quasi-Uniquenessp. 157
Double Description Algorithmsp. 165
Correctness and Finitenoss of the Algorithmp. 168
Geometry, Euclidean Reduction, Analysisp. 173
The Basis Algorithm and All-Integer Inversionp. 180
An All-Integer Algorithm for Double Descriptionp. 183
Digital Sizes of Rational Polyhedra and Linear Optimizationp. 188
Facet Complexity, Vertex Complexity, Complexity of Inversionp. 190
Polyhedra and Related Polytopes for Linear Optimizationp. 194
Feasibility, Binary Search, Linear Optimizationp. 197
Perturbation, Uniqueness, Separationp. 202
Geometry and Complexity of Simplex Algorithmsp. 207
Pivot Column Choice, Simplex Paths, Big M Revisitedp. 208
Gaussian Elimination, Fill-In, Scalingp. 212
Iterative Step I, Pivot Choice, Cholesky Factorizationp. 216
Cross Multiplication, Iterative Step II, Integer Factorizationp. 219
Division Free Gaussian Elimination and Cramer's Rulep. 221
Circles, Spheres, Ellipsoidsp. 229
Projective Algorithmsp. 239
A Basic Algorithmp. 243
The Solution of the Approximate Problemp. 245
Convergence of the Approximate Iteratesp. 246
Correctness, Finiteness, Initializationp. 250
Analysis, Algebra, Geometryp. 253
Solution to the Problem in the Original Spacep. 254
The Solution in the Transformed Spacep. 260
Geometric Interpretations and Propertiesp. 264
Extending the Exact Solution and Proofsp. 268
Examples of Projective Imagesp. 271
The Cross Ratiop. 274
Reflection on a Circle and Sandwichingp. 278
The Iterative Stepp. 283
A Projective Algorithmp. 288
Centers, Barriers, Newton Stepsp. 292
A Method of Centersp. 296
The Logarithmic Barrier Functionp. 298
A Newtonian Algorithmp. 303
Codap. 308
Ellipsoid Algorithmsp. 309
Matrix Norms, Approximate Inverses, Matrix Inequalitiesp. 316
Ellipsoid "Halving" in Approximate Arithmeticp. 320
Polynomial-Time Algorithms for Linear Programmingp. 328
Linear Programming and Binary Searchp. 336
Deep Cuts, Sliding Objective, Large Steps, Line Searchp. 339
Linear Programming the Ellipsoidal Way: Two Examplesp. 344
Correctness and Finiteness of the DCS Ellipsoid Algorithmp. 348
Optimal Separators, Most Violated Separators, Separationp. 352
¿-Solidification of Flats, Polytopal Norms, Roundingp. 356
Rational Rounding and Continued Fractionsp. 361
Optimization and Separationp. 368
¿-Optimal Sets and ¿-Optimal Solutionsp. 371
Finding Direction Vectors in the Asymptotic Conep. 373
A CCS Ellipsoid Algorithmp. 375
Linear Optimization and Polyhedral Separationp. 378
Combinatorial Optimization: An Introductionp. 387
The Berlin Airlift Model Revisitedp. 389
Complete Formulations and Their Implicationsp. 396
Extremal Characterizations of Ideal Formulationsp. 405
Blocking and Antiblocking Polyhedrap. 414
Polyhedra with the Integrality Propertyp. 417
Short-Term Financial Managementp. 423
Operations Management in a Refineryp. 427
Automatized Production: PCBs and Ulysses' Problemp. 441
Referencesp. 457
Bibliographyp. 479
Indexp. 495
Table of Contents provided by Publisher. All Rights Reserved.

ISBN: 9783540658337
ISBN-10: 3540658335
Series: Algorithms and Combinatorics
Audience: Professional
Format: Hardcover
Language: English
Number Of Pages: 501
Published: July 1999
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.5 x 15.5  x 3.81
Weight (kg): 2.02
Edition Number: 2
Edition Type: Revised