Discrete Optimization

by R. Gary Parker and Ronald L. Rardin
Academic Press, 1988
ISBN: 0-12-545075-3
472 pages

Overview

This text provides an introduction to the theory and general algorithms of discrete (integer and combinatorial) optimization at a level suitable for graduate courses and researchers. Following a brief introduction, Chapter 2 surveys the main concepts of the computational complexity theory that has revolutionized discrete optimization research in recent years. Main results are then developed in a complexity theory-based organization. Chapters 3 and 4 present the matroid and linear programming ideas leading to polynomial-time algorithms. Chapters 5 and 6 provide corresponding treatment of the major classes of nonpolynomial exact algorithms: branch-and-bound and polyhedral description. A final chapter surveys results for nonexact (heuristic) procedures. Appendices are included reviewing the concepts from matrix algebra, graph theory, and linear programming needed in various parts of the book.

The aim throughout is to make the enormously diverse array of elegant results that have emerged in both integer and combinatorial optimization research accessible to instructors, researchers, and students. While algorithms are presented in computational format, and demonstrated throughout with suitable examples, every effort has been made to maintain a consistent and rigorous treatment of the underlying theory. The numerous exercises included at the end of each chapter span the range from routine application of the algorithms to new research results.

Table of Contents

1 - INTRODUCTION TO DISCRETE OPTIMIZATION 1
1.1 Discrete Optimization Defined 2
1.2 Discrete Optimization and Integer Programming 4
1.3 Why are Discrete Optimization Problems
Difficult to Solve? 5
1.4 Progress in Discrete Optimization 7
1.5 Organization of the Book 7
Exercises 8

2 - COMPUTATIONAL COMPLEXITY 11
2.1 Fundamental Concepts 12
2.1.1 Problems 12
2.1.2 Computational Orders 12
2.1.3 Computation Time and Turing Machines 13
2.1.4 Problem Size and Encoding 18
2.1.5 Problem Reductions 19
2.1.6 Worst Case Behavior 22
2.2 Decision Problems 23
2.2.1 The Class P 24
2.2.2 Complements of Problems in P 24
2.2.3 The Class NP 25
2.2.4 Complements of Problems in NP -- the Class CoNP 26
2.3 NP-Equivalent Problems 28 2.3.1 NP-Hardness and Cook's Theorem 28
2.3.2 NP-Completeness 31
2.3.3 NP-Equivalent Optimization Problems 41
2.4 The P Not Equal NP Conjecture 45
2.5 Dealing with NP-Hard Problems 46
2.5.1 Special Cases 47
2.5.2 Pseudo-Polynomial Algorithms and Strong Sense NP-Hardness 47
2.5.3 Solving Over Relaxations 48
2.5.4 Polynomial-Time Nonexact Algorithms 49
Exercises 51

3 - POLYNOMIAL ALGORITHMS -- MATROIDS 57
3.1 Independence Systems and Matroids 58
3.2 Examples of Matroids 60
3.2.1 Uniform Matroids 60
3.2.2 Partition Matroids 60
3.2.3 Transversal Matroids 61
3.2.4 Graphic Matroids 61
3.2.5 Representable, Regular and Binary Matroids 61
3.3 Matroid Duality 62
3.4 Optimization and Independence Systems 66
3.4.1 The Greedy Algorithm 66
3.4.2 Polyhedral Interpretation 68
3.5 Matroid Intersection 71
3.5.1 Matroid Partition 72
3.5.2 Cardinality Intersection 77
3.5.3 Weighted Matroid Intersection 78
3.5.4 Three Matroid Intersection 88
3.6 Matroid Parity 88
3.6.1 Status of Matroid Parity 89
3.6.2 Weak and Strong Duality for Matroid Parity 90
3.6.3 A Matroid Parity Algorithm -- Basic Concepts 92
3.7 Submodular Functions and Polymatroids 93
3.7.1 Submodular Functions 93
3.7.2 Polymatroids 94
3.7.3 Polymatroid Intersection 98
Exercises 99

4 - POLYNOMIAL ALGORITHMS -- LINEAR PROGRAMMING 107
4.1 Polynomial-Time Solution of Linear Programs 107
4.1.1 Simplex Anomalies 108
4.1.2 Khachian's Ellipsoid Algorithm 110
4.1.3 Karmarkar's Projective Scaling Algorithm 117
4.2 Integer Solvability of Linear Programs 131
4.2.1 Unimodularity 131
4.2.2 Testing Total Unimodularity 134
4.2.3 Total Dual Integrality 137
4.3 Equivalences between Linear and
Polynomial Solvability 140
4.3.1 Separation and Optimization 140
4.3.2 Combinatorial Significance of Separation Implies Optimization 143
4.3.3 Combinatorial Significance of Optimization Implies Separation 145
4.4 Integer Programs with a Fixed Number of Variables 146
4.4.1 Lattices and Basis Reduction 147
4.4.2 Polynomial Solution 148
Exercises 149

5 - NONPOLYNOMIAL ALGORITHMS -- PARTIAL ENUMERATION 157
5.1 Fundamentals of Partial Enumeration 158
5.1.1 Branch and Bound 159
5.1.2 Candidate Problems from Partial Solutions 165
5.1.3 Bounds and Feasible Solutions from Relaxations 166
5.1.4 Branch and Bound and Dynamic Programming 168
5.1.5 Exponential Order of Partial Enumeration 173
5.2 Elementary Bounds 175
5.2.1 Implicit Enumeration 175
5.2.2 The Linear Programming Relaxation 182
5.2.3 Linear Programming versus Implicit Enumeration 185
5.2.4 Alternative Formulations 187
5.3 Conditional Bounds and Penalties 187
5.3.1 Conditional Bounds from Implicit Enumeration 189
5.3.2 Post-Linear Programming Penalties 190
5.4 Heuristic Aspects of Branch and Bound 194
5.4.1 Candidate Problem Selection 194
5.4.2 Feasible Solutions 199
5.4.3 Branching Variable Selection and Pseudo-Costs 200
5.5 Constructive Dual Techniques 205
5.5.1 Lagrangean Duals 206
5.5.2 Lagrangean Dual Search 212
5.5.3 Surrogate Duals 230
5.5.4 Practical Branch and Bound Considerations 237
5.6 Primal Partitioning -- Benders Enumeration 237
5.6.1 The Primal Partitioning Algorithm 238
5.6.2 Benders Imbedded in Other Enumeration 245
Exercises 249

6 - NONPOLYNOMIAL ALGORITHMS -- POLYHEDRAL DESCRIPTION 265
6.1 Fundamentals of Polyhedral Description 265
6.1.1 The Relaxation Strategy 266
6.1.2 Cutting vs. Other Strategies 268
6.1.3 The Convex Hull of Solutions 271
6.1.4 Classes of Valid Inequalities 277
6.1.5 Complexity of Cutting Algorithms 279
6.2 Gomory's Cutting Algorithm 279
6.2.1 Pure Integer Case 280
6.2.2 Mixed Integer Case 287
6.2.3 Computational Difficulties 290
6.3 Minimal Inequalities 291
6.3.1 Minimal Inequalities Versus Supporting and Facetial 293
6.3.2 Complexity of Minimal and Facetial Inequalities 295
6.4 Disjunctive Characterizations 298
6.4.1 The Disjunctive Model 298
6.4.2 The Disjunctive Principle 300
6.4.3 Cutting Planes for Local Disjunctions 305
6.4.4 Facial Cases 309
6.4.5 Alternative Convexity/Intersection Conceptualization 320
6.5 Subadditive Characterizations 322
6.5.1 The Subadditive Principle for Pure Integer Programs 322
6.5.2 Extensions of the Subadditive Principle to Mixed Integer Programs 328
6.6 Successive Integerized Sum Characterization 333
6.6.1 The Chvatal Model 335
6.6.2 Sufficiency of Successive Chv\o'a\''tal Construction 337
6.7 Direct Techniques 343
Exercises 347

7 - NONEXACT ALGORITHMS 357
7.1 The Nature of Nonexact Procedures 358
7.1.1 Definition and Applicability 358
7.1.2 Difficulties with Nonexact Procedures 358
7.2 Measures of Algorithm Performance 360
7.2.1 Empirical Analysis 362
7.2.2 Performance Guarantees 363
7.2.3 Approximation Schemes 365
7.2.4 Expected Performance Analysis 367
7.3 Greedy Procedures 368
7.3.1 General Concepts 369
7.3.2 Performance Guarantees for Independence Systems 369
7.4 Local Improvement 375
7.4.1 General Strategy 375
7.4.2 Implementation 375
7.4.3 Performance of Local Improvement 378
7.5 Truncated Exponential Schemes 383
7.5.1 Branch and Bound Environment 384
7.5.2 Bound Allowance Methods 385
7.6 Some Negative Results 391
7.6.1 Formal Limitations on Performance Bound Existence 392
7.6.2 Formal Limitations on Finite-Valued, Realizable Performance Bounds 394
Exercises 398

Appendix A: Vectors, Matrices and Convex Sets 407
A.1 Vectors 407
A.2 Matrices 409
A.3 Convex Sets 412

Appendix B: Graph Theory Fundamentals 417
B.1 Fundamental Definitions 417
B.2 Planarity 422
B.3 Trees, Forests, Arborescences, and Branchings 423
B.4 Traversals 424
B.5 Covering, Matching, and Independence 425
B.6 Network Flows 426

Appendix C: Linear Programming Fundamentals 429
C.1 Duality and Optimality 429
C.2 Representation and Bases 431
C.3 Simplex Algorithms 432

REFERENCES 437

INDEX 461