Discrete Optimization Algorithms with Pascal Programs

by Syslo, Maciej M.; Deo, Narsingh; Kowalik, Janusz S.

• ISBN13: 9780486453538
• ISBN10: 0486453537
• Format: Paperback
• Copyright: 2006-12-15
• Publisher: Dover Publications

Summary

Upper-level undergraduates and graduate students will benefit from this treatment of discrete optimization algorithms, which covers linear and integer programming. It offers ready-to-use computer programs, together with their derivation and performance characteristics. Subjects include packing and covering, optimization on networks, and coloring and scheduling. 1983 edition.

Table of Contents

PREFACE	xi
1 LINEAR AND INTEGER PROGRAMMING	1
1.1 Linear Programming	2
1.1.1 Construction of the Revised Simplex Method	3
1.1.2 Numerical Stability	18
1.1.3 Large LP Problems	21
1.1.4 Convergence and Time Complexity	21
1.1.5 A Polynomial-Time Algorithm	23
1.1.6 Problems Equivalent to Linear Programming	26
Problems	28
References and Remarks	35
1.2 Dual Linear Programming Method	37
Problems	50
References and Remarks	53
1.3 Transportation Problem	54
1.3.1 Maximum Flow in a Network	56
1.3.2 Maximum Flow Solution Method of the Transportation Problem	60
Problems	71
References and Remarks	76
1.4 Integer Programming	77
1.4.1 Algorithms for Integer Programming	80
1.4.2 Construction of the Gomory All-Integer Dual Method	82
1.4.3 Gomory's All-Integer Dual Algorithm	86
Problems	96
References and Remarks	99
1.5 Zero-One Integer Programming	100
1.5.1 Implicit Enumeration	102
1.5.2 The Balas Zero-One Additive Algorithm	104
Problems	114
References and Remarks	115
2 PACKING AND COVERING	117
2.1 The Knapsack Problem	118
2.1.1 Problem Formulations and Applications	118
2.1.2 Lower and Upper Bounds	123
2.1.3 Reduction Algorithm	126
2.1.4 Approximation Algorithms	135
2.1.5 Exact Methods	142
2.1.6 Computational Results	162
Problems	165
References and Remarks	171
2.2 Covering Problems	176
2.2.1 Formulations and Applications	176
2.2.2 Reduction Algorithms	179
2.2.3 Implicit Enumeration Method for the Set-Partitioning Problem	194
2.2.4 Computational Results	210
Problems	211
References and Remarks	217
3 OPTIMIZATION ON NETWORKS	221
3.1 Computer Representation of a Network	223
3.2 Paths and Trees	226
3.3 Shortest Path Problems	227
3.3.1 Single-Source Paths, Nonnegative Weights	228
3.3.2 Single-Source Paths, Arbitrary Weights	235
3.3.3 Shortest Paths between All Pairs of Nodes	242
3.3.4 Comparative Performances of Shortest-Path Algorithms	246
Problems	247
References and Remarks	249
3.4 Minimum Spanning Tree Problem	253
3.4.1 Kruskal's Algorithm	253
3.4.2 Prim's Algorithm	259
3.4.3 Comparative Performance of MST Algorithm	264
Problems	265
References and Remarks	267
3.5 Maximum Flow Problem	269
Problems	296
References and Remarks	298
3.6 Minimum-Cost Flow Problem	301
Problems	314
References and Remarks	317
3.7 Maximum-Cardinality Matching	320
Problems	337
References and Remarks	340
3.8 Traveling Salesman Problem	343
3.8.1 A Branch-and-Bound Algorithm	346
3.8.2 Approximate Algorithms	361
3.8.3 Local Search Heuristics	368
3.8.4 Modifications	380
Problems	382
References and Remarks	386
4 COLORING AND SCHEDULING	393
4.1 Graph Coloring	394
4.1.1 Definitions and Basic Properties	395
4.1.2 Independent Set Approach	399
4.1.3 Approximate Sequential Algorithms	404
4.1.4 Backtracking Sequential Algorithm	424
4.1.5 Computational Results	433
Problems	438
References and Remarks	442
4.2 Scheduling Problems	445
4.2.1 Network Scheduling	446
4.2.2 Resource Constrained Network Scheduling	454
4.2.3 Flow Shop and Job Shop Scheduling	474
4.2.4 General Schedulina Problem	484
4.2.5 Single-Machine Scheduling	489
4.2.6 Parallel Machine Scheduling	496
4.2.7 Parallel Machine Scheduling with Precedence Constraints	503
Problems	517
References and Remarks	527
INDEX	535