Linear Programming: Foundations and Extensions

Preface......Page 7
Preface to 2nd Edition......Page 11
Preface to 3rd Edition......Page 13
Preface to 4th Edition......Page 14
Preface to 5th Edition......Page 15
Part 1.  Basic Theory: The Simplex Method and Duality......Page 23
   1.1. Production Manager as Optimist......Page 25
   1.2. Comptroller as Pessimist......Page 26
  2. The Linear Programming Problem......Page 28
  Exercises......Page 30
  Notes......Page 32
  1. An Example......Page 33
  2. The Simplex Method......Page 36
  3. Initialization......Page 39
  4. Unboundedness......Page 41
  5. Geometry......Page 42
  Exercises......Page 43
  Notes......Page 47
  2. Two Examples of Degenerate Problems......Page 48
  3. The Perturbation/Lexicographic Method......Page 52
  4. Bland\'s Rule......Page 55
  5. Fundamental Theorem of Linear Programming......Page 57
  6. Geometry......Page 58
  Exercises......Page 61
  Notes......Page 62
  1. Performance Measures......Page 64
  3. Measuring the Effort to Solve a Problem......Page 65
  4. Worst-Case Analysis of the Simplex Method......Page 66
  5. Empirical Average Performance of the Simplex Method......Page 71
  Exercises......Page 76
  Notes......Page 79
  1. Motivation: Finding Upper Bounds......Page 80
  2. The Dual Problem......Page 81
  3. The Weak Duality Theorem......Page 82
  4. The Strong Duality Theorem......Page 84
  5. Complementary Slackness......Page 90
  6. The Dual Simplex Method......Page 92
  7. A Dual-Based Phase I Algorithm......Page 94
  8. The Dual of a Problem in General Form......Page 96
  9. Resource Allocation Problems......Page 98
  10. Lagrangian Duality......Page 101
  Exercises......Page 102
  Notes......Page 109
  1. Matrix Notation......Page 110
  2. The Primal Simplex Method......Page 112
  3. An Example......Page 116
   3.1. First Iteration......Page 117
   3.2. Second Iteration......Page 118
   3.3. Third Iteration......Page 119
  4. The Dual Simplex Method......Page 121
  5. Two-Phase Methods......Page 123
  6. Negative-Transpose Property......Page 125
  Exercises......Page 127
  Notes......Page 129
  1. Sensitivity Analysis......Page 130
   1.1. Ranging......Page 131
  2. Parametric Analysis and the Homotopy Method......Page 134
  3. The Parametric Self-Dual Simplex Method......Page 137
  Exercises......Page 139
  Notes......Page 142
 Chapter 8. Implementation Issues......Page 143
  1. Solving Systems of Equations: LU-Factorization......Page 144
  2. Exploiting Sparsity......Page 147
  3. Reusing a Factorization......Page 153
  4. Performance Tradeoffs......Page 156
  5. Updating a Factorization......Page 158
  6. Shrinking the Bump......Page 161
  7. Partial Pricing......Page 163
  8. Steepest Edge......Page 164
  Exercises......Page 165
  Notes......Page 167
  1. The Primal Simplex Method......Page 168
  2. The Dual Simplex Method......Page 171
  Notes......Page 177
  1. Convex Sets......Page 178
  2. Carathéodory\'s Theorem......Page 181
  3. The Separation Theorem......Page 182
  4. Farkas\' Lemma......Page 184
  5. Strict Complementarity......Page 185
  Exercises......Page 187
  Notes......Page 188
  1. Matrix Games......Page 189
  2. Optimal Strategies......Page 191
  3. The Minimax Theorem......Page 193
  4. Poker......Page 196
  Exercises......Page 201
  Notes......Page 203
  1. Measures of Mediocrity......Page 204
  2. Multidimensional Measures: Regression Analysis......Page 206
  3. L2-Regression......Page 208
  4. L1-Regression......Page 210
  5. Iteratively Reweighted Least Squares......Page 211
  6. An Example: How Fast Is The Simplex Method?......Page 212
   6.1. Random Problems......Page 216
  7. Character Recognition: A Support Vector Machine......Page 218
  Exercises......Page 224
  Notes......Page 230
  1. Portfolio Selection......Page 231
   1.2. Solution via Parametric Simplex Method......Page 234
  2. Option Pricing......Page 236
  Exercises......Page 241
  Notes......Page 242
Part 2.  Network-Type Problems......Page 243
  1. Networks......Page 245
  2. Spanning Trees and Bases......Page 248
  3. The Primal Network Simplex Method......Page 253
  4. The Dual Network Simplex Method......Page 257
  5. Putting It All Together......Page 261
  6. The Integrality Theorem......Page 263
  Exercises......Page 264
  Notes......Page 272
  1. The Transportation Problem......Page 273
  2. The Assignment Problem......Page 275
  3. The Shortest-Path Problem......Page 276
   3.2. A Label-Correcting Algorithm......Page 277
   3.3. A Label-Setting Algorithm......Page 278
  4. Upper-Bounded Network Flow Problems......Page 279
  5. The Maximum-Flow Problem......Page 282
  Exercises......Page 284
  Notes......Page 289
  1. An Example......Page 290
  2. Incidence Matrices......Page 292
  3. Stability......Page 294
  4. Conservation Laws......Page 295
  5. Minimum-Weight Structural Design......Page 299
  6. Anchors Away......Page 300
  Exercises......Page 302
  Notes......Page 304
Part 3.  Interior-Point Methods......Page 307
  1. The Barrier Problem......Page 309
  2. Lagrange Multipliers......Page 312
  3. Lagrange Multipliers Applied to the Barrier Problem......Page 315
  5. Existence......Page 317
  Exercises......Page 319
  Notes......Page 321
  1. Computing Step Directions......Page 322
  2. Newton\'s Method......Page 324
  3. Estimating an Appropriate Value for the Barrier Parameter......Page 325
  4. Choosing the Step Length Parameter......Page 326
  5. Convergence Analysis......Page 327
   5.2. Progress in One Iteration......Page 328
   5.4. Progress Over Several Iterations......Page 331
  Exercises......Page 333
  Notes......Page 337
  1. The Reduced KKT System......Page 338
  2. The Normal Equations......Page 339
  3. Step Direction Decomposition......Page 341
  Notes......Page 344
  1. Factoring Positive Definite Matrices......Page 345
   1.1. Stability......Page 348
  2. Quasidefinite Matrices......Page 349
   2.1. Instability......Page 352
  3. Problems in General Form......Page 355
  Notes......Page 360
  1. The Steepest Ascent Direction......Page 362
  2. The Projected Gradient Direction......Page 364
  3. The Projected Gradient Direction with Scaling......Page 366
  4. Convergence......Page 370
  5. Feasibility Direction......Page 371
  6. Problems in Standard Form......Page 373
  Exercises......Page 374
  Notes......Page 375
  1. From Standard Form to Self-Dual Form......Page 376
  2. Homogeneous Self-Dual Problems......Page 377
   2.1. Step Directions......Page 379
   2.2. Predictor–Corrector Algorithm......Page 381
   2.3. Convergence Analysis......Page 384
   2.4. Complexity of the Predictor–Corrector Algorithm......Page 386
  3. Back to Standard Form......Page 387
   3.1. The Reduced KKT System......Page 388
  4. Simplex Method vs Interior-Point Methods......Page 390
  Exercises......Page 394
  Notes......Page 395
Part 4.  Extensions......Page 397
  1. Scheduling Problems......Page 399
  2. The Traveling Salesman Problem......Page 401
  4. Nonlinear Objective Functions......Page 404
  5. Branch-and-Bound......Page 406
  6. Gomory Cuts......Page 418
  Exercises......Page 423
  Notes......Page 424
  1. The Markowitz Model......Page 425
  2. The Dual......Page 430
  3. Convexity and Complexity......Page 432
  4. Solution via Interior-Point Methods......Page 436
  5. Practical Considerations......Page 437
  Exercises......Page 440
  Notes......Page 441
  1. Differentiable Functions and Taylor Approximations......Page 442
  3. Problem Formulation......Page 443
  4. Solution via Interior-Point Methods......Page 444
  6. Merit Functions......Page 446
  Exercises......Page 450
  Notes......Page 452
 Appendix A. Source Listings......Page 453
  1. The Self-Dual Simplex Method......Page 454
  2. The Homogeneous Self-Dual Method......Page 457
 Answers to Selected Exercises......Page 460
 Bibliography......Page 463
 Index......Page 471