Jon Lee focuses on key mathematical ideas leading to useful models and algorithms, rather than on data structures and implementation details, in this introductory graduate-level text for students of operations research, mathematics, and computer science. The viewpoint is polyhedral, and Lee also uses matroids as a unifying idea. Topics include linear and integer programming, polytopes, matroids and matroid optimization, shortest paths, and network flows. Problems and exercises are included throughout as well as references for further study.
Author(s): Jon Lee
Series: Cambridge Texts in Applied Mathematics
Publisher: Cambridge University Press
Year: 2004
Language: English
Pages: 228
Tags: Математика;Методы оптимизации;
Cover......Page 1
Half-title......Page 3
Title......Page 7
Copyright......Page 8
Contents......Page 11
Preface......Page 15
Introduction......Page 19
0.1 Finite Systems of Linear Inequalities......Page 27
0.2 Linear-Programming Duality......Page 32
0.3 Basic Solutions and the Primal Simplex Method......Page 39
0.4 Sensitivity Analysis......Page 45
0.5 Polytopes......Page 47
0.6 Lagrangian Relaxation......Page 53
0.7 The Dual Simplex Method......Page 58
0.8 Totally Unimodular Matrices, Graphs, and Digraphs......Page 59
0.9 Further Study......Page 65
1.1 Independence Axioms and Examples of Matroids......Page 67
1.2 Circuit Properties......Page 69
1.3 Representations......Page 71
1.4 The Greedy Algorithm......Page 74
1.5 Rank Properties......Page 78
1.6 Duality......Page 81
1.7 The Matroid Polytope......Page 84
1.8 Further Study......Page 91
2 Minimum-Weight Dipaths......Page 93
2.1 No Negative-Weight Cycles......Page 94
2.3 Nonnegative Weights......Page 96
2.4 No Dicycles and Knapsack Programs......Page 99
2.5 Further Study......Page 100
3.1 Applications......Page 102
3.2 An Efficient Cardinality Matroid-Intersection Algorithm and Consequences......Page 107
3.3 An Efficient Maximum-Weight Matroid-Intersection Algorithm......Page 119
3.4 The Matroid-Intersection Polytope......Page 121
3.5 Further Study......Page 124
4.1 Augmenting Paths and Matroids......Page 125
4.2 The Matching Polytope......Page 127
4.3 Duality and a Maximum-Cardinality Matching Algorithm......Page 131
4.4 Kuhn’s Algorithm for the Assignment Problem......Page 139
4.5 Applications of Weighted Matching......Page 144
4.6 Further Study......Page 155
5.1 Source–Sink Flows and Cuts......Page 156
5.2 An Efficient Maximum-Flow Algorithm and Consequences......Page 158
5.3 Undirected Cuts......Page 165
5.4 Further Study......Page 168
6.1 Generic Cutting-Plane Method......Page 169
6.2 Chvátal–Gomory Cutting Planes......Page 170
6.3 Gomory Cutting Planes......Page 174
6.4 Tightening a Constraint......Page 185
6.5 Constraint Generation for Combinatorial-Optimization Problems......Page 189
6.6 Further Study......Page 194
7 Branch-&-Bound......Page 195
7.1 Branch-&-Bound Using Linear-Programming Relaxation......Page 197
7.2 Knapsack Programs and Group Relaxation......Page 202
7.3 Branch-&-Bound for Optimal-Weight Hamiltonian Tour......Page 206
7.4 Maximum-Entropy Sampling and Branch-&-Bound......Page 209
7.5 Further Study......Page 211
8.1 Minimizing Submodular Functions......Page 212
8.2 Minimizing Submodular Functions Over Odd Sets......Page 215
8.3 Maximizing Submodular Functions......Page 218
8.4 Further Study......Page 219
A.2 Algebra......Page 221
A.3 Graphs......Page 222
A.4 Digraphs......Page 223
Further Reading......Page 225
Indexes......Page 227
