상세정보

Large-scale optimization is becoming increasingly important for students and professionals in electrical and industrial engineering, computer science, management science and operations research, and applied mathematics.Linear Network Optimization presents a thorough treatment of classical approaches to network problems such as shortest path, max-flow, assignment, transportation, and minimum cost flow problems. It is the first text to clearly explain important recent algorithms such as auction and relaxation, proposed by the author and others for the solution of these problems. Its coverage of both theory and implementations make it particularly useful as a text for a graduate-level course on network optimization as well as a practical guide to state-of-the-art codes in the field.Bertsekas focuses on the algorithms that have proved successful in practice and provides FORTRAN codes that implement them. The presentation is clear, mathematically rigorous, and economical. Many illustrations, examples, and exercises are included in the text.Contents: Introduction. Simplex Methods. Dual Ascent Methods. Auction Algorithms. Performance and Comparisons. Appendixes.

정보제공 :

Contents
Preface = ⅸ
1 Introduction = 1
 1.1. Problem Formulation = 1
  1.1.1. Graphs and Flows = 2
  1.1.2. The Minimum Cost Flow Problem = 2
  1.1.3. Transformations and Equivalences = 10
 1.2. Three Basic Algorithmic Ideas = 14
  1.2.1. Primal Cost Improvement = 20
  1.2.2. Application to the Max-Flow Problem-The Max-Flow / Min-Cut Theorem = 24
  1.2.3. Duality and Dual Cost Improvement = 33
  1.2.4. Auction = 42
  1.2.5. Good, Bad, and Polynomial Algorithms = 51
 1.3. The Shortest Path Problem = 60
  1.3.1. A General Single Origin / Many Destinations Shortest Path Method = 62
  1.3.2. Label Setting (Dijkstra) Methods = 68
  1.3.3. Label Correcting Methods = 75
  1.3.4. Single Origin / Single Destination Methods = 77
  1.3.5. Multiple Origin / Multiple Destination Methods = 81
 1.4. Notes and Sources = 88
2 Simplex Methods = 91
 2.1. Main Ideas in Simplex Methods = 92
  2.1.1. Using Prices to Obtain the In-Arc = 97
  2.1.2. Obtaining the Out-Arc = 101
  2.1.3. Dealing with Degeneracy = 104
 2.2. The Basic Simplex Algorithm = 109
  2.2.1. Justification of the Simplex Method = 110
  2.2.2. Choosing the Initial Strongly Feasible Tree-The Big-M Method = 111
 2.3. Extension to the Problem with Upper and Lower Bounds = 122
 2.4. Implementation Issues = 125
 2.5. Notes and Sources = 129
3 Dual Ascent Methods = 133
 3.1. Dual Ascent = 133
 3.2. Primal-Dual (sequential Shortest Path) Methods = 138
 3.3. The Relaxation Method = 153
 3.4. Implementation Issues = 163
 3.5. Notes and Sources = 165
4 Auction Algorithms = 167
 4.1. The Auction Algorithm for the Assignment Problem = 167
  4.1.1. The Main Auction Algorithm = 168
  4.1.2. The Approximate Coordinate Descent Interpretation = 172
  4.1.3. Computational Aspects - ε-Scaling = 172
 4.2. Reverse Auction and Inequality Constrained Assignment Problems = 177
  4.2.1. Auction Algorithms for Asymmetric Assignment Problems = 181
  4.2.2. Auction Algorithms for Multiassignmrnt Problems = 188
 4.3. An Auction Algorithms for Shortest Paths = 194
  4.3.1. Algorithm Description and Analysis = 197
  4.3.2. Efficient Implementation-Forward / Reverse Algorithm = 207
  4.3.3. Relation to Naive Auction and Dual Coordinate Ascent = 211
 4.4. A Generic Auction Algorithm for the Minimum Cost Flow Problem = 222
 4.5. The -ε-Relaxation Method = 235
 4.6. Implementation Issues = 241
 4.7. Notes and Sources = 242
5 Performance and Comparisons = 245
 5.1. Shortest Path Problems = 246
 5.2. Max-Flow Problems = 247
 5.3. Assignment Problems = 249
 5.4. Minimum Cost Flow Problems = 250
 5.5. Sensitivity Analysis = 250
Appendixes = 253
 A.1. Problem Generator and Conversion Codes = 254
 A.2. Shortest Path Codes = 262
 A.3. Relaxation Code = 279
 A.4. Auction Codes for Assignment Problems = 280
 A.5. Combined Naive Auction and Sequential Shortest Path Code = 305
 A.6. Max-Flow Codes = 314
 A.7. ε-Relaxation Codes = 331
References = 343
Index = 357