Cover -- Title Page -- Copyright -- Contents -- Preface -- Part I: Foundations -- I.1 The Scope of Integer and Combinatorial Optimization -- 1. Introduction -- 2. Modeling with Binary Variables I: Knapsack, Assignmentand Matching, Covering, Packing and Partitioning -- The 0-1 Knapsack Problem -- The Assignment and Matching Problems -- Set-covering, Set-packing, and Set-partitioning Problems -- 3. Modeling with Binary Variables II: Facility Location, Fixed-charge Network Flow, and Traveling Salesman -- Facility Location Problems -- The Fixed-charge Network Flow Problem -- The Traveling Salesman Problem -- 4. Modeling with Binary Variables III: Nonlinear Functions and Disjunctive Constraints -- Piecewise Linear Functions -- Disjunctive Constraints -- A Scheduling Problem -- 5. Choices in Model Formulation -- 6. Preprocessing -- Tightening Bounds -- Adding Logical Inequalities, Fixing Variables, and Removing Redundant Constraints -- 7. Notes -- Section I.1.1 -- Sections I.1.2-I.1.4 -- Section I.1.5 -- Section I.1.6 -- 8. Exercises -- I.2: Linear Programming -- 1. Introduction -- 2. Duality -- 3. The Primal and Dual Simplex Algorithms -- Bases and Basic Solutions -- Changing the Basis -- Primal Simplex Algorithm -- Dual Simplex Algorithm -- Dual Simplex Algorithm (phase 2) -- The Simplex Algorithm with Simple Upper Bounds -- Addition of Constraints or Variables -- 4. Subgradient Optimization -- The Subgradient Algorithm for (4.1) -- 5. Notes -- Sections I.2.1-i.2.3. -- Section I.2.4 -- I.3: Graphs and Networks -- 1. Introduction -- 2. The Minimum-weight or Shortest-path Problem -- Dijkstra's Minimum-weight Path Algorithm -- Bellman-ford Minimum-weight Path Algorithm -- 3. The Minimum-weight Spanning Tree Problem.

Algorithm for Constructing a Spanning Tree -- 4. The Maximum-flow and Minimum-cut Problems -- Augmenting Path Algorithm -- 5. The Transportation Problem: A Primal-dual Algorithm -- Primal-dual Algorithm for the Transportation Problem -- Minimum-cost Path Augmentation Algorithm -- 6. A Primal Simplex Algorithm for Network Flow Problems -- 7. Notes -- Section I.3.1 -- Section I.3.2 -- Section I.3.3 -- Section I.3.4 -- Section I.3.5 -- Section I.3.6 -- I.4: Polyhedral Theory -- 1. Introduction and Elementary Linear Algebra -- 2. Definitions of Polyhedra and Dimension -- 3. Describing Polyhedra by Facets -- 4. Describing Polyhedra by Extreme Points and Extreme Rays -- 5. Polarity -- 6. Polyhedral Ties Between Linear and Integer Programs -- 7. Notes -- Sections I.4.1-I.4.4 -- Section I.4.5 -- Section I.4.6 -- 8. Exercises -- 1.5: Computational Complexity -- 1. Introduction -- 2. Measuring Algorithm Efficiency and Problem Complexity -- 3. Some Problems Solvable in Polynomial Time -- 4. Remarks on 0-1 and Pure-integer Programming -- 5. Nondeterministic Polynomial-time Algorithms and Np Problems -- Certificates of Feasibility, the Class Np, and Nondeterministic Algorithms -- 6. The Most Difficult Np Problems: the Class Np -- 7. Complexity and Polyhedra -- 8. Notes -- Sections I.5.1 and I.5.2 -- Section I.5.3 -- Section I.5.4 -- Sections I.5.5 and I.5.6 -- Section I.5.7 -- 9. Exercises -- I.6: Polynomial-Time Algorithms for Linear Programming -- 1. Introduction -- 2. The Ellipsoid Algorithm -- The Ellipsoid Algorithm for P< -- 3. The Polynomial Equivalence of Separation and Optimization -- 4. A Projective Algorithm for Linear Programming.

The Projective Algorithm to Find an E-approximate Ray -- The Projective Algorithm for the Linear Program (4.2) -- 5. A Strongly Polynomial Algorithm for Combinatorial Linear Programs -- 6. Notes -- Section I.6.1 -- Section I.6.2 -- Section I.6.3 -- Section I.6.4 -- Section I.6.5 -- I.7: Integer Lattices -- 1. Introduction -- 2. The Euclidean Algorithm -- The Euclidean Algorithm to Find Gcd(a, b) -- 3. Continued Fractions -- 4. Lattices and Hermite Normal Form -- The Hermite Normal Form Algorithm -- 5. A Reduced Basis of a Lattice -- The Gram-schmidt Orthogonalization of a Basis B -- A Reduced Basis Algorithm for a Full-dimensional Lattice L -- 6. Notes -- Section I.7.1 -- Section I.7.2 -- Section I.7.3 -- Section I.7.4 -- Section I.7.5 -- 7. Exercises -- Part II: General Integer Programming -- II. 1: the Theory of Valid Inequalities -- 1. Introduction -- 2. Generating All Valid Inequalities -- 0-1 Problems -- Bounded Integer Variables -- 3. Gomory's Fractional Cuts and Rounding -- 4. Superadditive Functions and Valid Inequalities -- 5. A Polyhedral Description of Superadditive Valid Inequalities for Independence Systems -- 6. Valid Inequalities for Mixed-integer Sets -- Mixed-integer Rounding (mir) Procedure -- 7. Superadditivity for Mixed-integer Sets -- 8. Notes -- Section II.1.1 -- Section II.1.2 -- Section II.1.3 -- Section II.1.4 -- Section II.1.5 -- Section II.1.6 -- Section II.1.7 -- 9. Exercises -- II.2: Strong Valid Inequalities and Facets for Structured Integer Programs -- 1. Introduction -- 2. Valid Inequalities for the 0-1 Knapsack Polytope -- 3. Valid Inequalities for the Symmetric Traveling Salesman Polytope.

4. Valid Inequalities for Variable Upper-bound Flow Models -- 5. Notes -- Section II.2.1 -- Section II.2.2 -- Section II.2.3 -- Section II.2.4 -- 6. Exercises -- II.3: Duality and Relaxation -- 1. Introduction -- 2. Duality and the Value Function -- 3. Superadditive Duality -- 4. The Maximum-weight Path Formulation and Superadditive Duality -- 5. Modular Arithmetic and the Group Problem -- 6. Lagrangian Relaxation and Duality -- 7. Benders' Reformulation -- 8. Notes -- Section II.3.1 -- Section II.3.2 -- Section II.3.3 -- Section II.3.4 -- Section II.3.5 -- Section II.3.6 -- Section II.3.7 -- 9. Exercises -- II.4: General Algorithms -- 1. Introduction -- General Relaxation Algorithm -- Fractional Cutting-plane Algorithm (fcpa) -- General Branch-and-bound Algorithm -- 2. Branch-and-bound Using Linear Programming Relaxations -- Pruning Criteria -- Division -- Node Selection -- Branching Variable Selection -- Generalized Upper-bound Constraints -- Piecewise Linear Functions -- 3. General Cutting-plane Algorithms -- Finite Convergence -- The Lexicographic Dual Simplex Algorithm -- Extension to Mixed-integer Programming -- Primal Cutting-plane Algorithm -- 4. Notes -- Section II.4.1 -- Section II.4.2 -- Section II.4.3 -- 5. Exercises -- II.5: Special-purpose Algorithms -- 1. Introduction -- 2. A Cuiting-plane Algorithm Using Strong Valid Inequalities -- Fractional Cutting-plane Algorithm (fcpa) for Lp(f) -- The Separation Problem for F -- A Strong Cutting-plane/branch-and-bound Algorithm for Ip. -- 3. Primal and Dual Heuristic Algorithms -- A Greedy (heuristic) Algorithm for Maximizing a Set Function -- A K-interchange Heuristic for Max{c(x): X Є S e Bn}. -- Dual Descent [a Greedy Algorithm for (3.2)] -- Analysis of Heuristics -- Simulated Annealing.

Simulated Annealing Algorithm for (3.5) -- Probabilistic Analysis -- 4. Decomposition Algorithms -- Solving the Lagrangian Dual by Subgradient Optimization -- Solving the Lagrangian Dual by Constraint Generation -- Benders' Decomposition -- Constraint Generation Algorithm for Mip' -- 5. Dynamic Programming -- A Dynamic Programming Algorithm for the 0-1 Knapsack Problem -- A Dynamic Programming Algorithm for the Uncapacitated Lot-size Problem (uls) -- 6. Notes -- Section II.5.1 -- Section II.5.2 -- Section II.5.3 -- Section II.5.4 -- Section II.5.5 -- 7. Exercises -- II.6: Applications of Special-purpose Algorithms -- 1. Knapsack and Group Problems -- The Integer Knapsack Problem -- Dynamic Programming -- A Superadditive Dual Algorithm -- Heuristic Algorithms -- The Scaling/rounding (sr) Heuristic -- The Group Problem -- A Shortest-path Enumeration Algorithm for Ip -- The Increasing Group Algorithm -- The 0-1 Knapsack Problem -- An Algorithm for the Linear Programming Relaxation -- Primal Heuristic Algorithm -- Branch-and-bound -- 2. 0-1 Integer Programming Problems -- A Simplex-based Heuristic for Bip -- Algorithm -- An Fcp/branch-and-bound Algorithm -- Set Covering and Packing -- Greedy Heuristic for Set Covering -- 3. The Symmetric Traveling Salesman Problem -- Relaxations -- Primal Heuristics -- Relaxation/branch-and-bound Algorithms -- Shrinking an Edge E = (i,j) of G(x*) with Xe*= 1 -- Solution of a Large Problem -- 4. Fixed-charge Network Flow Problems -- A Branch-and-bound Algorithm for Fn -- An Fcpa for Fn -- Separation Algorithm for Generalized Flow Cover Inequalities.

Solving a Fixed-charge Uncapacitated Transportation Problem by an Fcpa and Branch-and-bound.