Integer Programming

PrefaceChapter 1 Integer Optimization and Its Applications 1.1 What Is Integer Optimization? 1.2 "Solving" the Integer Problem by Rounding the Continuous Optimum 1.3 Examples of the Applications of Integer Programming 1.4 Methods of Integer Programming 1.5 Organization of the Book ProblemsChapter 2 Linear Programming 2.1 Introduction 2.2 Definition of Linear Programming 2.3 The Simplex Method 2.4 The Revised Simplex Method 2.5 The Dual Problem 2.6 Bounded Variables ProblemsChapter 3 Zero-One Implicit Enumeration 3.1 Introduction 3.2 Zero-One Equivalence of the Integer Problem 3.3 Concept of Implicit Enumeration 3.4 Enumeration Scheme 3.5 Fathoming Tests 3.6 Nonlinear Zero-One Problem 3.7 Mixed Zero-One Problem 3.8 Concluding Remarks ProblemsChapter 4 Branch-and-Bound Methods 4.1 The Concept of Branch-and-Bound 4.2 Branch-and-Bound Principle 4.3 General (Mixed) Integer Linear Problem 4.4 Solution of Nonlinear Integer Programs by Branch-and-Bound 4.5 Concluding Remarks ProblemsChapter 5 Cutting Methods 5.1 Introduction 5.2 Dual Cutting Methods 5.3 Primal Cutting Methods 5.4 Comments on Computational Experience 5.5 Concluding Remarks ProblemsChapter 6 The Asymptotic Integer Algorithm 6.1 Introduction 6.2 The Idea of the Asymptotic Algorithm 6.3 Development of the Asymptotic Algorithm 6.4 Solution of the Group (Relaxed) Problem 6.5 Solution of Integer Programs by the Group Problem 6.6 Reducing the Number of Congruences 6.7 Faces of the Corner Polyhedron 6.8 Concluding Remarks ProblemsChapter 7 Algorithms for Specialized Integer Models 7.1 Introduction 7.2 Knapsack Problem 7.3 Fixed-Charge and Plant Location Problems 7.4 Traveling Salesman Problem 7.5 Set Covering Problem 7.6 Concluding Remarks ProblemsChapter 8 Computational Considerations in Integer Programming 8.1 Introduction 8.2 Model Formulation in Integer Programming 8.3 A Composite Algorithm 8.4 "General" Approximate Methods for Integer Programming 8.5 Concluding RemarksReferencesIndex