Discrete Optimization (eBook)
472 Seiten
Elsevier Science (Verlag)
978-1-4832-9480-3 (ISBN)
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.
Front Cover 1
Discrete Optimization 4
Copyright Page 5
Table of Contents 8
Dedication 6
Preface 10
Chapter 1. Introduction to Discrete Optimization 14
1.1 Discrete Optimization Defined 15
1.2 Discrete Optimization and Integer Programming 17
1.3 Why are Discrete Optimization Problems Difficult to Solve? 18
1.4 Progress in Discrete Optimization 20
1.5 Organization of the Book 20
EXERCISES 21
Chapter 2.
24
2.1 Fundamental Concepts 25
2.2 Decision Problems 36
2.3 NP- Equivalent Problems 41
2.4 The P . NP Conjecture 58
2.5 Dealing with NP-Hard Problems 59
EXERCISES 64
Chapter 3.
70
3.1 Independence Systems and Matroids 71
3.2 Examples of Matroids 73
3.3 Matroid Duality 75
3.4 Optimization and Independence Systems 79
3.5 Matroid Intersection 84
3.6 Matroid Parity 101
3.7 Submodular Functions and Polymatroids 106
EXERCISES 112
Chapter 4.
120
4.1 Polynomial-Time Solution of Linear Programs 120
4.2 Integer Solvability of Linear Programs 144
4.3 Equivalences between Linear and Polynomial Solvability 153
4.4 Integer Programs with a Fixed Number of Variables 159
EXERCISES 162
Chapter 5.
170
5.1 Fundamentals of Partial Enumeration 171
5.2 Elementary Bounds 188
5.3 Conditional Bounds and Penalties 200
5.4 Heuristic Aspects of Branch and Bound 207
5.5 Constructive Dual Techniques 218
5.6 Primal Partitioning—Benders Enumeration 250
EXERCISES 262
Chapter 6.
278
6.1 Fundamentals of Polyhedral Description 278
6.2 Gomory's Cutting Algorithm 292
6.3 Minimal Inequalities 304
6.4 Disjunctive Characterizations 311
6.5 Subadditive Characterizations 335
6.6 Successive Integerized Sum Characterization 346
6.7 Direct Techniques 356
EXERCISES 360
Chapter 7.
370
7.1 The Nature of Nonexact Procedures 371
7.2 Measures of Algorithm Performance 373
7.3 Greedy Procedures 381
7.4 Local Improvement 388
7.5 Truncated Exponential Schemes 396
7.6 Some Negative Results 404
EXERCISES 411
Appendix A: Vectors, Matrices and Convex Sets 420
Appendix B:
430
Appendix C: Linear Programming Fundamentals 442
References 450
Index 474
Erscheint lt. Verlag | 28.6.2014 |
---|---|
Sprache | englisch |
Themenwelt | Mathematik / Informatik ► Mathematik ► Graphentheorie |
Technik | |
ISBN-10 | 1-4832-9480-3 / 1483294803 |
ISBN-13 | 978-1-4832-9480-3 / 9781483294803 |
Haben Sie eine Frage zum Produkt? |
Größe: 26,3 MB
Kopierschutz: Adobe-DRM
Adobe-DRM ist ein Kopierschutz, der das eBook vor Mißbrauch schützen soll. Dabei wird das eBook bereits beim Download auf Ihre persönliche Adobe-ID autorisiert. Lesen können Sie das eBook dann nur auf den Geräten, welche ebenfalls auf Ihre Adobe-ID registriert sind.
Details zum Adobe-DRM
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen eine
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen eine
Geräteliste und zusätzliche Hinweise
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich