Buch, Englisch, 336 Seiten, Format (B × H): 152 mm x 237 mm, Gewicht: 638 g
ISBN: 978-1-119-60653-6
Verlag: John Wiley & Sons Inc
A PRACTICAL GUIDE TO OPTIMIZATION PROBLEMS WITH DISCRETE OR INTEGER VARIABLES, REVISED AND UPDATED
The revised second edition of Integer Programming 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:
- Contains new developments on column generation
- Offers a new chapter on Benders’ algorithm
- Includes expanded information on preprocessing, heuristics, and branch-and-cut
- Presents several basic and extended formulations, for example for fixed cost
- network flows
- 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
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.
Autoren/Hrsg.
Fachgebiete
- Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen
- Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik
- Wirtschaftswissenschaften Betriebswirtschaft Betriebswirtschaft: Theorie & Allgemeines
- Wirtschaftswissenschaften Betriebswirtschaft Unternehmensforschung
Weitere Infos & Material
Preface to the Second Edition xii
Preface to the First Edition xiii
Abbreviations and Notation xvii
About the Companion Website xix
1 Formulations 1
1.1 Introduction 1
1.2 What Is an Integer Program? 3
1.3 Formulating IPs and BIPs 5
1.4 The Combinatorial Explosion 8
1.5 Mixed Integer Formulations 9
1.6 Alternative Formulations 12
1.7 Good and Ideal Formulations 15
1.8 Notes 18
1.9 Exercises 19
2 Optimality, Relaxation, and Bounds 25
2.1 Optimality and Relaxation 25
2.2 Linear Programming Relaxations 27
2.3 Combinatorial Relaxations 28
2.4 Lagrangian Relaxation 29
2.5 Duality 30
2.6 Linear Programming and Polyhedra 32
2.7 Primal Bounds: Greedy and Local Search 34
2.8 Notes 38
2.9 Exercises 38
3 Well-Solved Problems 43
3.1 Properties of Easy Problems 43
3.2 IPs with Totally Unimodular Matrices 44
3.3 Minimum Cost Network Flows 46
3.4 Special Minimum Cost Flows 48
3.4.1 Shortest Path 48
3.4.2 Maximum s - t Flow 49
3.5 Optimal Trees 50
3.6 Submodularity and Matroids 54
3.7 Two Harder Network Flow Problems 57
3.8 Notes 59
3.9 Exercises 60
4 Matchings and Assignments 63
4.1 Augmenting Paths and Optimality 63
4.2 Bipartite Maximum Cardinality Matching 65
4.3 The Assignment Problem 67
4.4 Matchings in Nonbipartite Graphs 73
4.5 Notes 74
4.6 Exercises 75
5 Dynamic Programming 79
5.1 Some Motivation: Shortest Paths 79
5.2 Uncapacitated Lot-Sizing 80
5.3 An Optimal Subtree of a Tree 83
5.4 Knapsack Problems 84
5.4.1 0–1 Knapsack Problems 85
5.4.2 Integer Knapsack Problems 86
5.5 The Cutting Stock Problem 89
5.6 Notes 91
5.7 Exercises 92
6 Complexity and Problem Reduction
