This book treats the fundamental issues and algorithmic strategies emerging as the core of the discipline of discrete optimization in a comprehensive and rigorous fashion. Following an introductory chapter on computational complexity, the basic algorithmic results for the two major models of polynomial algorithms are introduced--models using matroids and linear programming. Further chapters treat the major non-polynomial algorithms: branch-and-bound and cutting planes. The text concludes with a chapter on heuristic algorithms.
Several appendixes are included which review the fundamental ideas of linear programming, graph theory, and combinatorics--prerequisites for readers of the text. Numerous exercises are included at the end of each chapter
Author(s): R. Gary Parker and Ronald L. Rardin (Auth.)
Series: Computer Science and Scientific Computing
Publisher: Elsevier Inc, Academic Press
Year: 1988
Language: English
Pages: 472
Tags: Математика;Методы оптимизации;
Content:
Inside Front Cover, Page ii
Front Matter, Page iii
Copyright, Page iv
Dedication, Page v
Preface, Pages ix-xi
1 - Introduction to Discrete Optimization, Pages 1-10
2 - Computational Complexity, Pages 11-56
3 - Polynomial Algorithms—Matroids, Pages 57-106
4 - Polynomial Algorithms—Linear Programming, Pages 107-156
5 - Nonpolynomial Algorithms—Partial Enumeration, Pages 157-263
6 - Nonpolynomial Algorithms—Polyhedral Description, Pages 265-355
7 - Nonexact Algorithms, Pages 357-406
Appendix A - Vectors, Matrices and Convex Sets, Pages 407-416
Appendix B - Graph Theory Fundamentals, Pages 417-428
Appendix C - Linear Programming Fundamentals, Pages 429-435
References, Pages 437-459
Index, Pages 461-472
