| Linear Equations, Inequalities, Linear Programming: A Brief Historical Overview | p. 1 |
| Mathematical Modeling, Algebra, Systems of Linear Equations, and Linear Algebra | p. 1 |
| Elimination Method for Solving Linear Equations | p. 2 |
| Review of the GJ Method for Solving Linear Equations: Revised GJ Method | p. 5 |
| GJ Method Using the Memory Matrix to Generate the Basis Inverse | p. 8 |
| The Revised GJ Method with Explicit Basis Inverse | p. 11 |
| Lack of a Method to Solve Linear Inequalities Until Modern Times | p. 14 |
| The Importance of Linear Inequality Constraints and Their Relation to Linear Programs | p. 15 |
| Fourier Elimination Method for Linear Inequalities | p. 17 |
| History of the Simplex Method for LP | p. 18 |
| The Simplex Method for Solving LPs and Linear Inequalities Viewed as an Extension of the GJ Method | p. 19 |
| Generating the Phase I Problem if No Feasible Solution Available for the Original Problem | p. 19 |
| The Importance of LP | p. 21 |
| Marginal Values and Other Planning Tools that can be Derived from the LP Model | p. 22 |
| Dantzig's Contributions to Linear Algebra, Convex Polyhedra, OR, Computer Science | p. 27 |
| Contributions to OR | p. 27 |
| Contributions to Linear Algebra and Computer Science | p. 27 |
| Contributions to the Mathematical Study of Convex Polyhedra | p. 28 |
| Interior Point Methods for LP | p. 29 |
| Newer Methods | p. 30 |
| Conclusions | p. 30 |
| How to Be a Successful Decision Maker? | p. 30 |
| Exercises | p. 31 |
| References | p. 37 |
| Formulation Techniques Involving Transformations of Variables | p. 39 |
| Operations Research: The Science of Better | p. 39 |
| Differentiable Convex and Concave Functions | p. 40 |
| Convex and Concave Functions | p. 40 |
| Piecewise Linear (PL) Functions | p. 46 |
| Convexity of PL Functions of a Single Variable | p. 47 |
| PL Convex and Concave Functions in Several Variables | p. 48 |
| Optimizing PL Functions Subject to Linear Constraints | p. 53 |
| Minimizing a Separable PL Convex Function Subject to Linear Constraints | p. 53 |
| Min-max, Max-min Problems | p. 57 |
| Minimizing Positive Linear Combinations of Absolute Values of Affine Functions | p. 59 |
| Minimizing the Maximum of the Absolute Values of Several Affine Functions | p. 61 |
| Minimizing Positive Combinations of Excesses/Shortages | p. 69 |
| Multiobjective LP Models | p. 72 |
| Practical Approaches for Handling Multiobjective LPs in Current Use | p. 74 |
| Weighted Average Technique | p. 75 |
| The Goal Programming Approach | p. 76 |
| Exercises | p. 79 |
| References | p. 124 |
| Intelligent Modeling Essential to Get Good Results | p. 127 |
| The Need for Intelligent Modeling in Real World Decision Making | p. 127 |
| Case Studies Illustrating the Need for Intelligent Modeling | p. 128 |
| Case Study 1: Application in a Container Shipping Terminal | p. 128 |
| Case Study 2: Application in a Bus Rental Company | p. 140 |
| Case Study 3: Allocating Gates to Flights at an International Airport | p. 150 |
| Murty's Three Commandments for Successful Decision Making | p. 164 |
| Exercises | p. 164 |
| References | p. 165 |
| Polyhedral Geometry | p. 167 |
| Hyperplanes, Half-Spaces, and Convex Polyhedra | p. 167 |
| Expressing a Linear Equation as a Pair of Inequalities | p. 167 |
| Straight Lines, Half-Lines, and Their Directions | p. 369 |
| Convex Combinations, Line Segments | p. 170 |
| Tight (Active)/Slack (Inactive) Constraints at a Feasible Solution x | p. 171 |
| What is the Importance of Classifying the Constraints in a System as Active/Inactive at a Feasible Solution? | p. 173 |
| Subspaces, Affine Spaces, Convex Polyhedra; Binding, Nonbinding, Redundant Inequalities; Minimal Representations | p. 174 |
| The Interior and the Boundary of a Convex Polyhedron | p. 176 |
| Supporting Hyperplanes, Faces of a Convex Polyhedron, Optimum Face for an LP | p. 177 |
| Supporting Hyperplanes | p. 177 |
| Faces of a Convex Polyhedron | p. 178 |
| Zero-Dimensional Faces, or Extreme Points, or Basic Feasible Solutions (BFSs) | p. 180 |
| Nondegenerate, Degenerate BFSs for Systems in Standard Form | p. 184 |
| Basic Vectors and Bases for a System in Standard Form | p. 185 |
| BFSs for Systems in Standard Form for Bounded Variables | p. 187 |
| Purification Routine for Deriving a BFSs from a Feasible Solution for Systems in Standard Form | p. 188 |
| The Main Strategy of the Purification Routine | p. 189 |
| General Step in the Purification Routine | p. 190 |
| Purification Routine for Systems in Symmetric Form | p. 196 |
| Edges, One-Dimensional Faces, Adjacency of Extreme Points, Extreme Directions | p. 204 |
| How to Check if a Given Feasible Solution is on an Edge | p. 205 |
| Adjacency in a Primal Simplex Pivot Step | p. 212 |
| How to Obtain All Adjacent Extreme Points of a Given Extreme Point? | p. 218 |
| Faces of Dimension ?2 of a Convex Polyhedron | p. 221 |
| Facets of a Convex Polyhedron | p. 222 |
| Optimality Criterion in the Primal Simplex Algorithm | p. 223 |
| Boundedness of Convex Polyhedra | p. 226 |
| Exercises | p. 229 |
| References | p. 233 |
| Duality Theory and Optimality Conditions for LPs | p. 235 |
| The Dual Problem | p. 235 |
| Deriving the Dual by Rational Economic Arguments | p. 236 |
| Dual Variables are Marginal Values | p. 238 |
| The Dual of the General Problem in This Form | p. 238 |
| Rules for Writing the Dual of a General LP | p. 239 |
| Complementary Pairs in a Primal, Dual Pair of LPs | p. 243 |
| What is the Importance of Complementary Pairs? | p. 242 |
| Complementary Pairs for LPs in Standard Form | p. 242 |
| Complementary Pairs for LPs in Symmetric Form | p. 244 |
| Complementary Pairs for LPs in Bounded Variable Standard Form | p. 245 |
| Duality Theory and Optimality Conditions for LP | p. 247 |
| The Importance of Good Lower Bounding Strategies in Solving Optimization Problems | p. 249 |
| Definition of the Dual Solution Corresponding to Each Primal Basic Vector for an LP in Standard Form | p. 251 |
| Properties Satisfied by the Primal and Dual Basic Solutions Corresponding to a Primal Basic Vector | p. 254 |
| The Duality Theorem of LP | p. 257 |
| Optimality Conditions for LP | p. 258 |
| Necessary and Sufficient Optimality Conditions for LP | p. 260 |
| Duality Gap, a Measure of Distance from Optimality | p. 260 |
| Using CS Conditions to Check the Optimality of a Given Feasible Solution to an LP | p. 261 |
| How Various Algorithms Solve LPs | p. 268 |
| How to Check if an Optimum Solution is Unique | p. 269 |
| Primal and Dual Degeneracy of a Basic Vector for an LP in Standard Form | p. 269 |
| Sufficient Conditions for Checking the Uniqueness of Primal and Dual Optimum Solutions | p. 271 |
| Procedure to Check if the BFS Corresponding to an Optimum Basic Vector xB is the Unique Optimum Solution | p. 272 |
| The Optimum Face for an LP | p. 275 |
| Mathematical Equivalence of LP to the Problem of Finding a Feasible Solution of a System of Linear Constraints Involving Inequalities | p. 276 |
| Marginal Values and the Dual Optimum Solution | p. 277 |
| Summary of Optimality Conditions for Continuous Variable Nonlinear Programs and Their Relation to Those for LP | p. 279 |
| Global Minimum (Maximum), Local Minimum (Maximum), and Stationary Points | p. 279 |
| Relationship to Optimality Conditions for LP Discussed Earlier | p. 284 |
| Exercises | p. 285 |
| References | p. 296 |
| Revised Simplex Variants of the Primal and Dual Simplex Methods and Sensitivity Analysis | p. 297 |
| Primal Revised Simplex Algorithm Using the Explicit Basis Inverse | p. 298 |
| A Steps in an Iteration of the Primal Simplex Algorithm When (xB,-z) is the Primal Feasible Basic Vector | p. 299 |
| Practical Consequences of Satisfying the Unboundedness Criterion | p. 306 |
| Featuresof the Simplex Algorithm | p. 307 |
| Revised Primal Simplex Method (Phase I, II) with Explicit Basis Inverse | p. 307 |
| Setting Up the Phase I Problem | p. 307 |
| How to Find a Feasible Solution to a System of Linear Constraints | p. 314 |
| Infeasibility Analysis | p. 316 |
| Practical Usefulness of the Revised Simplex Method Using Explicit Basis Inverse | p. 318 |
| Cycling in the Simplex Method | p. 319 |
| Revised Simplex Method Using the Product Form of the Inverse | p. 320 |
| Pivot Matrices | p. 320 |
| A General Iteration in the Revised Simplex Method Using the Product From of the Inverse | p. 321 |
| Transition from Phase I to Phase II | p. 322 |
| Reinversions in the Revised Simplex Method Using PFI | p. 323 |
| Revised Simplex Method Using Other Factorizations of the Basis Inverse | p. 324 |
| Finding the Optimum Face of an LP (Alternate Optimum Solutions) | p. 324 |
| The Dual Simplex Algorithm | p. 326 |
| Properties of the Dual Simplex Algorithm | p. 334 |
| Importance of the Dual Simplex Algorithm, How to Get New Optimum Efficiently When RHS Changes or New Constraints Are Added to the Model | p. 337 |
| The Dual Simplex Method | p. 342 |
| Marginal Analysis | p. 342 |
| How to Compute the Marginal Values in a General LP Model | p. 345 |
| Sensitivity Analysis | p. 347 |
| Introducing a New Nonnegative Variable | p. 347 |
| Ranging the Cost Coefficient or an I/O Coefficient in a Nonbasic Column Vector | p. 349 |
| Ranging a Basic Cost Coefficient | p. 352 |
| Ranging the RHS Constants | p. 353 |
| Features of Sensitivity Analysis Available in Commercial LP Software | p. 354 |
| Other Types of Sensitivity Analyses | p. 355 |
| Revised Primal Simplex Method for Solving Bounded Variable LP Models | p. 355 |
| The Bounded Variable Primal Simplex Algorithm | p. 358 |
| General Iteration in the Bounded Variable Primal Simplex Algorithm | p. 359 |
| The Bounded Variable Primal Simplex Method | p. 362 |
| Exercises | p. 363 |
| References | p. 392 |
| Interior Point Methods for LP | p. 393 |
| Boundary Point and Interior Point Methods | p. 393 |
| Interior Feasible Solutions | p. 394 |
| General Introduction to Interior Point Methods | p. 394 |
| Center, Analytic Center, Central Path | p. 399 |
| The Affine Scaling Method | p. 401 |
| Newton's Method for Solving Systems of Nonlinear Equations | p. 408 |
| Primal-Dual Path Following Methods | p. 409 |
| Summary of Results on the Primal-Dual IPMs | p. 414 |
| Exercises | p. 415 |
| References | p. 416 |
| Sphere Methods for LP | p. 417 |
| Introduction | p. 417 |
| Ball Centers: Geometric Concepts | p. 422 |
| Approximate Computation of Ball Centers | p. 425 |
| Approximate Computation of Ball Centers of Polyhedra | p. 425 |
| Computing an Approximate Ball Center of K on the Current Objective Plane | p. 430 |
| Ball Centers of Some Simple Special Polytopes | p. 430 |
| Sphere Method 1 | p. 431 |
| Summary of Computational Results on Sphere Method 1 | p. 435 |
| Sphere Method 2 | p. 436 |
| Improving the Performance of Sphere Methods Further | p. 439 |
| Some Open Theoretical Research Problems | p. 440 |
| Future Research Directions | p. 442 |
| Exercises | p. 442 |
| References | p. 444 |
| Quadratic Programming Models | p. 445 |
| Introduction | p. 445 |
| Superdiagonalization Algorithm for Checking PD and PSD | p. 446 |
| Classification of Quadratic Programs | p. 451 |
| Types of Solutions and Optimality Conditions | p. 452 |
| What Types of Solutions Can Be Computed Efficiently by Existing Algorithms? | p. 454 |
| Some Important Applications of QP | p. 455 |
| Unconstrained Quadratic Minimization in Classical Mathematics | p. 458 |
| Summary of Some Existing Algorithms for Constrained QPs | p. 459 |
| The Sphere Method for QP | p. 461 |
| Procedure for Getting an Approximate Solution for (9.6) | p. 462 |
| Descent Steps | p. 464 |
| The Algorithm | p. 467 |
| The Case when the Matrix D is not Positive Definite | p. 468 |
| Commercially Available Software | p. 469 |
| Exercises | p. 470 |
| References | p. 475 |
| Epilogoue | p. 477 |
| Index | p. 479 |
| Table of Contents provided by Ingram. All Rights Reserved. |
