Deterministic Operations Research Models and Methods in Linear Optimization

by Rader, David J.

• ISBN13: 9780470484517
• ISBN10: 0470484519
• Edition: 1st
• Format: Hardcover
• Copyright: 2010-09-07
• Publisher: Wiley

Summary

Thoroughly classroom-tested over the past eight years, this book focuses on the study of linear optimization (both continuous and discrete), and it also emphasizes the modeling of real problems as linear optimization problems and designs algorithms to solve them.Topics in linear programming, network optimization, and integer programming are discussed, and three aspects of deterministic operations research are emphasized: modeling real-world problems as linear optimization problems; designing algorithms (both heuristic and exact methods) to solve these problems; and using mathematical theory to improve the understanding of the problem, to improve existing algorithms, and to design new algorithms. These three aspects are important for both researchers and practitioners of operations research. Such topics are not always in the forefront of operations research textbooks, and while it is true that many books highlight optimization modeling and algorithms to solve these problems, very few, if any, explicitly discuss the algorithm design process used to solve problems.This book successfully fills this gap in the literature and incorporates these components into the study of linear and integer programming, currently the two most-used optimization models in business and industry. Each chapter of the book is designed to be the continuation of the "story" of how to both model and solve optimization problems by using the specific problems (linear and integer programs) as guides. This enables the reader (and instructors) to see how solution methods can be derived instead of just seeing the final product (the algorithms themselves). Numerous examples and problems as well as relevant historical summaries can be found throughout the text. Each chapter contains at least 20 problems per chapter, with some chapters having many more problems.

Author Biography

David J. Rader JR., PHD, is Associate Professor of Mathematics at Rose-Hulman Institute of Technology, where he is also the editor of the Rose-Hulman Institute of Technology Undergraduate Mathematics Journal. Dr. Rader currently focuses his research in the areas of nonlinear 0-1 optimization, computational integer programming, and exam timetabling.

Table of Contents

Preface	p. xi
Introduction to Operations Research	p. 1
What is Deterministic Operations Research?	p. 1
Introduction to Optimization Modeling	p. 5
Common Classes of Mathematical Programs	p. 13
About this Book	p. 18
Exercises	p. 19
Linear Programming Modeling	p. 21
Resource Allocation Models	p. 21
Work Scheduling Models	p. 25
Models and Data	p. 28
Blending Models	p. 30
Production Process Models	p. 36
Multiperiod Models: Work Scheduling and Inventory	p. 42
Linearization of Special Nonlinear Models	p. 46
Various Forms of Linear Programs	p. 51
Network Models	p. 56
Exercises	p. 68
Integer and Combinatorial Models	p. 85
Fixed-Charge Models	p. 85
Set Covering Models	p. 92
Models Using Logical Constraints	p. 94
Combinatorial Models	p. 99
Sports Scheduling and an Introduction to IP Solution Techniques	p. 109
Exercises	p. 112
Real-World Operations Research Applications: An Introduction	p. 126
Vehicle Routing Problems	p. 126
Facility Location and Network Design Models	p. 130
Applications in the Airline Industry	p. 139
Exercises	p. 152
Introduction to Algorithm Design	p. 159
Exact and Heuristic Algorithms	p. 159
What to Ask When Designing Algorithms?	p. 161
Constructive versus Local Search Algorithms	p. 162
How Good is our Heuristic Solution?	p. 168
Examples of Constructive Methods	p. 169
Example of a Local Search Method	p. 181
Other Heuristic Methods	p. 182
Designing Exact Methods: Optimality Conditions	p. 183
Exercises	p. 189
Improving Search Algorithms and Convexity	p. 197
Improving Search and Optimal Solutions	p. 198
Finding Better Solutions	p. 201
Convexity: When Does Improving Search Imply Global Optimality?	p. 214
Farkas' Lemma: When Can No Improving Feasible Direction be Found?	p. 227
Exercises	p. 232
Geometry and Algebra of Linear Programs	p. 238
Geometry and Algebra of "Corner Points"	p. 239
Fundamental Theorem of Linear Programming	p. 248
Linear Programs in Canonical Form	p. 250
Exercises	p. 262
Solving Linear Programs: Simplex Method	p. 271
Simplex Method	p. 271
Making the Simplex Method More Efficient	p. 285
Convergence, Degeneracy, and the Simplex Method	p. 289
Finding an Initial Solution: Two-Phase Method	p. 294
Bounded Simplex Method ?.	p. 300
Computational Issues	p. 305
Exercises	p. 308
Linear Programming Duality	p. 317
Motivation: Generating Bounds	p. 317
Dual Linear Program	p. 321
Duality Theorems	p. 327
Another Interpretation of the Simplex Method	p. 333
Farkas' Lemma Revisited	p. 334
Economic Interpretation of the Dual	p. 336
Another Duality Approach: Lagrangian Duality	p. 338
Exercises	p. 344
Sensitivity Analysis of Linear Programs	p. 351
Graphical Sensitivity Analysis	p. 351
Sensitivity Analysis Calculations	p. 359
Use of Sensitivity Analysis	p. 368
Parametric Programming	p. 375
Exercises	p. 380
Algorithmic Applications of Duality	p. 389
Dual Simplex Method	p. 389
Transportation Problem	p. 401
Column Generation	p. 414
Dantzig-Wolfe Decomposition	p. 420
Primal-Dual Interior Point Method	p. 432
Exercises	p. 441
Network Optimization Algorithms	p. 449
Introduction to Network Optimization	p. 449
Shortest Path Problems	p. 449
Maximum Flow Problems	p. 458
Minimum Cost Network Flow Problems	p. 470
Exercises	p. 484
Introduction to Integer Programming	p. 489
Basic Definitions and Formulations	p. 490
Relaxations and Bounds	p. 496
Preprocessing and Probing	p. 500
When are Integer Programs "Easy?"	p. 506
Exercises	p. 511
Solving Integer Programs: Exact Methods	p. 514
Complete Enumeration	p. 514
Branch-and-Bound Methods	p. 516
Valid Inequalities and Cutting Planes	p. 524
Gomory's Cutting Plane Algorithm	p. 531
Valid Inequalities for 0-1 Knapsack Constraints	p. 536
Branch-and-Cut Algorithms	p. 540
Computational Issues	p. 547
Exercises	p. 551
Solving Integer Programs: Modern Heuristic Techniques	p. 556
Review of Local Search Methods: Pros and Cons	p. 556
Simulated Annealing	p. 558
Tabu Search	p. 562
Genetic Algorithms	p. 565
GRASP Algorithms	p. 570
Exercises	p. 574
Background Review	p. 579
Basic Notation	p. 579
Graph Theory	p. 581
Linear Algebra	p. 583
Reference	p. 597
Index	p. 603
Table of Contents provided by Ingram. All Rights Reserved.