Integer Programming

ISBN-13: 9781119606536 / Angielski / Twarda / 2020 / 336 str.

Laurence A. Wolsey

Spis treści

Preface to the Second Edition xiiPreface to the First Edition xiiiAbbreviations and Notation xviiAbout the Companion Website xix1 Formulations 11.1 Introduction 11.2 What Is an Integer Program? 31.3 Formulating IPs and BIPs 51.4 The Combinatorial Explosion 81.5 Mixed Integer Formulations 91.6 Alternative Formulations 121.7 Good and Ideal Formulations 151.8 Notes 181.9 Exercises 192 Optimality, Relaxation, and Bounds 252.1 Optimality and Relaxation 252.2 Linear Programming Relaxations 272.3 Combinatorial Relaxations 282.4 Lagrangian Relaxation 292.5 Duality 302.6 Linear Programming and Polyhedra 322.7 Primal Bounds: Greedy and Local Search 342.8 Notes 382.9 Exercises 383 Well-Solved Problems 433.1 Properties of Easy Problems 433.2 IPs with Totally Unimodular Matrices 443.3 Minimum Cost Network Flows 463.4 Special Minimum Cost Flows 483.4.1 Shortest Path 483.4.2 Maximum s . t Flow 493.5 Optimal Trees 503.6 Submodularity and Matroids 543.7 Two Harder Network Flow Problems 573.8 Notes 593.9 Exercises 604 Matchings and Assignments 634.1 Augmenting Paths and Optimality 634.2 Bipartite Maximum Cardinality Matching 654.3 The Assignment Problem 674.4 Matchings in Nonbipartite Graphs 734.5 Notes 744.6 Exercises 755 Dynamic Programming 795.1 Some Motivation: Shortest Paths 795.2 Uncapacitated Lot-Sizing 805.3 An Optimal Subtree of a Tree 835.4 Knapsack Problems 845.4.1 0-1 Knapsack Problems 855.4.2 Integer Knapsack Problems 865.5 The Cutting Stock Problem 895.6 Notes 915.7 Exercises 926 Complexity and Problem Reductions 956.1 Complexity 956.2 Decision Problems, and Classes NP and P 966.3 Polynomial Reduction and the Class NPC 986.4 Consequences of P =NP orP <>NP 1036.5 Optimization and Separation 1046.6 The Complexity of Extended Formulations 1056.7 Worst-Case Analysis of Heuristics 1066.8 Notes 1096.9 Exercises 1107 Branch and Bound 1137.1 Divide and Conquer 1137.2 Implicit Enumeration 1147.3 Branch and Bound: an Example 1167.4 LP-Based Branch and Bound 1207.5 Using a Branch-and-Bound/Cut System 1237.6 Preprocessing or Presolve 1297.7 Notes 1347.8 Exercises 1358 Cutting Plane Algorithms 1398.1 Introduction 1398.2 Some Simple Valid Inequalities 1408.3 Valid Inequalities 1438.4 A Priori Addition of Constraints 1478.5 Automatic Reformulation or Cutting Plane Algorithms 1498.6 Gomory's Fractional Cutting Plane Algorithm 1508.7 Mixed Integer Cuts 1538.7.1 The Basic Mixed Integer Inequality 1538.7.2 The Mixed Integer Rounding (MIR) Inequality 1558.7.3 The Gomory Mixed Integer Cut 1558.7.4 Split Cuts 1568.8 Disjunctive Inequalities and Lift-and-Project 1588.9 Notes 1618.10 Exercises 1629 Strong Valid Inequalities 1679.1 Introduction 1679.2 Strong Inequalities 1689.3 0-1 Knapsack Inequalities 1759.3.1 Cover Inequalities 1759.3.2 Strengthening Cover Inequalities 1769.3.3 Separation for Cover Inequalities 1789.4 Mixed 0-1 Inequalities 1799.4.1 Flow Cover Inequalities 1799.4.2 Separation for Flow Cover Inequalities 1819.5 The Optimal Subtour Problem 1839.5.1 Separation for Generalized Subtour Constraints 1839.6 Branch-and-Cut 1869.7 Notes 1899.8 Exercises 19010 Lagrangian Duality 19510.1 Lagrangian Relaxation 19510.2 The Strength of the Lagrangian Dual 20010.3 Solving the Lagrangian Dual 20210.4 Lagrangian Heuristics 20510.5 Choosing a Lagrangian Dual 20710.6 Notes 20910.7 Exercises 21011 Column (and Row) Generation Algorithms 21311.1 Introduction 21311.2 The Dantzig-Wolfe Reformulation of an IP 21511.3 Solving the LP Master Problem: Column Generation 21611.4 Solving the Master Problem: Branch-and-Price 21911.5 Problem Variants 22211.5.1 Handling Multiple Subproblems 22211.5.2 Partitioning/Packing Problems with Additional Variables 22311.5.3 Partitioning/Packing Problems with Identical Subsets 22411.6 Computational Issues 22511.7 Branch-Cut-and-Price: An Example 22611.7.1 A Capacitated Vehicle Routing Problem 22611.7.2 Solving the Subproblems 22911.7.3 The Load Formulation 23011.8 Notes 23111.9 Exercises 23212 Benders' Algorithm 23512.1 Introduction 23512.2 Benders' Reformulation 23612.3 Benders' with Multiple Subproblems 24012.4 Solving the Linear Programming Subproblems 24212.5 Integer Subproblems: Basic Algorithms 24412.5.1 Branching in the (x, eta, y)-Space 24412.5.2 Branching in (x, eta)-Space and "No-Good" Cuts 24612.6 Notes 24712.7 Exercises 24813 Primal Heuristics 25113.1 Introduction 25113.2 Greedy and Local Search Revisited 25213.3 Improved Local Search Heuristics 25513.3.1 Tabu Search 25513.3.2 Simulated Annealing 25613.3.3 Genetic Algorithms 25713.4 Heuristics Inside MIP Solvers 25913.4.1 Construction Heuristics 25913.4.2 Improvement Heuristics 26113.5 User-Defined MIP heuristics 26213.6 Notes 26513.7 Exercises 26614 From Theory to Solutions 26914.1 Introduction 26914.2 Software for Solving Integer Programs 26914.3 How Do We Find an Improved Formulation? 27214.4 Multi-item Single Machine Lot-Sizing 27714.5 A Multiplexer Assignment Problem 28214.6 Integer Programming and Machine Learning 28514.7 Notes 28714.8 Exercises 287References 291Index 311

O autorze

LAURENCE A. WOLSEY is a mathematician working in the field of integer programming. He is a former president and research director of the Center for Operations Research and Econometrics (CORE) at UCLouvain in Belgium where he is Emeritus Professor of applied mathematics in the Engineering school.