E-Book, Englisch, 472 Seiten, Web PDF
Parker / Rardin Discrete Optimization
1. Auflage 2014
ISBN: 978-1-4832-9480-3
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark
E-Book, Englisch, 472 Seiten, Web PDF
Reihe: Computer Science and Scientific Computing
ISBN: 978-1-4832-9480-3
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark
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.
Autoren/Hrsg.
Weitere Infos & Material
1;Front Cover;1
2;Discrete Optimization;4
3;Copyright Page;5
4;Table of Contents ;8
5;Dedication;6
6;Preface;10
7;Chapter 1. Introduction to Discrete Optimization;14
7.1;1.1 Discrete Optimization Defined;15
7.2;1.2 Discrete Optimization and Integer Programming;17
7.3;1.3 Why are Discrete Optimization Problems Difficult to Solve?;18
7.4;1.4 Progress in Discrete Optimization;20
7.5;1.5 Organization of the Book;20
7.6;EXERCISES;21
8;Chapter 2.
Computational Complexity;24
8.1;2.1 Fundamental Concepts;25
8.2;2.2 Decision Problems;36
8.3;2.3 NP- Equivalent Problems;41
8.4;2.4 The P . NP Conjecture;58
8.5;2.5 Dealing with NP-Hard Problems;59
8.6;EXERCISES;64
9;Chapter 3.
Polynomial Algorithms—Matroids;70
9.1;3.1 Independence Systems and Matroids;71
9.2;3.2 Examples of Matroids;73
9.3;3.3 Matroid Duality;75
9.4;3.4 Optimization and Independence Systems;79
9.5;3.5 Matroid Intersection;84
9.6;3.6 Matroid Parity;101
9.7;3.7 Submodular Functions and Polymatroids;106
9.8;EXERCISES;112
10;Chapter 4.
Polynomial Algorithms—Linear Programming;120
10.1;4.1 Polynomial-Time Solution of Linear Programs;120
10.2;4.2 Integer Solvability of Linear Programs;144
10.3;4.3 Equivalences between Linear and Polynomial Solvability;153
10.4;4.4 Integer Programs with a Fixed Number of Variables;159
10.5;EXERCISES;162
11;Chapter 5.
Nonpolynomial Algorithms—Partial Enumeration;170
11.1;5.1 Fundamentals of Partial Enumeration;171
11.2;5.2 Elementary Bounds;188
11.3;5.3 Conditional Bounds and Penalties;200
11.4;5.4 Heuristic Aspects of Branch and Bound;207
11.5;5.5 Constructive Dual Techniques;218
11.6;5.6 Primal Partitioning—Benders Enumeration;250
11.7;EXERCISES;262
12;Chapter 6.
Nonpolynomial Algorithms—Polyhedral Description;278
12.1;6.1 Fundamentals of Polyhedral Description;278
12.2;6.2 Gomory's Cutting Algorithm;292
12.3;6.3 Minimal Inequalities;304
12.4;6.4 Disjunctive Characterizations;311
12.5;6.5 Subadditive Characterizations;335
12.6;6.6 Successive Integerized Sum Characterization;346
12.7;6.7 Direct Techniques;356
12.8;EXERCISES;360
13;Chapter 7.
Nonexact Algorithms;370
13.1;7.1 The Nature of Nonexact Procedures;371
13.2;7.2 Measures of Algorithm Performance;373
13.3;7.3 Greedy Procedures;381
13.4;7.4 Local Improvement;388
13.5;7.5 Truncated Exponential Schemes;396
13.6;7.6 Some Negative Results;404
13.7;EXERCISES;411
14;Appendix A: Vectors, Matrices and Convex Sets;420
15;Appendix B:
Graph Theory Fundamentals;430
16;Appendix C: Linear Programming Fundamentals;442
17;References;450
18;Index;474
