Discrete Optimization Algorithms with Pascal

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.

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

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Discrete Optimization Algorithms with Pascal Programs

Summary

Table of Contents

Supplemental Materials