整数规划，经典超全教材
  Integer and Combinatorial Optimization







目录表：

• PART I. 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 III: 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 of Polyhedra 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.H9fJ Problems 127
6. The Most Difficult j{9fJ Problems: The Class j{9fJcg 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
11.1 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 Super additive Valid Inequalities for
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 U pper-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 General 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
11.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
11.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