Network Flows

CONTENTS

PREFACE, xl

1 INTRODUCTION, 1

1.1 Introduction, 1

1.2 Network Flow Problems, 4

1.3 Applications, 9

1.4 Summary, 18

Reference Notes, 19

Exercises, 20

2 PATHS, TREES, AND CYCLES, 23

2.1 Introduction, 23

2.2 Notation and Definitions, 24

2.3 Network Representations, 31

2.4 Network Transformations, 38

2.5 Summary, 46

Reference Notes, 47

Exercises, 47

3 ALGOlUTHM DESIGN AND ANALYSIS, ~3

3.1 Introduction, 53

3.2 Complexity Analysis, 56

3.3 Developing Polynomial-Time Algorithms, 66

3.4 Search Algorithms, 73

3.5 Flow Decomposition Algorithms, 79

3.6 Summary, 84

Reference Notes, 85

Exercises, 86

4 SHORTEST PA THS: LABEL-SETTING ALGOBITHMS, 93

4.1 Introduction, 93

4.2 Applications, 97

4.3 Tree of Shortest Paths, 106

4.4 Shortest Path Problems in Acyclic Networks, 107

4.5 Dijkstra's Algorithm, 108

4.6 Dial's Implementation, 113

4.7 Heap Implementations, 115

4.8 Radix Heap Implementation, 116

v

4.9 Summary, 121

Reference Notes, 122

Exercises, 124

15 SHORTEST PATHS: LABEL-COBBECTING ALGOBITHMS, 133

5.1 Introduction, 133

5.2 Optimality Conditions, 135

5.3 Generic Label-Correcting Algorithms, 136

5.4 Special Implementations of the Modified Label-Correcting Algorithm, 141

5.5 Detecting Negative Cycles, 143

5.6 All-Pairs Shortest Path Problem, 144

5.7 Minimum Cost-to-Time Ratio Cycle Problem, 150

5.8 Summary, 154

Reference Notes, 156

Exercises, 157

8 MAXIMUM FLOWS: BABIC IDEAS, 188

6.1 Introduction, 166

6.2 Applications, 169

6.3 Flows and Cuts, 177

6.4 Generic Augmenting Path Algorithm, 180

6.5 Labeling Algorithm and the Max-Flow Min-Cut Theorem, 184

6.6 Combinatorial Implications of the Max-Flow Min-Cut Theorem, 188

6.7 Flows with Lower Bounds, 191

6.8 Summary, 196

Reference Notes, 197

Exercises, 198

7 MAXIMUM FLOWS: POLYNOMIAL ALGOBITHMB, 207

7.1 Introduction, 207

7.2 Distance Labels, 209

7.3 Capacity Scaling Algorithm, 210

7.4 Shortest Augmenting Path Algorithm, 213

7.5 Distance Labels and Layered Networks, 221

7.6 Generic Preflow-Push Algorithm, 223

7.7 FIFO Preflow-Push Algorithm, 231

7.8 Highest-Label Preflow-Push Algorithm, 233

7.9 Excess Scaling Algorithm, 237

7.10 Summary, 241

Reference Notes, 241

Exercises, 243

8 MAXIMUM FLOWS: ADDITIONAL TOPICS, 2lJO

8.1 Introduction, 250

8.2 Flows in Unit Capacity Networks, 252

8.3 Flows in Bipartite Networks, 255

8.4 Flows in Planar Undirected Networks, 260

8.5 Dynamic Tree Implementations, 265

vi Contents

8.6 Network Connectivity, 273

8.7 All-Pairs Minimum Value Cut Problem, 277

8.8 Summary, 285

Reference Notes, 287

Exercises, 288

9 MINIMUM COST FLOWS: BABIC ALGOBITHMS, 294

9.1 Introducti"on, 294

9.2 Applications, 298

9.3 Optimality Conditions, 306

9.4 Minimum Cost Flow Duality, 310

9.5 Relating Optimal Flows to Optimal Node Potentials, 315

9.6 Cycle-Canceling Algorithm and the Integrality Property, 317

9.7 Successive Shortest Path Algorithm, 320

9.8 Primal-Dual Algorithm, 324

9.9 Out-of-Kilter Algorithm, 326

9.10 Relaxation Algorithm, 332

9.11 Sensitivity Analysis, 337

9.12 Summary, 339

Reference Notes, 341

Exercises, 344

10 MINIMUM COST FLOWS: POLYNOMIAL ALGORITHMS, 8lJ7

10.1 Introduction, 357

10.2 Capacity Scaling Algorithm, 360

10.3 Cost Scaling Algorithm, 362

10.4 Double Scaling Algorithm, 373

10.5 Minimum Mean Cycle-Canceling Algorithm, 376

10.6 Repeated Capacity Scaling Algorithm, 382

10.7 Enhanced Capacity Scaling Algorithm, 387

10.8 Summary, 395

Reference Notes, 396

Exercises, 397

11 MINIMUM COST FLOWS: NETWORK SIMPLEX ALGO.RlTHMS, 402

11.1 Introduction, 402

11.2 Cycle Free and Spanning Tree Solutions, 405

11.3 Maintaining a Spanning Tree Structure, 409

11.4 Computing Node Potentials and Flows, 411

11. 5 Network Simplex Algorithm, 415

11.6 Strongly Feasible Spanning Trees, 421

11.7 Network Simplex Algorithm for the Shortest Path Problem, 425

11.8 Network Simplex Algorithm for the Maximum Flow Problem, 430

11.9 Related Network Simplex Algorithms, 433

11.10 Sensitivity Analysis, 439

11.11 Relationship to Simplex Method, 441

11.12 U nimodularity Property, 447

11.13 Summary, 450

Reference Notes, 451

Exercises, 453

Contents vii

12 ABSIGNMENTSANDMATCHINGS, 481

12.1 Introduction, 461

12.2 Applications, 463

12.3 Bipartite Cardinality Matching Problem, 469

12.4 Bipartite Weighted Matching Problem, 470

12.S Stable Marriage Problem, 473

12.6 Nonbipartite Cardinality Matching Problem, 475

12.7 Matchings and Paths, 494

12.8 Summary, 498

Reference Notes, 499

Exercises, 501

13 MINIMUM SPANNING TREES, 1510

13.1 Introduction, 510

13.2 Applications, 512

13.3 Optimality Conditions, 516

13.4 Kruskal's Algorithm, 520

13.S Prim's Algorithm, 523

13.6 Sollin's Algorithm, 526

13.7 Minimum Spanning Trees and Matroids, 528

13.8 Minimum Spanning Trees and Linear Programming, 530

13.9 Summary, 533

Reference Notes, 535

Exercises, 536

14 CONVEX COST FLOWS, 1543

14.1 Introduction, 543

14.2 Applications, 546

14.3 Transformation to a Minimum Cost Flow Problem, 551

14.4 Pseudopolynomial-Time Algorithms, 554

14.S Polynomial-Time Algorithm, 556

14.6 Summary, 560

Reference Notes, 561

Exercises, 562

15 GENEBALIZED FLOWS, 1588

IS.1 Introduction, 566

IS.2 Applications, 568

15.3 Augmented Forest Structures, 572

IS.4 Determining Potentials and Flows for an Augmented Forest Structure, 577

IS.S Good Augmented Forests and Linear Programming Bases, 582

IS.6 Generalized Network Simplex Algorithm, 583

IS.7 Summary, 591

Reference Notes, 591

Exercises, 593

viii Contents

16 LAGRANGIAN RELAXATION AND NETWORK OPTIMIZATION, 698

16.1 Introduction, 598

16.2 Problem Relaxations and Branch and Bound, 602

16.3 Lagrangian Relaxation Technique, 605

16.4 Lagrangian Relaxation and Linear Programming, 615

16.5 Applications of Lagrangian Relaxation, 620

16.6 Summary, 635

Reference Notes, 637

Exercises, 638

17 MULTICOMMODITY FLOWS, 849

17.1 Introduction, 649

17.2 Applications, 653

17.3 Optimality Conditions, 657

17.4 Lagrangian Relaxation, 660

17.5 Column Generation Approach, 665

17.6 Dantzig-Wolfe Decomposition, 671

17.7 Resource-Directive Decomposition, 674

17.8 Basis Partitioning, 678

17.9 Summary, 682

Reference Notes, 684

Exercises, 686

18 COMPUTATIONAL TESTING OF ALGOlUTHMS, 896

18.1 Introduction, 695

18.2 Representative Operation Counts, 698

18.3 Application to Network Simplex Algorithm, 702

18.4 Summary, 713

Reference Notes, 713

Exercises, 715

19 ADDITIONAL APPLICATIONS, 717

19.1 Introduction, 717

19.2 Maximum Weight Closure of a Graph, 719

19.3 Data Scaling, 725

19.4 Science Applications, 728

19.5 Project Management, 732

19.6 Dynamic Flows, 737

19.7 Arc Routing Problems, 740

19.8 Facility Layout and Location, 744

19.9 Production and Inventory Planning, 748

19.10 Summary, 755

Reference Notes, 759

Exercises, 760

Contents Ix

APPENDIX A DATA STBUCTUBES, 78~

A.I Introduction, 765

A.2 Elementary Data Structures, 766

A.3 d-Heaps, 773

A.4 Fibonacci Heaps, 779

Reference Notes, 787

APPENDIX B Nf/I-COMPLETENESS, 788

B.I Introduction, 788

B.2 Problem Reductions and Transformations, 790

B.3 Problem Classes r;p, ,Nr;p, ,Nr;p-Complete, and ,Nr;p-Hard, 792

B.4 Proving ,Nr;p-Completeness Results, 796

B.5 Concluding Remarks, 800

Reference Notes, 801

APPENDIX C LINEAR PROGRAMMING, 802

C.I Introduction, 802

C.2 Graphical Solution Procedure, 804

C.3 Basic Feasible Solutions, 805

C.4 Simplex Method, 810

C.S Bounded Variable Simplex Method, 814

C.6 Linear Programming Duality, 816

Reference Notes, 820

BEFEBENCES, 821

INDEX, 840

......(更多)