Linear Optimization and Extensions (Algorithms and Combinatorics, 12)

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. This book offers a comprehensive treatment of linear programming as well as of the optimization of linear functions over polyhedra in finite dimensional Euclidean vector spaces. An introduction surveying fifty years of linear optimization is given. The book can serve both as a graduate textbook for linear programming and as a text for advanced topics classes or seminars. Exercises as well as several case studies are included. The book is based on the author's long term experience in teaching and research. For his research work he has received, among other honors, the 1983 Lanchester Prize of the Operations Research Society of America, the 1985 Dantzig Prize of the Mathematical Programming Society and the Society for Industrial Applied Mathematics and a 1989 Alexander-von-Humboldt Senior U.S. Scientist Research Award. Front Matter....Pages I-XXI Introduction....Pages 1-24 The Linear Programming Problem....Pages 25-32 Basic Concepts....Pages 33-42 Five Preliminaries....Pages 43-48 Simplex Algorithms....Pages 49-86 Primal-Dual Pairs....Pages 87-120 Analytical Geometry....Pages 121-238 Projective Algorithms....Pages 239-308 Ellipsoid Algorithms....Pages 309-386 Combinatorial Optimization: An Introduction....Pages 387-422 Back Matter....Pages 423-503

From the reviews: Do you know M.Padberg's Linear Optimization and Extensions? […] Now here is the continuation of it, discussing the solutions of all its exercises and with detailed analysis of the applications mentioned. Tell your students about it. […] For those who strive for good exercises and case studies for LP this is an excellent volume. Acta Scientiarum Mathematicarum

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.