Integer Programming von Laurence A Wolsey

<p><b>A PRACTICAL GUIDE TO OPTIMIZATION PROBLEMS WITH DISCRETE OR INTEGER VARIABLES, REVISED AND UPDATED</b></p><p>The revised second edition of<i>Integer Programming</i> explains in clear and simple terms how to construct custom-made algorithms or use existing commercial software to obtain optimal or near-optimal solutions for a variety of real-world problems. The second edition also includes information on the remarkable progress in the development of mixed integer programming solvers in the 22 years since the first edition of the book appeared. The updated text includes information on the most recent developments in the field such as the much improved preprocessing/presolving and the many new ideas for primal heuristics included in the solvers. The result has been a speed-up of several orders of magnitude. The other major change reflected in the text is the widespread use of decomposition algorithms, in particular column generation (branch-(cut)-and-price) and Benders decomposition. The revised second edition:</p><ul><li>Contains new developments on column generation</li><li>Offers a new chapter on Benders algorithm</li><li>Includes expanded information on preprocessing, heuristics, and branch-and-cut</li><li>Presents several basic and extended formulations, for example for fixed cost</li><li>network flows</li><li>Also touches on and briefly introduces topics such as non-bipartite matching, the complexity of extended formulations or a good linear program for the implementation of lift-and-project</li></ul><p>Written for students of integer/mathematical programming in operations research, mathematics, engineering, or computer science, Integer Programming offers an updated edition of the basic text that reflects the most recent developments in the field.</p>

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.

Preface to the Second Edition xiiPreface to the First Edition xiiiAbbreviations and Notation xviiAbout the Companion Website xix1 Formulations11.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 Bounds252.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 Problems433.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 MaximumstFlow 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 Assignments634.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 Programming795.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 01 Knapsack Problems 855.4.2 Integer Knapsack Problems 865.5 The Cutting Stock Problem 895.6 Notes 915.7 Exercises 926 Complexity and Problem Reductions956.1 Complexity 956.2 Decision Problems, and ClassesNP andP 966.3 Polynomial Reduction and the ClassNPC 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 Bound1137.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 Algorithms1398.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 Gomorys 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 Inequalities1679.1 Introduction 1679.2 Strong Inequalities 1689.3 01 Knapsack Inequalities 1759.3.1 Cover Inequalities 1759.3.2 Strengthening Cover Inequalities 1769.3.3 Separation for Cover Inequalities 1789.4 Mixed 01 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 Duality19510.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 Algorithms21311.1 Introduction 21311.2 The DantzigWolfe 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 Algorithm23512.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,𝜂, y)-Space 24412.5.2 Branching in (x,𝜂)-Space and No-Good Cuts 24612.6 Notes 24712.7 Exercises 24813 Primal Heuristics25113.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 Solutions26914.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

Funktionsweise E-Books.