Three-Level Table of Contents
CHAPTER 1: Problem Solving with Mathematical Models
1.1: Application Stories... 1
- Example 1.1: Mortimer Middleman... 2
1.2: Optimization and the Operations Research Process... 3
- Decisions, Constraints and Objectives... 4
- Optimization and Mathematical Programming... 4
- Constant-Rate Demand Assumption... 5
- Back of Envelope Analysis... 5
- Constant-Rate Demand Model... 7
- Feasible and Optimal Solutions... 7
1.3: System Boundaries, Sensitivity Analysis, Tractability and Validity... 8
- EOQ under Constant-Rate Demand... 9
- System Boundaries and Sensitivity Analysis... 10
- Closed Form Solutions... 11
- Tractability versus Validity... 11
1.4: Descriptive Models and Simulation... 11
- Simulation over MM's History... 12
- Simulation Model Validity... 12
- Descriptive versus Prescriptive Models... 12
1.5: Numerical Search and Exact versus Heuristic Solutions... 14
- Numerical Search... 14
- A Different Start... 15
- Exact versus Heuristic Optimization... 15
1.6: Deterministic versus Stochastic Models... 16
- Random Variables and Realizations... 16
- Stochastic Simulation... 17
- Tradeoffs between Deterministic and Stochastic Models... 18
1.7: Perspectives... 19
- Other Issues... 19
- The Rest of This Book... 20
Exercises... 20
CHAPTER 2: Deterministic Optimization Models in Operations Research
2.1: Decision Variables, Constraints, and Objective Functions... 23
- Example 2.1: Two Crude Petroleum... 24
- Decision Variables... 24
- Variable-Type Constraints... 24
- Main Constraints... 25
- Objective Functions... 25
- Standard Model... 26
2.2: Graphic Solution and Optimization Outcomes... 27
- Graphic Solution... 27
- Feasible Sets... 27
- Graphing Constraints and Feasible Sets... 27
- Graphing Objective Functions... 30
- Optimal Solutions... 33
- Optimal Values... 34
- Unique versus Alternative Optimal Solutions... 34
- Infeasible Models... 35
- Unbounded Models... 37
2.3: Large-Scale Optimization Models and Indexing... 39
- Example 2.2: Pi Hybrids... 39
- Indexing... 40
- Indexed Decision Variables... 40
- Indexed Symbolic Parameters... 41
- Objective Function... 42
- Indexed Families of Constraints... 43
- Pi Hybrids Example Model... 45
- How Models Become Large... 45
2.4: Linear and Nonlinear Programs... 46
- General Mathematical Programming Format... 46
- Right-Hand Sides... 47
- Linear Functions... 48
- Linear and Nonlinear Programs Defined... 49
- Two Crude and Pi Hybrids Models Are LPs... 50
- Example 2.3: E-mart... 50
- Indexing, Parameters and Decision Variables for E-mart... 50
- Nonlinear Response... 51
- E-mart Example Model... 51
2.5: Discrete or Integer Programs... 52
- Example 2.4: Bethlehem Ingot Mold... 52
- Indexes and Parameters of the Bethlehem Example... 52
- Discrete and Continuous Decision Variables... 53
- Constraints in Discrete Variables... 53
- Bethlehem Ingot Mold Example Model... 55
- Integer and Mixed-Integer Programs... 55
- Integer Linear versus Integer Nonlinear Programs... 57
- Example 2.5: Purdue Final Exam Scheduling... 58
- Indexing, Parameters and Decision Variables for Purdue Finals Example... 58
- Nonlinear Objective Function... 59
- Purdue Final Exam Scheduling Example Model... 59
2.6: Multiobjective Optimization Models... 59
- Example 2.6: DuPage Land Use Planning... 60
- Multiple Objectives... 60
- Constraints of the DuPage Land Use Example... 61
- DuPage Land Use Example Model... 62
- Conflict among Objectives... 63
2.7: Classification Summary... 63
Exercises... 64
CHAPTER 3: Improving Search
3.1: Improving Search, Local and Global Optima... 77
- Solutions... 78
- Solutions as Vectors... 78
- Primer 1: Vectors... 79
- Example 3.1: DClub Location... 81
- Example of an Improving Search... 83
- Neighborhood Perspective... 84
- Local Optima... 85
- Local Optima and Improving Search... 85
- Local versus Global Optima... 85
- Dealing with Local Optima... 87
3.2: Search with Improving and Feasible Directions... 88
- Direction-Step Paradigm... 88
- Improving Directions... 90
- Feasible Directions... 92
- Step Size: How Far?... 94
- Algorithm 3A: Continuous Improving Search... 96
- Search of the DClub Example... 96
- When Improving Search Stops... 96
- Detecting Unboundedness... 96
3.3: Algebraic Conditions for Improving and Feasible Directions... 99
- Gradients... 99
- Primer 2: Derivatives and Partial Derivatives... 100
- Gradient Conditions for Improving Directions... 102
- Objective Function Gradients as Move Directions... 104
- Active Constraints and Feasible Directions... 105
- Linear Constraints... 107
- Conditions for Feasible Directions with Linear Constraints... 107
3.4: Unimodal and Convex Model Forms Tractable for Improving Search... 109
- Tractability and Local Optima... 109
- Unimodal Objective Functions... 109
- Linear Objective Functions... 111
- Unimodal Objective Functions and Unconstrained Local Optima... 112
- Constraints and Local Optima... 112
- Convex Feasible Sets... 113
- Algebraic Description of Line Segments... 115
- Linear Constraints and Convexity... 116
- Convex Sets and Constraint Tractability... 117
- Models for Which Local Optima Must Be Global... 118
3.5: Searching for Starting Feasible Solutions... 118
- Two Phase Method... 118
- Two Crude Model Example Revisited... 119
- Artificial Variables... 119
- Phase I Models... 120
- Starting Artificial Solution... 121
- Phase I Outcomes... 122
- Concluding Infeasibility from Phase I... 123
- The Big-M Method... 124
- Big-M Outcomes... 125
Exercises... 127
CHAPTER 4: Linear Programming Models
4.1: Allocation Models... 131
- Example 4.1: Forest Service Allocation... 132
- Allocation Decision Variables... 132
- Forest Service Allocation Model... 133
4.2: Blending Models... 135
- Example 4.2: Swedish Steel... 135
- Ingredient Decision Variables... 135
- Composition Constraints... 136
- Swedish Steel Example Model... 137
- Ratio Constraints... 138
4.3: Operations Planning Models... 139
- Example 4.3: Tubular Products Operations Planning... 139
- Tubular Products Operations Planning Model... 140
- Example 4.4: Canadian Forest Products (CFPL) Operations Planning... 141
- CFPL Decision Variables... 143
- Continuous Variables for Integer Quantities... 144
- CFPL Objective Function... 144
- CFPL Constraints... 144
- Balance Constraints... 145
- CFPL Example Model... 146
4.4: Shift Scheduling and Staff Planning Models... 148
- Example 4.5: Ohio National Bank (ONB) Shift Scheduling... 148
- ONB Decision Variables and Objective Function... 150
- ONB Constraints... 150
- Covering Constraints... 151
- ONB Shift Scheduling Example Model... 151
4.5: Time-Phased Models... 153
- Example 4.6: Institutional Food Services (IFS) Cash Flow... 153
- Time-Phased Decision Variables... 153
- Time-Phased Balance Constraints... 153
- IFS Cash Flow Model... 155
- Time Horizons... 156
4.6: Models with Linearizable Nonlinear Objectives... 157
- Example 4.7: Highway Patrol... 158
- Maxisum Highway Patrol Example Model... 158
- Minimax and Maximin Objective Functions... 158
- Nonlinear Maximin Highway Patrol Example Model... 159
- Linearizing Minimax and Maximin Objective Functions... 159
- Linearized Maximin Highway Patrol Example Model... 160
- Example 4.8: Virginia Prestress (VP) Location... 161
- Nonlinear VP Location Model... 161
- Min Deviation Objective Functions... 162
- Linearizing Min Deviation Objective Functions... 162
- Linearized VP Location Model... 163
Exercises... 164
CHAPTER 5: Simplex Search for Linear Programming
5.1: LP Optimal Solutions and Standard Form... 175
- Example 5.1: Top Brass Trophy... 175
- Global Optima in Linear Programs... 176
- Interior, Boundary and Extreme Points... 177
- Optimal Points in Linear Programs... 179
- LP Standard Form... 180
- Converting Inequalities to Nonnegativities with Slack Variables... 180
- Converting Nonpositive and Unrestricted Variables to Nonnegative... 182
- Standard Notation for LPs... 184
- Primer 3: Matrices and Matrix Arithmetic... 185
5.2: Extreme-Point Search and Basic Solutions... 186
- Determining Extreme Points with Active Constraints... 186
- Adjacent Extreme Points and Edges... 187
- Basic Solutions... 189
- Existence of Basic Solutions... 189
- Primer 4: Simultaneous Equations, Singularity and Bases... 193
- Basic Feasible Solutions and Extreme Points... 194
5.3: The Simplex Algorithm... 197
- Standard Display... 197
- Initial Basic Solution... 197
- Simplex Directions... 197
- Improving Simplex Directions and Reduced Costs... 200
- Step Size and the Minimum Ratio Rule... 201
- Updating the Basis... 203
- Rudimentary Simplex Algorithm... 204
- Algorithm 5A: Rudimentary Simplex Search for Linear Programs... 204
- Rudimentary Simplex Solution of Top Brass Example... 205
- Stopping and Global Optimality... 206
5.4: Dictionary and Tableau Representations of Simplex... 207
- Simplex Dictionaries... 207
- Simplex Tableaux... 209
- Algorithm with Dictionaries or Tableaux... 210
- Correspondence to the Search Paradigm... 210
- Comparison of Formats... 211
5.5: Two Phase Simplex... 211
- Example 5.2: Clever Clyde... 211
- Starting Basis in the Two Phase Simplex... 212
- Three Possible Outcomes for Linear Programs... 214
- Clever Clyde Infeasible Case... 214
- Algorithm 5B: Two-Phase Simplex Search.. 215
- Clever Clyde Optimal Case... 217
- Clever Clyde Unbounded Case... 219
5.6: Degeneracy and Zero-Length Simplex Steps... 220
- Degenerate Solutions... 220
- Zero-Length Simplex Steps... 221
- Progress through Changing of Bases... 222
5.7: Convergence and Cycling with Simplex... 224
- Finite Convergence with Positive Steps... 224
- Degeneracy and Cycling... 225
5.8: Doing It Efficiently: Revised Simplex... 225
- Computations with Basis Inverses... 225
- Primer 5: Identity and Inverse Matrices... 228
- Updating the Representation of B-Inverse... 230
- Basic Variable Sequence in Revised Simplex... 232
- Computing Reduced Costs by Pricing... 233
- Revised Simplex Search of Top Brass Example... 235
- Algorithm 5C: Revised Simplex Search for Linear Programs... 236
5.9: Simplex with Simple Upper and Lower Bounds... 238
- Lower and Upper-Bounded Standard Form... 238
- Basic Solutions with Lower and Upper Bounds... 239
- Unrestricted Variables with No Bounds... 240
- Increasing and Decreasing Nonbasic Variable Values... 240
- Step Size with Increasing and Decreasing Values... 241
- Case with No Basis Change... 243
- Lower- and Upper-Bounded Simplex Algorithm... 243
- Lower- and Upper-Bounded Simplex on Top Brass Example... 243
- Algorithm 5D: Lower- and Upper-Bounded Revised Simplex... 244
Exercises... 245
CHAPTER 6: Interior Point Methods for Linear Programming
6.1: Searching through the Interior... 251
- Example 6.1: Frannie's Firewood... 252
- Interior Points... 252
- Objective as a Move Direction... 252
- Boundary Strategy of Interior Point Methods... 253
- Interior in LP Standard Form... 255
- Projecting to Deal with Equality Constraints... 256
- Primer 6: Matrix Transposes... 259
- Improvement with Projected Directions... 261
6.2: Scaling with the Current Solution... 262
- Affine Scaling... 262
- Diagonal Matrix Formalization of Affine Scaling... 264
- Affine-Scaled Standard Form... 266
- Projecting on Affine-Scaled Equality Constraints... 267
- Computational Effort in Interior Point Computations... 268
6.3: Affine Scaling Search... 269
- Affine Scaling Move Directions... 269
- Feasibility and Improvement of Affine Scaling Directions... 270
- Affine Scaling Step Size... 271
- Termination in Affine Scaling Search... 273
- Affine Scaling Search of the Frannie's Firewood Example... 273
- Algorithm 6A: Affine Scaling Search for Linear Programs... 274
6.4: Log Barrier Methods for Interior Point Search... 275
- Barrier Objective Functions... 275
- Problems with Gradient Directions... 278
- Newton Steps for Barrier Search... 278
- Newton Step Barrier Search Step Sizes... 281
- Impact of the Barrier Multiplier... 284
- Barrier Algorithm Multiplier Strategy... 284
- Newton Step Barrier Algorithm... 284
- Algorithm 6B: Newton Step Barrier Search for Linear Programs... 285
- Newton Barrier Solution of Frannie's Firewood Example... 285
6.5: Dual and Primal-Dual Extensions... 287
- Duals of Standard-Form Linear Programs... 287
- Using Duals to Bound Affine Scaling Progress... 289
- Using Duals to Bound Newton Barrier Search Progress... 290
- Primal-Dual Interior Point Barrier Search... 291
- Primal-Dual Move Directions... 291
- Primal-Dual Algorithms... 292
- Algorithm 6C: Primal-Dual Interior Search for Linear Programs... 293
Exercises... 293
CHAPTER 7: Duality and Sensitivity in Linear Programming
7.1: Generic Activities versus Resources Perspective... 299
- Objective Functions as Costs and Benefits... 300
- Choosing a Direction of Inequality Constraints... 300
- Inequalities as Resource Supplies and Demands... 300
- Equality Constraints as Both Supplies and Demands... 301
- Variable-Type Constraints... 301
- Variables as Activities... 302
- LHS Coefficients as Activity Inputs and Outputs... 302
7.2: Qualitative Sensitivity to Changes in Model Coefficients... 304
- Relaxing versus Tightening Constraints... 305
- Swedish Steel Example Revisited... 305
- Effects of Changes in Right-Hand Sides... 305
- Effects of Changes in LHS Constraint Coefficients... 307
- Effects of Adding and Dropping Constraints... 308
- Effects of Unmodeled Constraints... 309
- Changing Rates of Constraint Impact... 309
- Effects of Objective Function Coefficient Changes... 311
- Changing Rates of Objective Function Coefficient Impact... 313
- Effects of Adding and Dropping Variables... 314
7.3: Quantifying Sensitivity to Changes in LP Model Coefficients: A Dual Formulation... 315
- Primals and Duals Defined... 315
- Dual Variables... 316
- Dual Variable Types... 317
- Two Crude Example Again... 317
- Dual Variables as Implicit Marginal Resource Pricing... 318
- Implicit Activity Pricing in Terms of Resources Produced and Consumed... 319
- Main Dual Constraints to Enforce Activity Pricing... 320
- Optimal Value Equality between Primal and Dual... 321
- Primal Complementary Slackness between Primal Constraints and Dual Variable Values... 322
- Dual Complementary Slackness between Dual Constraints and Primal Variable Values... 323
7.4: Formulating Linear Programming Duals... 324
- Form of the Dual for Nonnegative Primal Variables... 324
- Duals of LP Models with Nonpositive and Unrestricted Variables... 326
- Dual of the Dual Is the Primal... 328
7.5: Primal-to-Dual Relationships... 329
- Weak Duality between Objective Values... 329
- Strong Duality between Objective Values... 331
- Dual Optimum as a By-product... 332
- Complementary Slackness between Primal and Dual Optima... 335
- Unbounded and Infeasible Cases... 336
7.6: Computer Outputs and What If Changes of Single Parameters... 338
- CFPL Primal and Dual... 339
- Constraint Sensitivity Outputs... 339
- Right-Hand-Side Ranges... 341
- Constraint What If's... 344
- Variable Sensitivity Outputs... 346
- Objective Coefficient Ranges... 346
- Variable What If's... 349
- Dropping and Adding Constraint What If's... 350
- Dropping and Adding Variable What If's... 352
7.7: Bigger Model Changes, Reoptimization and Parametric Programming... 354
- Ambiguity at Limits of the RHS and Objective Coefficient Ranges... 354
- Connection between Rate Changes and Degeneracy... 356
- Reoptimization to Make Sensitivity Exact... 356
- Parametric Variation of One Coefficient... 357
- Assessing Effects of Multiple Parameter Changes... 359
- Parametric Multiple-RHS Change... 359
- Parametric Change of Multiple Objective Function Coefficients... 361
Exercises... 363
CHAPTER 8: Multiobjective Optimization and Goal Programming
8.1: Multiobjective Optimization Models... 373
- Example 8.1: Bank Three Investment... 373
- Bank Three Example Objectives... 374
- Bank Three Example Model... 375
- Example 8.2: Dynamometer Ring Design... 375
- Dynamometer Ring Design Model... 376
- Example 8.3: Hazardous Waste Disposal... 376
- Hazardous Waste Disposal Model... 378
8.2: Efficient Points and the Efficient Frontier... 378
- Efficient Points... 379
- Identifying Efficient Points Graphically... 379
- Efficient Frontier... 381
- Plots in Objective Value Space... 382
- Constructing the Efficient Frontier... 382
8.3: Preemptive Optimization and Weighted Sums of Objectives... 384
- Preemptive Optimization... 384
- Preemptive Optimization of the Bank Three Example... 384
- Preemptive Optimization and Efficient Points... 386
- Preemptive Optimization and Alternative Optima... 387
- Weighted Sums of Objectives... 387
- Weighted-Sum Optimization of the Hazardous Waste Example... 388
- Weighted-Sum Optimization and Efficient Points... 389
8.4: Goal Programming... 389
- Goal or Target Levels... 390
- Goal Form of Bank Three Example... 390
- Soft Constraints... 391
- Deficiency Variables... 391
- Expressing Soft Constraints In Mathematical Programs... 391
- Goal Program Objective Function: Minimizing (Weighted) Deficiency... 392
- Goal Linear Program Model of the Bank Three Example... 393
- Alternative Deficiency Weights in the Objective... 393
- Preemptive Goal Programming... 394
- Preemptive Goal Programming of the Bank Three Example... 395
- Preemptive Goal Programming by Weighting the Objective... 396
- Practical Advantage of Goal Programming in Multiobjective Problems... 397
- Goal Programming and Efficient Points... 397
- Modified Goal Program Formulation for Efficient Points... 399
Exercises... 400
CHAPTER 9: Shortest Paths and Discrete Dynamic Programming
9.1: Shortest Path Models... 409
- Example 9.1: Littleville... 409
- Nodes, Arcs, Edges and Graphs... 410
- Paths... 411
- Shortest Path Problems... 413
- Classification of Shortest Path Models... 413
- Example 9.2: Texas Transfer... 413
- Example 9.3: Two Ring Circus... 414
- Undirected and Directed Graphs (Digraphs)... 414
- Two Ring Example Model... 417
9.2: Dynamic Programming Approach to Shortest Paths... 417
- Families of Shortest Path Models... 417
- Functional Notation... 418
- Optimal Paths and Sub-Paths... 419
- Negative Dicycles Exception... 420
- Principle of Optimality... 421
- Functional Equations... 421
- Functional Equations for One Node to All Others... 421
- Sufficiency of Functional Equations in the One to All Case... 422
- Functional Equations for All Nodes to All Others... 425
- Solving Shortest Path Problems by Linear Programming... 426
9.3: Shortest Paths from One Node to All Others: Bellman-Ford... 426
- Solving the Functional Equations... 427
- Repeated Evaluation Algorithm: Bellman-Ford... 427
- Algorithm 9A: One to All (No Negative Dicycles); Bellman-Ford... 428
- Bellman-Ford Solution of the Two Ring Circus Example... 428
- Justification of the Bellman-Ford Algorithm... 431
- Recovering Optimal Paths... 431
- Encountering Negative Dicycles with Bellman-Ford... 432
9.4: Shortest Paths from All Nodes to All Others: Floyd-Warshall... 433
- Floyd-Warshall Algorithm... 433
- Algorithm 9B: All to All (No Negative Dicycles); Floyd-Warshall... 434
- Floyd-Warshall Solution of the Littleville Example... 434
- Recovering Optimal Paths... 438
- Detecting Negative Dicycles with Floyd-Warshall... 439
9.5: Shortest Path from One Node to All Others with Costs Nonnegative: Dijkstra... 440
- Algorithm 9C: One to All (Nonnegative Costs); Dijkstra... 440
- Permanently and Temporarily Labeled Nodes... 440
- Least Temporary Criterion for Next Permanent Node... 441
- Dijkstra Algorithm Solution of the Texas Transfer Example... 441
- Recovering Optimal Paths... 445
- Justification of the Dijkstra Algorithm... 445
9.6: Shortest Paths from One Node to All Others in Acyclic Digraphs... 446
- Acyclic Digraphs... 446
- Shortest Path Algorithm for Acyclic Digraphs... 449
- Algorithm 9D: Shortest One to All Paths (Acyclic Digraph)
- Acyclic Shortest Path Example... 449
9.7: CPM Project Scheduling and Longest Paths... 450
- Project Management... 450
- Example 9.4: We Build Construction... 451
- CPM Project Networks... 451
- CPM Schedules and Longest Paths... 453
- Critical Paths... 453
- Computing an Early Start Schedule for the We Build Construction Example... 454
- Algorithm 9E: CPM Early Start Scheduling... 455
- Late Start Schedules and Schedule Slack... 456
- Difficulty of General Longest Path Problems... 458
- Acyclic Character of Project Networks... 458
9.8: Discrete Dynamic Programming Models... 458
- Sequential Decision Problems... 458
- Example 9.5: Wagner-Whitin Lot-Sizing... 459
- States in Dynamic Programming... 459
- Digraphs for Dynamic Programs... 460
- Dynamic Programming Solutions as an Optimal Path... 461
- Dynamic Programming Functional Equations... 461
- Dynamic Programming Models with Both Stages and States... 462
- Example 9.6: President's Library... 463
- Dynamic Programming Modeling of the President's Library Example... 464
- Backwards Solution of Dynamic Programs... 466
- Multiple Problem Solutions Obtained Simultaneously... 468
Exercises... 468
CHAPTER 10: Network Flows
10.1: Graphs, Networks and Flows... 475
- Digraphs, Nodes and Arcs... 475
- Example 10.1: Optimal Ovens, Incorporated (OOI)... 476
- OOI Example Network... 476
- Minimum Cost Flow Models... 477
- Sources, Sinks and Transshipment Nodes... 477
- OOI Example Model... 478
- Total Supply = Total Demand... 480
- Node-Arc Incidence Matrices and Matrix Standard Form... 481
10.2: Cycle Directions for Network Flow Search... 483
- Chains, Paths, Cycles and Dicycles... 483
- Cycle Directions... 484
- Maintaining Flow Balance with Cycle Directions... 486
- Feasible Cycle Directions... 487
- Improving Cycle Directions... 490
- Step Size with Cycle Directions... 491
- Sufficiency of Cycle Directions... 492
10.3: Rudimentary Cycle Direction Search Algorithms for Network Flows... 494
- Rudimentary Cycle Direction Search of the OOI Example... 494
- Algorithm 10A: Rudimentary Cycle Direction Search... 495
- Finding Starting Feasible Solutions... 497
- Artificial Network Flow Model... 498
- Network Flows versus Linear Programming... 499
10.4: Integrality of Optimal Network Flows... 500
- When Optimal Flows Must Be Integer... 500
- Total Unimodularity of Node-Arc Incidence Matrices... 501
10.5: Transportation and Assignment Models... 502
- Transportation Problems... 502
- Standard Form for Transportation Problems... 503
- Example 10.2: Marine Mobilization Transportation Problem... 504
- Assignment Problems... 506
- Example 10.3: CAM Assignment... 507
- Balancing Unequal Sets with Dummy Elements... 508
- Linear Assignment as Network Flows with Integer Solutions... 508
- CAM Assignment Example Model... 510
- Tableau Representation of Transportation and Assignment Problems... 510
10.6: Other Single-Commodity Network Flow Models... 511
- Network Flow Formulation of Shortest Path Problems... 512
- Maximum Flow Problems... 513
- Example 10.4: Building Evacuation Maximum Flow... 514
- Return Arc Network Flow Formulation of Maximum Flow Problems... 515
- Time-Expanded Flow Models and Networks... 517
- Example 10.5: Agrico Chemical... 517
- Time-Expanded Modeling of Agrico Example... 517
10.7: Network Simplex Algorithm for Optimal Flows... 519
- Linear Dependence in Node-Arc Matrices and Cycles... 519
- Spanning Trees of Networks... 522
- Spanning Tree Bases for Network Flow Models... 523
- Network Basic Solutions... 524
- Simplex Cycle Directions... 525
- Network Simplex Algorithm... 526
- Network Simplex Solution of OOI Example... 526
- Algorithm 10B: Network Simplex Search... 527
10.8: Cycle Canceling Algorithms for Optimal Flows... 529
- Residual Digraphs... 529
- Feasible Cycle Directions and Dicycles of Residual Digraphs... 530
- Improving Feasible Cycle Directions and Negative Dicycles of Residual Digraphs... 531
- Using the Floyd-Warshall Algorithm to Find Cycle Directions... 532
- Cycle Canceling Solution of the OOI Example... 533
- Algorithm 10C: Cycle Canceling for Network Flows... 534
10.9: Multicommodity and Gain/Loss Flows... 536
- Multicommodity Flows... 536
- Example 10.6: Bay Ferry Multicommodity Flow... 537
- Multicommodity Flow Models... 538
- Tractability of Multicommodity Flow Models... 540
- Flows with Gains and Losses... 541
- Example 10.7: Tinyco Cash Flow 541
- Gain and Loss Network Flow Models... 542
- Tractability of Network Flows with Gains and Losses... 543
Exercises... 543
CHAPTER 11: Discrete Optimization Models
11.1: Lumpy Linear Programs and Fixed Charges... 555
- Swedish Steel Example with All-or-Nothing Constraints... 555
- ILP Modeling of All-or-Nothing Requirements... 556
- Swedish Steel Model with All-or-Nothing Constraints... 556
- ILP Modeling of Fixed Charges... 558
- Swedish Steel Example with Fixed Charges... 558
11.2: Knapsack and Capital Budgeting Models... 560
- Knapsack Problems... 561
- Example 11.1: Indy Car Knapsack... 561
- Capital Budgeting Models... 562
- Example 11.2: NASA Capital Budgeting... 562
- Budget Constraints... 563
- Modeling Mutually Exclusive Choices... 564
- Modeling Dependencies between Projects... 565
- NASA Example Model... 565
11.3: Set Packing, Covering and Partitioning Models... 566
- Example 11.3: EMS Location Planning... 566
- Set Packing, Covering and Partitioning Constraints... 567
- Minimum Cover EMS Model... 569
- Maximum Coverage EMS Model... 570
- Column Generation Models... 572
- Example 11.4: AA Crew Scheduling... 572
- Column Generation Model for AA Example... 573
11.4: Assignment and Matching Models... 574
- Assignment Constraints... 575
- CAM Linear Assignment Example Revisited... 575
- Linear Assignment Models... 576
- Quadratic Assignment Models... 576
- Example 11.5: Mall Layout Quadratic Assignment... 577
- Mall Layout Example Model... 578
- Generalized Assignment Models... 580
- Example 11.6: CDOT Generalized Assignment... 580
- CDOT Example Model... 581
- Matching Models... 582
- Example 11.7: Superfi Speaker Matching... 583
- Superfi Example Model... 583
- Tractability of Assignment and Matching Models... 584
11.5: Traveling Salesman and Routing Models... 584
- Traveling Salesman Problem... 584
- Example 11.8: NCB Circuit Board TSP... 585
- Symmetric versus Asymmetric Cases of the TSP... 585
- Formulating the Symmetric TSP... 586
- Subtours... 587
- ILP Model of the Symmetric TSP... 589
- ILP Model of the Asymmetric TSP... 589
- Quadratic Assignment Formulation of the TSP... 591
- Problems Requiring Multiple Routes... 592
- Example 11.9: KI Truck Routing... 592
- KI Truck Routing Example Model... 593
11.6: Facility Location and Network Design Models... 595
- Facility Location Models... 594
- Example 11.10: Tmark Facilities Location... 595
- ILP Model of Facilities Location... 596
- Tmark Facilities Location Example Model... 597
- Network Design Models... 598
- Example 11.11: Wastewater Network Design... 599
- Wastewater Network Design Example Model... 600
11.7: Processor Scheduling and Sequencing Models... 602
- Example 11.11: Nifty Notes Single-Machine Scheduling... 602
- Single-Processor Scheduling Problems... 602
- Time Decision Variables... 603
- Conflict Constraints and Disjunctive Variables... 603
- Handling of Due Dates... 605
- Processor Scheduling Objective Functions... 605
- ILP Formulation of Minmax Scheduling Objectives... 607
- Equivalences among Scheduling Objective Functions... 608
- Job Shop Scheduling... 609
- Example 11.13: Custom Metalworking Job Shop... 609
- Custom Metalworking Decision Variables and Objective... 610
- Precedence Constraints... 610
- Conflict Constraints in Job Shops... 611
- Custom Metalworking Example Model... 612
Exercises... 613
CHAPTER 12: Discrete Optimization Methods
12.1: Solving by Total Enumeration... 627
- Total Enumeration... 628
- Swedish Steel All-or-Nothing Example... 628
- Exponential Growth of Cases to Enumerate... 629
- Nonlinearities... 630
12.2: Relaxations of Discrete Optimization Models and Their Uses... 630
- Example 12.1: Bison Boosters... 631
- Constraint Relaxations... 632
- Linear Programming Relaxations... 633
- Proving Infeasibility with Relaxations... 634
- Solution Value Bounds from Relaxations... 635
- Optimal Solutions from Relaxations... 637
- Rounded Solutions from Relaxations... 639
12.3: Stronger LP Relaxations, Valid Inequalities, and Lagrangian Relaxations... 641
- Stronger LP Relaxations... 642
- Choosing Big-M Constants... 642
- Valid Inequalities... 644
- Lagrangian Relaxations... 647
- Lagrangian Relaxation of the CDOT Example... 647
- Tractable (Integer) Lagrangian Relaxations... 649
- Lagrangian Relaxation Bounds... 649
- Choosing Lagrange Multipliers... 650
12.4: Branch and Bound Search... 651
- Example 12.2: River Power... 651
- Partial Solutions... 651
- Completions of Partial Solutions... 652
- Tree Search... 652
- Incumbent Solutions... 655
- Candidate Problems... 656
- Terminating Partial Solutions with Relaxations... 658
- LP-Based Branch and Bound... 660
- Algorithm 12A: LP-Based Branch and Bound (0-1 ILPs).. 660
- Branching Rules for LP-Based Branch and Bound... 661
- LP-Based Branch and Bound Solution of the River Power Example... 662
12.5: Rounding, Parent Bounds, Enumeration Sequences and Stopping Early in Branch and Bound... 664
- Branch and Bound Solution of NASA Capital Budgeting Example... 664
- Rounding for Incumbent Solutions... 664
- Branch and Bound Family Tree Terminology... 668
- Parent Bounds... 668
- Terminating with Parent Bounds... 669
- Stopping Early: Branch and Bound as a Heuristic... 670
- Bounds on the Error of Stopping with the Incumbent Solution... 670
- Depth First, Best First and Depth Forward Best Back... 671
- Branch and Cut Search... 676
- Branch and Cut Solution of the River Power Example... 676
- Algorithm 12B: Branch and Cut (0-1 ILPs)... 677
12.6: Improving Search Heuristics and Discrete Optimization INLPs... 680
- Rudimentary Improving Search Algorithm... 680
- Discrete Neighborhoods and Move Sets... 680
- Algorithm 12C: Discrete Improving Search... 681
- NCB Example Revisited... 682
- Choosing a Move Set... 682
- Rudimentary Improving Search of the NCB Example... 684
- Multistart Search... 685
12.7: Tabu, Simulated Annealing, and Genetic Algorithm Extensions of Improving Search... 687
- Difficulty of Allowing Nonimproving Moves... 687
- Tabu Search... 687
- Algorithm 12D: Tabu Search... 688
- Tabu Search of the NCB Example... 688
- Simulated Annealing Search... 690
- Algorithm 12E: Simulated Annealing Search... 691
- Simulated Annealing Search of NCB Example... 692
- Genetic Algorithms... 694
- Crossover Operations in Genetic Algorithms... 695
- Managing Genetic Algorithms with Elites, Immigrants and Crossovers... 695
- Algorithm 12E: Genetic Algorithm Search... 696
- Solution Encoding for Genetic Algorithm Search... 696
- Genetic Algorithm Search of NCB Example... 697
12.8: Constructive Heuristics... 698
- Rudimentary Constructive Search Algorithm... 698
- Algorithm 12G: Rudimentary Constructive Search... 699
- Greedy Choices of Variables to Fix... 699
- Greedy Rule for NASA Example... 699
- Constructive Heuristic Solution of NASA Example... 701
- Method of Last Resort... 703
- Constructive Search of KI Truck Routing Example... 703
Exercises... 705
CHAPTER 13: Unconstrained Nonlinear Programming
13.1: Unconstrained Nonlinear Programming Models... 715
- Example 13.1: USPS Single Variable... 716
- USPS Single Variable Example Model... 717
- Neglecting Constraints to Use Unconstrained Methods... 717
- Curve Fitting and Regression Problems... 718
- Example 13.2: Custom Computer Curve Fitting... 718
- Linear versus Nonlinear Regression... 719
- Regression Objective Functions... 720
- Custom Computer Curve Fitting Example Model... 720
- Maximum Likelihood Estimation Problems... 721
- Example 13.3: PERT Maximum Likelihood... 722
- PERT Maximum Likelihood Example Model... 723
- Smooth and Nonsmooth Functions and Derivatives... 724
- Usable Derivatives... 725
13.2: One-Dimensional Search... 726
- Unimodal Objective Functions... 726
- Golden Section Search... 727
- Golden Section Solution of USPS Example... 729
- Algorithm 13A: Golden Section Search... 729
- Bracketing and 3-Point Patterns... 731
- Finding a 3-Point Pattern... 732
- Algorithm 13B: Three-Point Pattern... 733
- Quadratic Fit Search... 734
- Quadratic Fit Solution of USPS Example... 735
- Algorithm 13C: Quadratic Fit Search... 736
13.3: Derivatives, Taylor Series, and Conditions for Local Optima... 737
- Improving Search Paradigm... 737
- Local Information and Neighborhoods... 738
- First Derivatives and Gradients... 738
- Second Derivatives and Hessian Matrices... 739
- Primer 7: Second Derivatives and Hessian Matrices... 740
- Taylor Series Approximations with One Variable... 741
- Taylor Series Approximations with Multiple Variables... 742
- Stationary Points and Local Optima... 743
- Saddle Points... 745
- Hessian Matrices and Local Optima... 745
- Primer 8: Positive and Negative (Semi)Definite Matrices... 747
13.4: Convex/Concave Functions and Global Optimality... 749
- Convex and Concave Functions Defined... 750
- Sufficient Conditions for Unconstrained Global Optima... 752
- Convex/Concave Functions and Stationary Points... 753
- Tests for Convex and Concave Functions... 753
- Unimodal versus Convex/Concave Objectives... 756
13.5: Gradient Search... 757
- Gradient Search Algorithm... 757
- Algorithm 13D: Gradient Search... 757
- Gradient Search of Custom Computer Example... 758
- Steepest Ascent/Descent Property... 760
- Zigzagging and Poor Convergence of Gradient Search... 761
13.6: Newton's Method... 761
- Newton Step... 762
- Newton's Method... 763
- Newton's Method on the Custom Computer Example... 763
- Algorithm 13E: Newton's Method... 764
- Rapid Convergence Rate of Newton's Method... 765
- Computational Tradeoffs between Gradient and Newton Search... 765
- Starting Close with Newton's Method... 766
13.7: Quasi-Newton Methods and BFGS Search... 766
- Deflection Matrices... 766
- Quasi-Newton Approach... 767
- Guaranteeing Directions Improve... 768
- BFGS Formula... 768
- BFGS Search of Custom Computer Example... 769
- Algorithm 13F: BFGS Quasi-Newton Search... 770
- Verifying Quasi-Newton Requirements... 773
- Approximating the Hessian Inverse with BFGS... 774
13.8: Optimization Without Derivatives and Nelder-Mead... 774
- Nelder-Mead Strategy... 774
- Algorithm 13G: Nelder-Mead Derivative-Free Search... 775
- Nelder-Mead Direction... 777
- Nelder-Mead Limited Step Sizes... 778
- Nelder-Mead Shrinking... 780
- Nelder-Mead Search of PERT Example... 781
Exercises... 781
CHAPTER 14: Constrained Nonlinear Programming
14.1: Constrained Nonlinear Programming Models... 787
- Example 14.1: Beer Belge Location Allocation... 787
- Beer Belge Location Allocation Model... 788
- Linearly Constrained Nonlinear Programs... 789
- Example 14.2: Texaco Gasoline Blending... 789
- Texaco Gasoline Blending Model... 790
- Engineering Design Models... 792
- Example 14.3: Oxygen System Engineering Design... 792
- Oxygen System Engineering Design Model... 793
14.2: Convex, Separable, Quadratic and Posynomial Geometric Programming Special NLP Forms... 795
- Example 14.4: Pfizer Optimal Lot Sizing... 795
- Pfizer Optimal Lot Sizing Model... 796
- Convex Programs... 797
- Special Tractability of Convex Programs... 799
- Separable Programs... 801
- Special Tractability of Separable Programs... 802
- Example 14.5: Quadratic Portfolio Management... 803
- Quadratic Portfolio Management Model... 803
- Quadratic Programs Defined... 804
- Special Tractability of Quadratic Programs... 805
- Example 14.6: Cofferdam Design... 805
- Cofferdam Example Model... 806
- Posynomial Geometric Programs... 807
- Special Tractability of Posynomial Geometric Programs... 809
14.3: Lagrange Multiplier Methods... 810
- Reducing to Equality Form... 810
- Lagrangian Function and Lagrange Multipliers... 811
- Stationary Points of the Lagrangian Function... 812
- Lagrangian Stationary Points and the Original Model... 813
- Lagrange Multiplier Procedure... 813
- Interpretation of Lagrange Multipliers... 815
- Limitations of the Lagrangian Approach... 816
14.4: Karush-Kuhn-Tucker Optimality Conditions... 817
- Full Differentiable NLP Model... 817
- Complementary Slackness Conditions... 818
- Lagrange Multiplier Sign Restrictions... 818
- KKT Conditions and KKT Points... 819
- Improving Feasible Directions and Local Optima Revisited... 821
- KKT Conditions and Existence of Improving Feasible Directions... 822
- Sufficiency of KKT Conditions for Optimality... 825
- Necessity of KKT Conditions for Optimality... 826
14.5: Penalty and Barrier Methods... 827
- Penalty Methods... 827
- Example 14.7: Service Desk Design... 827
- Penalty Treatment of the Service Desk Example... 828
- Concluding Constrained Optimality with Penalties... 829
- Differentiability of Penalty Functions... 829
- Exact Penalty Functions... 830
- Managing the Penalty Multiplier... 831
- Sequential Unconstrained Penalty Technique... 832
- Algorithm 14A: Sequential Unconstrained Penalty Technique... 832
- Barrier Methods... 833
- Barrier Treatment of Service Desk Example... 834
- Converging to Optimality with Barrier Methods... 834
- Managing the Barrier Multiplier... 835
- Sequential Unconstrained Barrier Technique... 836
- Algorithm 14B: Sequential Unconstrained Barrier Technique... 836
14.6: Reduced Gradient Algorithms... 837
- Standard Form of NLPs with Linear Constraints... 837
- Example 14.8: Filter Tuning... 837
- Conditions for Feasible Directions with Linear Constraints... 838
- Bases of the Main Linear Equalities... 838
- Basic, Nonbasic and Superbasic Variables... 839
- Maintaining Equalities by Solving Main Constraints for Basic Variables... 840
- Active Nonnegativities and Degeneracy... 841
- Reduced Gradient... 841
- Reduced Gradient Move Direction... 842
- Line Search in Reduced Gradient Methods... 843
- Basis Changes in Reduced Gradient Methods... 844
- Reduced Gradient Algorithm... 845
- Reduced Gradient Search of Filter Tuning Example... 845
- Algorithm 14C: Reduced Gradient Search... 846
- Major and Minor Iterations in Reduced Gradient... 847
- Second-Order Extensions of Reduced Gradient... 848
- Generalized Reduced Gradient Procedures for Nonlinear Constraints... 848
14.7: Quadratic Programming Methods... 849
- General Symmetric Form of Quadratic Programs... 849
- Quadratic Program Form of the Filter Tuning Example... 849
- Equality-Constrained Quadratic Programs and KKT Conditions... 850
- Direct Solution of KKT Conditions for Quadratic Programs... 851
- Active Set Strategies for Quadratic Programming... 852
- Step Size... 853
- Stopping at a KKT Point with Active Set Methods... 854
- Dropping a Constraint from the Active Set... 855
- Active Set Solution of the Filter Tuning Example... 856
- Algorithm 14D: Active Set Method for Quadratic Programs... 856
14.8: Separable Programming Methods... 858
- Pfizer Example Revisited... 858
- Piecewise Linear Approximation to Separable Functions... 860
- Linear Program Representation of Separable Programs... 862
- Correctness of the LP Approximation to Separable Programs... 863
- Convex Separable Programs... 864
- Difficulties with Nonconvex Separable Programs... 865
14.9: Posynomial Geometric Programming Methods... 866
- Posynomial Geometric Program Form... 866
- Cofferdam Example Revisited... 867
- Logarithmic Change of Variables in GPs... 868
- Convex Transformed GP Model... 869
- Direct Solution of the Transformed Primal GP... 869
- Dual of a Geometric Program... 870
- Degrees of Difficulty and Solving the GP Dual... 872
- Recovering a GP Primal Solution... 872
- Derivation of the GP Dual... 873
- Signomial Extension of GPs... 874
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