| Preface | p. xiii |
| Preface to 2nd Edition | p. xvii |
| Basic Theory--The Simplex Method and Duality | p. 1 |
| Introduction | p. 3 |
| Managing a Production Facility | p. 3 |
| The Linear Programming Problem | p. 6 |
| Exercises | p. 8 |
| Notes | p. 10 |
| The Simplex Method | p. 13 |
| An Example | p. 13 |
| The Simplex Method | p. 16 |
| Initialization | p. 19 |
| Unboundedness | p. 22 |
| Geometry | p. 22 |
| Exercises | p. 24 |
| Notes | p. 27 |
| Degeneracy | p. 29 |
| Definition of Degeneracy | p. 29 |
| Two Examples of Degenerate Problems | p. 29 |
| The Perturbation/Lexicographic Method | p. 32 |
| Bland's Rule | p. 36 |
| Fundamental Theorem of Linear Programming | p. 38 |
| Geometry | p. 39 |
| Exercises | p. 42 |
| Notes | p. 43 |
| Efficiency of the Simplex Method | p. 45 |
| Performance Measures | p. 45 |
| Measuring the Size of a Problem | p. 45 |
| Measuring the Effort to Solve a Problem | p. 46 |
| Worst-Case Analysis of the Simplex Method | p. 47 |
| Exercises | p. 52 |
| Notes | p. 53 |
| Duality Theory | p. 55 |
| Motivation--Finding Upper Bounds | p. 55 |
| The Dual Problem | p. 57 |
| The Weak Duality Theorem | p. 58 |
| The Strong Duality Theorem | p. 60 |
| Complementary Slackness | p. 66 |
| The Dual Simplex Method | p. 68 |
| A Dual-Based Phase I Algorithm | p. 71 |
| The Dual of a Problem in General Form | p. 73 |
| Resource Allocation Problems | p. 74 |
| Lagrangian Duality | p. 78 |
| Exercises | p. 79 |
| Notes | p. 87 |
| The Simplex Method in Matrix Notation | p. 89 |
| Matrix Notation | p. 89 |
| The Primal Simplex Method | p. 91 |
| An Example | p. 96 |
| The Dual Simplex Method | p. 101 |
| Two-Phase Methods | p. 104 |
| Negative Transpose Property | p. 105 |
| Exercises | p. 108 |
| Notes | p. 109 |
| Sensitivity and Parametric Analyses | p. 111 |
| Sensitivity Analysis | p. 111 |
| Parametric Analysis and the Homotopy Method | p. 115 |
| The Parametric Self-Dual Simplex Method | p. 119 |
| Exercises | p. 120 |
| Notes | p. 124 |
| Implementation Issues | p. 125 |
| Solving Systems of Equations: LU-Factorization | p. 126 |
| Exploiting Sparsity | p. 130 |
| Reusing a Factorization | p. 136 |
| Performance Tradeoffs | p. 140 |
| Updating a Factorization | p. 141 |
| Shrinking the Bump | p. 145 |
| Partial Pricing | p. 146 |
| Steepest Edge | p. 147 |
| Exercises | p. 149 |
| Notes | p. 150 |
| Problems in General Form | p. 151 |
| The Primal Simplex Method | p. 151 |
| The Dual Simplex Method | p. 153 |
| Exercises | p. 159 |
| Notes | p. 160 |
| Convex Analysis | p. 161 |
| Convex Sets | p. 161 |
| Caratheodory's Theorem | p. 163 |
| The Separation Theorem | p. 165 |
| Farkas' Lemma | p. 167 |
| Strict Complementarity | p. 168 |
| Exercises | p. 170 |
| Notes | p. 171 |
| Game Theory | p. 173 |
| Matrix Games | p. 173 |
| Optimal Strategies | p. 175 |
| The Minimax Theorem | p. 177 |
| Poker | p. 181 |
| Exercises | p. 184 |
| Notes | p. 187 |
| Regression | p. 189 |
| Measures of Mediocrity | p. 189 |
| Multidimensional Measures: Regression Analysis | p. 191 |
| L[superscript 2]-Regression | p. 193 |
| L[superscript 1]-Regression | p. 195 |
| Iteratively Reweighted Least Squares | p. 196 |
| An Example: How Fast is the Simplex Method? | p. 198 |
| Which Variant of the Simplex Method is Best? | p. 202 |
| Exercises | p. 203 |
| Notes | p. 208 |
| Network-Type Problems | p. 211 |
| Network Flow Problems | p. 213 |
| Networks | p. 213 |
| Spanning Trees and Bases | p. 216 |
| The Primal Network Simplex Method | p. 221 |
| The Dual Network Simplex Method | p. 225 |
| Putting It All Together | p. 228 |
| The Integrality Theorem | p. 231 |
| Exercises | p. 232 |
| Notes | p. 240 |
| Applications | p. 241 |
| The Transportation Problem | p. 241 |
| The Assignment Problem | p. 243 |
| The Shortest-Path Problem | p. 244 |
| Upper-Bounded Network Flow Problems | p. 247 |
| The Maximum-Flow Problem | p. 250 |
| Exercises | p. 252 |
| Notes | p. 257 |
| Structural Optimization | p. 259 |
| An Example | p. 259 |
| Incidence Matrices | p. 261 |
| Stability | p. 262 |
| Conservation Laws | p. 264 |
| Minimum-Weight Structural Design | p. 267 |
| Anchors Away | p. 269 |
| Exercises | p. 272 |
| Notes | p. 272 |
| Interior-Point Methods | p. 275 |
| The Central Path | p. 277 |
| Warning: Nonstandard Notation Ahead | p. 277 |
| The Barrier Problem | p. 277 |
| Lagrange Multipliers | p. 280 |
| Lagrange Multipliers Applied to the Barrier Problem | p. 283 |
| Second-Order Information | p. 285 |
| Existence | p. 285 |
| Exercises | p. 287 |
| Notes | p. 289 |
| A Path-Following Method | p. 291 |
| Computing Step Directions | p. 291 |
| Newton's Method | p. 293 |
| Estimating an Appropriate Value for the Barrier Parameter | p. 294 |
| Choosing the Step Length Parameter | p. 295 |
| Convergence Analysis | p. 296 |
| Exercises | p. 302 |
| Notes | p. 306 |
| The KKT System | p. 307 |
| The Reduced KKT System | p. 307 |
| The Normal Equations | p. 308 |
| Step Direction Decomposition | p. 310 |
| Exercises | p. 313 |
| Notes | p. 313 |
| Implementation Issues | p. 315 |
| Factoring Positive Definite Matrices | p. 315 |
| Quasidefinite Matrices | p. 319 |
| Problems in General Form | p. 325 |
| Exercises | p. 331 |
| Notes | p. 331 |
| The Affine-Scaling Method | p. 333 |
| The Steepest Ascent Direction | p. 333 |
| The Projected Gradient Direction | p. 335 |
| The Projected Gradient Direction with Scaling | p. 337 |
| Convergence | p. 341 |
| Feasibility Direction | p. 343 |
| Problems in Standard Form | p. 344 |
| Exercises | p. 345 |
| Notes | p. 346 |
| The Homogeneous Self-Dual Method | p. 349 |
| From Standard Form to Self-Dual Form | p. 349 |
| Homogeneous Self-Dual Problems | p. 350 |
| Back to Standard Form | p. 360 |
| Simplex Method vs Interior-Point Methods | p. 363 |
| Exercises | p. 367 |
| Notes | p. 368 |
| Extensions | p. 371 |
| Integer Programming | p. 373 |
| Scheduling Problems | p. 373 |
| The Traveling Salesman Problem | p. 375 |
| Fixed Costs | p. 378 |
| Nonlinear Objective Functions | p. 378 |
| Branch-and-Bound | p. 380 |
| Exercises | p. 392 |
| Notes | p. 393 |
| Quadratic Programming | p. 395 |
| The Markowitz Model | p. 395 |
| The Dual | p. 399 |
| Convexity and Complexity | p. 402 |
| Solution Via Interior-Point Methods | p. 404 |
| Practical Considerations | p. 406 |
| Exercises | p. 409 |
| Notes | p. 411 |
| Convex Programming | p. 413 |
| Differentiable Functions and Taylor Approximations | p. 413 |
| Convex and Concave Functions | p. 414 |
| Problem Formulation | p. 414 |
| Solution Via Interior-Point Methods | p. 415 |
| Successive Quadratic Approximations | p. 417 |
| Merit Functions | p. 417 |
| Parting Words | p. 421 |
| Exercises | p. 421 |
| Notes | p. 423 |
| Source Listings | p. 425 |
| The Self-Dual Simplex Method | p. 426 |
| The Homogeneous Self-Dual Method | p. 429 |
| Answers to Selected Exercises | p. 433 |
| Bibliography | p. 435 |
| Index | p. 443 |
| Table of Contents provided by Syndetics. All Rights Reserved. |
