Discrete Optimization (eBook)

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