Optimization for Decision Making (eBook)

Preface 6
Contents 11
Glossary of Symbols and Abbreviations 18
1 Linear Equations, Inequalities, Linear Programming: A Brief Historical Overview 24
1.1 Mathematical Modeling, Algebra, Systems of Linear Equations, and Linear Algebra 24
1.1.1 Elimination Method for Solving Linear Equations 25
1.2 Review of the GJ Method for Solving Linear Equations: Revised GJ Method 28
1.2.1 GJ Method Using the Memory Matrix to Generate the Basis Inverse 31
1.2.2 The Revised GJ Method with Explicit Basis Inverse 34
1.3 Lack of a Method to Solve Linear Inequalities Until Modern Times 37
1.3.1 The Importance of Linear Inequality Constraints and Their Relation to Linear Programs 38
1.4 Fourier Elimination Method for Linear Inequalities 40
1.5 History of the Simplex Method for LP 41
1.6 The Simplex Method for Solving LPs and Linear Inequalities Viewed as an Extension of the GJ Method 42
1.6.1 Generating the Phase I Problem if No Feasible Solution Available for the Original Problem 42
1.7 The Importance of LP 44
1.7.1 Marginal Values and Other Planning Toolsthat can be Derived from the LP Model 45
1.8 Dantzig's Contributions to Linear Algebra, Convex Polyhedra, OR, Computer Science 50
1.8.1 Contributions to OR 50
1.8.2 Contributions to Linear Algebra and Computer Science 50
1.8.3 Contributions to the Mathematical Study of Convex Polyhedra 51
1.9 Interior Point Methods for LP 52
1.10 Newer Methods 53
1.11 Conclusions 53
1.12 How to Be a Successful Decision Maker? 53
1.13 Exercises 54
References 60
2 Formulation Techniques Involving Transformationsof Variables 62
2.1 Operations Research: The Science of Better 62
2.2 Differentiable Convex and Concave Functions 63
2.2.1 Convex and Concave Functions 63
2.3 Piecewise Linear (PL) Functions 69
2.3.1 Convexity of PL Functions of a Single Variable 70
2.3.2 PL Convex and Concave Functions in Several Variables 71
2.4 Optimizing PL Functions Subject to Linear Constraints 76
2.4.1 Minimizing a Separable PL Convex Function Subject to Linear Constraints 76
2.4.2 Min-max, Max-min Problems 80
2.4.3 Minimizing Positive Linear Combinations of Absolute Values of Affine Functions 82
2.4.4 Minimizing the Maximum of the Absolute Values of Several Affine Functions 84
2.4.5 Minimizing Positive Combinationsof Excesses/Shortages 92
2.5 Multiobjective LP Models 95
2.5.1 Practical Approaches for Handling Multiobjective LPs in Current Use 97
2.5.2 Weighted Average Technique 98
2.5.3 The Goal Programming Approach 99
2.6 Exercises 102
References 147
3 Intelligent Modeling Essential to Get Good Results 149
3.1 The Need for Intelligent Modeling in Real WorldDecision Making 149
3.2 Case Studies Illustrating the Need for Intelligent Modeling 150
3.2.1 Case Study 1: Application in a Container Shipping Terminal 150
3.2.2 Case Study 2: Application in a Bus Rental Company 162
3.2.3 Case Study 3: Allocating Gates to Flights at an International Airport 172
3.3 Murty's Three Commandments for SuccessfulDecision Making 186
3.4 Exercises 186
References 187
4 Polyhedral Geometry 189
4.1 Hyperplanes, Half-Spaces, and Convex Polyhedra 189
4.1.1 Expressing a Linear Equation as a Pair of Inequalities 189
4.1.2 Straight Lines, Half-Lines, and Their Directions 191
4.1.3 Convex Combinations, Line Segments 192
4.2 Tight (Active)/Slack (Inactive) Constraints at a Feasible Solution 193
4.2.1 What is the Importance of Classifying the Constraints in a System as Active/Inactive at a Feasible Solution? 195
4.3 Subspaces, Affine Spaces, Convex Polyhedra Binding, Nonbinding, Redundant Inequalities
4.4 The Interior and the Boundary of a Convex Polyhedron 198
4.5 Supporting Hyperplanes, Faces of a Convex Polyhedron, Optimum Face for an LP 199
4.5.1 Supporting Hyperplanes 199
4.5.2 Faces of a Convex Polyhedron 200
4.6 Zero-Dimensional Faces, or Extreme Points, or Basic Feasible Solutions (BFSs) 202
4.6.1 Nondegenerate, Degenerate BFSs for Systems in Standard Form 206
4.6.2 Basic Vectors and Bases for a System in Standard Form 207
4.6.3 BFSs for Systems in Standard Form for Bounded Variables 209
4.7 Purification Routine for Deriving a BFSs from a Feasible Solution for Systems in Standard Form 210
4.7.1 The Main Strategy of the Purification Routine 211
4.7.2 General Step in the Purification Routine 212
4.7.3 Purification Routine for Systems in Symmetric Form 218
4.8 Edges, One-Dimensional Faces, Adjacency of Extreme Points, Extreme Directions 226
4.8.1 How to Check if a Given Feasible Solution is on an Edge 227
4.9 Adjacency in a Primal Simplex Pivot Step 234
4.10 How to Obtain All Adjacent Extreme Points of a Given Extreme Point? 240
4.11 Faces of Dimension 2 of a Convex Polyhedron 243
4.11.1 Facets of a Convex Polyhedron 244
4.12 Optimality Criterion in the Primal Simplex Algorithm 245
4.13 Boundedness of Convex Polyhedra 248
4.14 Exercises 251
References 255
5 Duality Theory and Optimality Conditions for LPs 256
5.1 The Dual Problem 256
5.2 Deriving the Dual by Rational Economic Arguments 257
5.2.1 Dual Variables are Marginal Values 259
5.2.2 The Dual of the General Problem in This Form 259
5.3 Rules for Writing the Dual of a General LP 260
5.3.1 Complementary Pairs in a Primal, Dual Pair of LPs 262
5.3.2 What Is the Importance of Complementary Pairs? 263
5.3.3 Complementary Pairs for LPs in Standard Form 263
5.3.4 Complementary Pairs for LPs in Symmetric Form 265
5.3.5 Complementary Pairs for LPs in Bounded Variable Standard Form 266
5.4 Duality Theory and Optimality Conditions for LP 268
5.4.1 The Importance of Good Lower Bounding Strategies in Solving Optimization Problems 270
5.4.2 Definition of the Dual Solution Corresponding to Each Primal Basic Vector for an LP in Standard Form 272
5.4.3 Properties Satisfied by the Primal and Dual Basic Solutions Corresponding to a Primal Basic Vector 275
5.4.4 The Duality Theorem of LP 278
5.4.5 Optimality Conditions for LP 279
5.4.6 Necessary and Sufficient Optimality Conditions for LP 281
5.4.7 Duality Gap, a Measure of Distance from Optimality 281
5.4.8 Using CS Conditions to Check the Optimality of a Given Feasible Solution to an LP 282
5.5 How Various Algorithms Solve LPs 289
5.6 How to Check if an Optimum Solution is Unique 290
5.6.1 Primal and Dual Degeneracy of a Basic Vector for an LP in Standard Form 290
5.6.2 Sufficient Conditions for Checking the Uniqueness of Primal and Dual Optimum Solutions 292
5.6.3 Procedure to Check if the BFS Corresponding to an Optimum Basic Vector xB is the Unique Optimum Solution 293
5.6.4 The Optimum Face for an LP 296
5.7 Mathematical Equivalence of LP to the Problem of Finding a Feasible Solution of a System of Linear Constraints Involving Inequalities 297
5.8 Marginal Values and the Dual Optimum Solution 298
5.9 Summary of Optimality Conditions for Continuous Variable Nonlinear Programs and Their Relation to Those for LP 300
5.9.1 Global Minimum (Maximum), Local Minimum (Maximum), and Stationary Points 300
5.9.2 Relationship to Optimality Conditions for LP Discussed Earlier 305
5.10 Exercises 306
References 317
6 Revised Simplex Variants of the Primal and Dual Simplex Methods and Sensitivity Analysis 318
6.1 Primal Revised Simplex Algorithm Using the Explicit Basis Inverse 319
6.1.1 Steps in an Iteration of the Primal Simplex Algorithm When (xB, –z) is the Primal Feasible Basic Vector 320
6.1.2 Practical Consequences of Satisfying the Unboundedness Criterion 327
6.1.3 Features of the Simplex Algorithm 328
6.2 Revised Primal Simplex Method (Phase I, II) with Explicit Basis Inverse 328
6.2.1 Setting Up the Phase I Problem 328
6.3 How to Find a Feasible Solution to a System of Linear Constraints 335
6.4 Infeasibility Analysis 337
6.5 Practical Usefulness of the Revised Simplex Method Using Explicit Basis Inverse 339
6.6 Cycling in the Simplex Method 340
6.7 Revised Simplex Method Using the Product Form of the Inverse 341
6.7.1 Pivot Matrices 341
6.7.2 A General Iteration in the Revised Simplex Method Using the Product Form of the Inverse 342
6.7.3 Transition from Phase I to Phase II 343
6.7.4 Reinversions in the Revised Simplex Method Using PFI 344
6.8 Revised Simplex Method Using Other Factorizations of the Basis Inverse 345
6.9 Finding the Optimum Face of an LP (Alternate Optimum Solutions) 345
6.10 The Dual Simplex Algorithm 347
6.10.1 Properties of the Dual Simplex Algorithm 355
6.11 Importance of the Dual Simplex Algorithm, How to Get New Optimum Efficiently When RHS Changes or New Constraints Are Added to the Model 358
6.11.1 The Dual Simplex Method 363
6.12 Marginal Analysis 363
6.12.1 How to Compute the Marginal Values in a General LP Model 366
6.13 Sensitivity Analysis 368
6.13.1 Introducing a New Nonnegative Variable 368
6.13.2 Ranging the Cost Coefficient or an I/O Coefficient in a Nonbasic Column Vector 370
6.13.3 Ranging a Basic Cost Coefficient 373
6.13.4 Ranging the RHS Constants 374
6.13.5 Features of Sensitivity Analysis Available in Commercial LP Software 375
6.13.6 Other Types of Sensitivity Analyses 376
6.14 Revised Primal Simplex Method for Solving Bounded Variable LP Models 376
6.14.1 The Bounded Variable Primal Simplex Algorithm 379
6.14.2 General Iteration in the Bounded Variable Primal Simplex Algorithm 380
6.14.3 The Bounded Variable Primal Simplex Method 383
6.15 Exercises 384
References 413
7 Interior Point Methods for LP 414
7.1 Boundary Point and Interior Point Methods 414
7.2 Interior Feasible Solutions 415
7.3 General Introduction to Interior Point Methods 415
7.4 Center, Analytic Center, Central Path 420
7.5 The Affine Scaling Method 422
7.6 Newton's Method for Solving Systems of Nonlinear Equations 429
7.7 Primal-Dual Path Following Methods 430
7.8 Summary of Results on the Primal-Dual IPMs 435
7.9 Exercises 436
References 437
8 Sphere Methods for LP 438
8.1 Introduction 438
8.2 Ball Centers: Geometric Concepts 443
8.3 Approximate Computation of Ball Centers 446
8.3.1 Approximate Computation of Ball Centersof Polyhedra 446
8.3.2 Computing An Approximate Ball Center of K on the Current Objective Plane 451
8.3.3 Ball Centers of Some Simple Special Polytopes 451
8.4 Sphere Method 1 452
8.4.1 Summary of Computational Results on Sphere Method 1 456
8.5 Sphere Method 2 457
8.6 Improving the Performance of Sphere Methods Further 460
8.7 Some Open Theoretical Research Problems 461
8.8 Future Research Directions 463
8.9 Exercises 463
References 465
9 Quadratic Programming Models 466
9.1 Introduction 466
9.2 Superdiagonalization Algorithm for Checking PD and PSD 467
9.3 Classification of Quadratic Programs 472
9.4 Types of Solutions and Optimality Conditions 473
9.5 What Types of Solutions Can Be Computed Efficiently by Existing Algorithms? 475
9.6 Some Important Applications of QP 476
9.7 Unconstrained Quadratic Minimization in ClassicalMathematics 479
9.8 Summary of Some Existing Algorithms for Constrained QPs 480
9.9 The Sphere Method for QP 482
9.9.1 Procedure for Getting an Approximate Solution for (9.6) 483
9.9.2 Descent Steps 485
9.9.3 The Algorithm 488
9.9.4 The Case when the Matrix D is not Positive Definite 489
9.10 Commercially Available Software 490
9.11 Exercises 491
References 496
Epilogue 496
Index 499