Parker / Rardin | Discrete Optimization | E-Book | sack.de
E-Book

E-Book, Englisch, 472 Seiten, Web PDF

Reihe: Computer Science and Scientific Computing

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.

Parker / Rardin Discrete Optimization jetzt bestellen!

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



Ihre Fragen, Wünsche oder Anmerkungen
Vorname*
Nachname*
Ihre E-Mail-Adresse*
Kundennr.
Ihre Nachricht*
Lediglich mit * gekennzeichnete Felder sind Pflichtfelder.
Wenn Sie die im Kontaktformular eingegebenen Daten durch Klick auf den nachfolgenden Button übersenden, erklären Sie sich damit einverstanden, dass wir Ihr Angaben für die Beantwortung Ihrer Anfrage verwenden. Selbstverständlich werden Ihre Daten vertraulich behandelt und nicht an Dritte weitergegeben. Sie können der Verwendung Ihrer Daten jederzeit widersprechen. Das Datenhandling bei Sack Fachmedien erklären wir Ihnen in unserer Datenschutzerklärung.