Table of Contents

Preface     xi
Linear and Integer Programming     1
Linear Programming     2
Construction of the Revised Simplex Method     3
Numerical Stability     18
Large LP Problems     21
Convergence and Time Complexity     21
A Polynomial-Time Algorithm     23
Problems Equivalent to Linear Programming     26
Problems     28
References and Remarks     35
Dual Linear Programming Method     37
Problems     50
References and Remarks     53
Transportation Problem     54
Maximum Flow in a Network     56
Maximum Flow Solution Method of the Transportation Problem     60
Problems     71
References and Remarks     76
Integer Programming     77
Algorithms for Integer Programming     80
Construction of the Gomory All-Integer Dual Method     82
Gomory's All-Integer Dual Algorithm     86
Problems     96
References and Remarks     99
Zero-One Integer Programming     100
Implicit Enumeration     102
The Balas Zero-One Additive Algorithm     104
Problems     114
References and Remarks     115
Packing and Covering     117
The Knapsack Problem     118
Problem Formulations and Applications     118
Lower and Upper Bounds     123
Reduction Algorithm     126
Approximation Algorithms     135
Exact Methods     142
Computational Results     162
Problems     165
References and Remarks     171
Covering Problems     176
Formulations and Applications     176
Reduction Algorithms     179
Implicit Enumeration Method for the Set-Partitioning Problem     194
Computational Results     210
Problems     211
References and Remarks     217
Optimization on Networks     221
Computer Representation of a Network     223
Paths and Trees     226
Shortest Path Problems     227
Single-Source Paths, Nonnegative Weights     228
Single-Source Paths, Arbitrary Weights     235
Shortest Paths between All Pairs of Nodes     242
Comparative Performances of Shortest-Path Algorithms     246
Problems      247
References and Remarks     249
Minimum Spanning Tree Problem     253
Kruskal's Algorithm     253
Prim's Algorithm     259
Comparative Performance of MST Algorithm     264
Problems     265
References and Remarks     267
Maximum Flow Problem     269
Problems     296
References and Remarks     298
Minimum-Cost Flow Problem     301
Problems     314
References and Remarks     317
Maximum-Cardinality Matching     320
Problems     337
References and Remarks     340
Traveling Salesman Problem     343
A Branch-and-Bound Algorithm     346
Approximate Algorithms     361
Local Search Heuristics     368
Modifications     380
Problems     382
References and Remarks     386
Coloring and Scheduling     393
Graph Coloring     394
Definitions and Basic Properties     395
Independent Set Approach     399
Approximate Sequential Algorithms     404
Backtracking Sequential Algorithm     424
Computational Results      433
Problems     438
References and Remarks     442
Scheduling Problems     445
Network Scheduling     446
Resource Constrained Network Scheduling     454
Flow Shop and Job Shop Scheduling     474
General Scheduling Problem     484
Single-Machine Scheduling     489
Parallel Machine Scheduling     496
Parallel Machine Scheduling with Precedence Constraints     503
Problems     517
References and Remarks     527
Index     535