Two-Level Table of Contents
CHAPTER 1: Problem Solving with Mathematical Models
1.1: Application Stories... 1
1.2: Optimization and the Operations Research Process... 3
1.3: System Boundaries, Sensitivity Analysis, Tractability and Validity... 8
1.4: Descriptive Models and Simulation... 11
1.5: Numerical Search and Exact versus Heuristic Solutions... 14
1.6: Deterministic versus Stochastic Models... 16
1.7: Perspectives... 19
Exercises... 20
CHAPTER 2: Deterministic Optimization Models in Operations Research
2.1: Decision Variables, Constraints, and Objective Functions... 23
2.2: Graphic Solution and Optimization Outcomes... 27
2.3: Large-Scale Optimization Models and Indexing... 39
2.4: Linear and Nonlinear Programs... 46
2.5: Discrete or Integer Programs... 52
2.6: Multiobjective Optimization Models... 59
2.7: Classification Summary... 63
Exercises... 64
CHAPTER 3: Improving Search
3.1: Improving Search, Local and Global Optima... 77
3.2: Search with Improving and Feasible Directions... 88
3.3: Algebraic Conditions for Improving and Feasible Directions... 99
3.4: Unimodal and Convex Model Forms Tractable for Improving Search... 109
3.5: Searching for Starting Feasible Solutions... 118
Exercises... 127
CHAPTER 4: Linear Programming Models
4.1: Allocation Models... 131
4.2: Blending Models... 135
4.3: Operations Planning Models... 139
4.4: Shift Scheduling and Staff Planning Models... 148
4.5: Time-Phased Models... 153
4.6: Models with Linearizable Nonlinear Objectives... 157
Exercises... 164
CHAPTER 5: Simplex Search for Linear Programming
5.1: LP Optimal Solutions and Standard Form... 175
5.2: Extreme-Point Search and Basic Solutions... 186
5.3: The Simplex Algorithm... 197
5.4: Dictionary and Tableau Representations of Simplex... 207
5.5: Two Phase Simplex... 211
5.6: Degeneracy and Zero-Length Simplex Steps... 220
5.7: Convergence and Cycling with Simplex... 224
5.8: Doing It Efficiently: Revised Simplex... 225
5.9: Simplex with Simple Upper and Lower Bounds... 238
Exercises... 245
CHAPTER 6: Interior Point Methods for Linear Programming
6.1: Searching through the Interior... 251
6.2: Scaling with the Current Solution... 262
6.3: Affine Scaling Search... 269
6.4: Log Barrier Methods for Interior Point Search... 275
6.5: Dual and Primal-Dual Extensions... 287
Exercises... 293
CHAPTER 7: Duality and Sensitivity in Linear Programming
7.1: Generic Activities versus Resources Perspective... 299
7.2: Qualitative Sensitivity to Changes in Model Coefficients... 304
7.3: Quantifying Sensitivity to Changes in LP Model Coefficients: A Dual Formulation... 315
7.4: Formulating Linear Programming Duals... 324
7.5: Primal-to-Dual Relationships... 329
7.6: Computer Outputs and What If Changes of Single Parameters... 338
7.7: Bigger Model Changes, Reoptimization and Parametric Programming... 354
Exercises... 363
CHAPTER 8: Multiobjective Optimization and Goal Programming
8.1: Multiobjective Optimization Models... 373
8.2: Efficient Points and the Efficient Frontier... 378
8.3: Preemptive Optimization and Weighted Sums of Objectives... 384
8.4: Goal Programming... 389
Exercises... 400
CHAPTER 9: Shortest Paths and Discrete Dynamic Programming
9.1: Shortest Path Models... 409
9.2: Dynamic Programming Approach to Shortest Paths... 417
9.3: Shortest Paths from One Node to All Others: Bellman-Ford... 426
9.4: Shortest Paths from All Nodes to All Others: Floyd-Warshall... 433
9.5: Shortest Path from One Node to All Others with Costs Nonnegative: Dijkstra... 440
9.6: Shortest Paths from One Node to All Others in Acyclic Digraphs... 446
9.7: CPM Project Scheduling and Longest Paths... 450
9.8: Discrete Dynamic Programming Models... 458
Exercises... 468
CHAPTER 10: Network Flows
10.1: Graphs, Networks and Flows... 475
10.2: Cycle Directions for Network Flow Search... 483
10.3: Rudimentary Cycle Direction Search Algorithms for Network Flows... 494
10.4: Integrality of Optimal Network Flows... 500
10.5: Transportation and Assignment Models... 502
10.6: Other Single-Commodity Network Flow Models... 511
10.7: Network Simplex Algorithm for Optimal Flows... 519
10.8: Cycle Canceling Algorithms for Optimal Flows... 529
10.9: Multicommodity and Gain/Loss Flows... 536
Exercises... 543
CHAPTER 11: Discrete Optimization Models
11.1: Lumpy Linear Programs and Fixed Charges... 555
11.2: Knapsack and Capital Budgeting Models... 560
11.3: Set Packing, Covering and Partitioning Models... 566
11.4: Assignment and Matching Models... 574
11.5: Traveling Salesman and Routing Models... 584
11.6: Facility Location and Network Design Models... 595
11.7: Processor Scheduling and Sequencing Models... 602
Exercises... 613
CHAPTER 12: Discrete Optimization Methods
12.1: Solving by Total Enumeration... 627
12.2: Relaxations of Discrete Optimization Models and Their Uses... 630
12.3: Stronger LP Relaxations, Valid Inequalities, and Lagrangian Relaxations... 641
12.4: Branch and Bound Search... 651
12.5: Rounding, Parent Bounds, Enumeration Sequences and Stopping Early in Branch and Bound... 664
12.6: Improving Search Heuristics and Discrete Optimization INLPs... 680
12.7: Tabu, Simulated Annealing, and Genetic Algorithm Extensions of Improving Search... 687
12.8: Constructive Heuristics... 698
Exercises... 705
CHAPTER 13: Unconstrained Nonlinear Programming
13.1: Unconstrained Nonlinear Programming Models... 715
13.2: One-Dimensional Search... 726
13.3: Derivatives, Taylor Series, and Conditions for Local Optima... 737
13.4: Convex/Concave Functions and Global Optimality... 749
13.5: Gradient Search... 757
13.6: Newton's Method... 761
13.7: Quasi-Newton Methods and BFGS Search... 766
13.8: Optimization Without Derivatives and Nelder-Mead... 774
Exercises... 781
CHAPTER 14: Constrained Nonlinear Programming
14.1: Constrained Nonlinear Programming Models... 787
14.2: Convex, Separable, Quadratic and Posynomial Geometric Programming Special NLP Forms... 795
14.3: Lagrange Multiplier Methods... 810
14.4: Karush-Kuhn-Tucker Optimality Conditions... 817
14.5: Penalty and Barrier Methods... 827
14.6: Reduced Gradient Algorithms... 837
14.7: Quadratic Programming Methods... 849
14.8: Separable Programming Methods... 858
14.9: Posynomial Geometric Programming Methods... 866
Exercises... 875
Selected Answers
Answers to approximately half the numerical and smaller formulation
exercises at ends of chapters... 887
Index
Topic index to all material of the book... 905
Back to Optimization in Operations Research mainpage