Integer and Combinatorial Optimization - TOC

Integer and Combinatorial Optimization GEORGE NEMHAUSER School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, Georgia LAURENCE WOLSEY Center for Operations Research and Econometrics Universite Catholique de Louvain Louvain-la-Neuve, Belgium A Wiley-Interscience Publication JOHN WILEY & SONS, INC. New York • Chichester • Weinheim • Brisbane • Singapore • Toronto Contents PARTI. FOUNDATIONS 1 1.1 The Scope of Integer and Combinatorial Optimization 3 1. Introduction 3 2. Modeling with Binary Variables I: Knapsack, Assignment and Matching, Covering, Packing and Partitioning 5 3. Modeling with Binary Variables II: Facility Location, Fixed-Charge Network Flow, and Traveling Salesman 7 4. Modeling with Binary Variables HI: Nonlinear Functions and Disjunctive Constraints 10 5. Choices in Model Formulation 14 6. Preprocessing 17 7. Notes 20 8. Exercises 22 1.2 Linear Programming 27 1. Introduction 27 2. Duality 28 3. The Primal and Dual Simplex Algorithms 30 4. Subgradient Optimization 41 5. Notes 49 1.3 Graphs and Networks 50 1. Introduction * 50 2. The Minimum-Weight or Shortest-Path Problem 55 3. The Minimum-Weight Spanning Tree Problem 60 4. The Maximum-Flow and Minimum-Cut Problems 62 5. The Transportation Problem: A Primal-Dual Algorithm 68 6. A Primal Simplex Algorithm for Network Flow Problems 76 7. Notes 82 1.4 Polyhedral Theory 83 1. Introduction and Elementary Linear Algebra 83 2. Definitions ofPolyhedra and Dimension 85 3. Describing Polyhedra by Facets 88 4. Describing Polyhedra by Extreme Points and Extreme Rays 92 5. Polarity 98 xi xii Contents 6. Polyhedral Ties Between Linear and Integer Programs 104 7. Notes 109 8. Exercises 109 1.5 Computational Complexity 114 1. Introduction 114 2. Measuring Algorithm Efficiency and Problem Complexity 117 3. Some Problems Solvable in Polynomial Time 121 4. Remarks on 0-1 and Pure-Integer Programming 125 5. Nondeterministic Polynomial-Time Algorithms and Jf& Problems 127 6. The Most Difficult Jf& Problems: The Class Jf9*€ 131 7. Complexity and Polyhedra 139 8. Notes 142 9. Exercises 143 1.6 Polynomial-Time Algorithms for Linear Programming 146 1. Introduction 146 2. The Ellipsoid Algorithm 147 3. The Polynomial Equivalence of Separation and Optimization 161 4. A Projective Algorithm 164 5. A Strongly Polynomial Algorithm for Combinatorial Linear Programs 172 6. Notes 180 1.7 Integer Lattices 182 1. Introduction 182 2. The Euclidean Algorithm 184 3. Continued Fractions 187 4. Lattices and Hermite Normal Form 189 5. Reduced Bases 195 6. Notes 201 7. Exercises 202 PART II. GENERAL INTEGER PROGRAMMING 203 II.l The Theory of Valid Inequalities 205 1. Introduction 205 2. Generating All Valid Inequalities 217 3. Gomory's Fractional Cuts and Rounding 227 4. Superadditive Functions and Valid Inequalities 229 5. A Polyhedral Description of Superadditive Valid Inequalitiesrfor Independence Systems 237 6. Valid Inequalities for Mixed-Integer Sets 242 7. Superadditivity for Mixed-Integer Sets 246 8. Notes 254 9. Exercises 256 Contents xiii 11.2 Strong Valid Inequalities and Facets for Structured Integer Programs 259 1. Introduction 259 2. Valid Inequalities for the 0-1 Knapsack Polytope 265 3. Valid Inequalities for the Symmetric Traveling Salesman Polytope 270 4. Valid Inequalities for Variable Upper-Bound Flow Models 281 5. Notes 290 6. Exercises 291 11.3 Duality and Relaxation 296 1. Introduction 296 2. Duality and the Value Function 300 3. Superadditive Duality 304 4. The Maximum-Weight Path Formulation and Superadditive Duality 308 5. Modular Arithmetic and the Group Problem 312 6. Lagrangian Relaxation and Duality 323 7. Benders' Reformulation 337 8. Notes 341 9. Exercises 343 11.4 Genera] Algorithms 349 1. Introduction 349 2. Branch-and-Bound Using Linear Programming Relaxations 355 3. General Cutting-Plane Algorithms 367 4. Notes 379 5. Exercises 381 II.5 Special-Purpose Algorithms 383 1. Introduction 383 2. A Cutting-Plane Algorithm Using Strong Valid Inequalities 386 3. Primal and Dual Heuristic Algorithms 393 4. Decomposition Algorithms 409 5. Dynamic Programming •> 417 6. Notes 424 7. * Exercises 427 II.6 Applications of Special-Purpose Algorithms 433 1. Knapsack and Group Problems 433 2. 0-1 Integer Programming Problems " 456 3. The Symmetric Traveling Salesman Problem 469 4. Fixed-Charge Network Flow Problems 495 5. Applications of Basis Reduction 513 6. Notes 520 7. Exercises 526 xiv Contents PART III. COMBINATORIAL OPTIMIZATION 533 111.1 Integral Polyhedra 535 1. Introduction 535 2. Totally Unimodular Matrices 540 3. Network Matrices 546 4. Balanced and Totally Balanced Matrices 562 5. Node Packing and Perfect Graphs 573 6. Blocking and Integral Polyhedra 586 7. Notes 598 8. Exercises 602 111.2 Matching 608 1. Introduction 608 2. Maximum-Cardinality Matching 611 3. Maximum-Weight Matching 627 4. Additional Results on Matching and Related Problems 636 5. Notes 654 6. Exercises 655 111.3 Matroid and Submodular Function Optimization 659 1. Introduction 659 2. Elementary Properties 662 3. Maximum-Weight Independent Sets 666 4. Matroid Intersection 671 5. Weighted Matroid Intersection 678 6. Polymatroids, Separation, and Submodular Function Minimization 688 7. Algorithms To Minimize a Submodular Function 694 8. Covering with Independent Sets and Matroid Partition 702 9. Submodular Function Maximization 708 10. Notes 712 11. Exercises 714 References 721 Author Index 749 Subject Index * 755