Linear Programming: Mathematics, Theory and Algorithms

1. Introduction and Overview.- 2. Preliminary Mathematics.- 2.1 Vectors in Rn.- 2.2 Rank and Linear Transformations.- 2.3 The Solution Set of a System of Simultaneous Linear Equations.- 2.4 Orthogonal Projections and Least Squares Solutions.- 2.5 Point-Set Theory: Topological Properties of Rn.- 2.6 Hyperplanes and Half-Planes (-Spaces).- 2.7 Convex Sets.- 2.8 Existence of Separating and Supporting Hyperplanes.- 2.9 Convex Cones.- 2.10 Basic Solutions to Linear Equalities.- 2.11 Faces of Polyhedral Convex Sets: Extreme Points, Facets, and Edges.- 2.12 Extreme Point Representation for Polyhedral Convex Sets.- 2.13 Directions for Polyhedral Convex Sets.- 2.14 Combined Extreme Point and Extreme Direction Representation for Polyhedral Convex Sets.- 2.15 Resolution of Convex Polyhedra..- 2.16 Simplexes.- 2.18 Linear Functionals.- 3. Introduction to Linear Programming.- 3.1 The Canonical Form of a Linear Programming Problem.- 3.2 A Graphical Solution to the Linear Programming Problem.- 3.3 The Standard Form of a Linear Programming Problem.- 3.4 Properties of the Feasible Region.- 3.5 Existence and Location of Finite Optimal Solutions.- 3.6 Basic Feasible and Extreme Point Solutions to the Linear Programming Problem.- 3.7 Solutions and Requirements Spaces.- 4. Duality Theory.- 4.1 The Symmetric Dual.- 4.2 Unsymmetric Duals.- 4.3 Duality Theorems.- 5. The Theory of Linear Programming.- 5.1 Finding Primal Basic Feasible Solutions.- 5.2 The Reduced Primal Problem.- 5.3 The Primal Optimality Criterion.- 5.4 Constructing the Dual Solution.- 5.5 The Primal Simplex Method.- 5.6 Degenerate Basic Feasible Solutions.- 5.7 Unbounded Solutions Reexamined.- 5.8 Multiple Optimal Solutions.- 6. Duality Theory Revisited.- 6.1 The Geometry of Duality and Optimality.- 6.2 Lagrangian Saddle Points and Primal Optimality.- 7. Computational Aspects of Linear Programming.- 7.1 The Primal Simplex Method Reexamined.- 7.2 Improving a Basic Feasible Solution.- 7.3 The Cases of Multiple Optimal, Unbounded, and Degenerate Solutions.- 7.4 Summary of the Primal Simplex Method.- 7.5 Obtaining the Optimal Dual Solution From the Optimal Primal Matrix.- 8. One-Phase, Two-Phase, and Composite Methods of Linear Programming.- 8.1 Artificial Variables.- 8.2 The One-Phase Method.- 8.3 Inconsistency and Redundancy.- 8.4 Unbounded Solutions to the Artificial Problem.- 8.5 The Two-Phase Method.- 8.6 Obtaining the Optimal Primal Solution from the Optimal Dual Matrix.- 8.7 The Composite Simplex Method.- 9. Computational Aspects of Linear Programming: Selected Transformations.- 9.1 Minimizing the Objective Function.- 9.2 Unrestricted Variables.- 9.3 Bounded Variables.- 9.4 Interval Linear Programming.- 9.5 Absolute Value Functionals.- 10. The Dual Simplex, Primal-Dual, and Complementary Pivot Methods.- 10.1 Dual Simplex Method.- 10.2 Computational Aspects of the Dual Simplex Method.- 10.3 Dual Degeneracy.- 10.4 Summary of the Dual Simplex Method.- 10.5 Generating an Initial Primal-Optimal Basic Solution: The Artificial Constraint Method.- 10.6 Primal-Dual Method.- 10.7 Summary of the Primal-Dual Method.- 10.8 A Robust Primal-Dual Algorithm.- 10.9 The Complementary Pivot Method.- 11. Postoptimality Analysis I.- 11.1 Sensitivity Analysis.- 11.2 Structural Changes.- 12. Postoptimality Analysis II.- 12.1 Parametric Analysis.- 12.2 The Primal-Dual Method Revisited.- 13. Interior Point Methods.- 13.1 Optimization Over a Sphere.- 13.2 An Overview of Karmarkar's Algorithm.- 13.3 The Projective Transformation T(X).- 13.4 The Transformed Problem.- 13.5 Potential Function Improvement andComputational Complexity.- 13.6 A Summary of Karmarkar's Algorithm.- 13.7 Transforming a General Linear Program to Karmarkar Standard Form.- 13.8 Extensions and Modifications of Karmarkar's Algorithm.- 13.9 Methods Related to Karmarkar's Routine: Affine Scaling Scaling Algorithms.- 13.10 Methods Related to Karmarkar's Routine: A Path-Following Following Algorithm.- 13.11 Methods Related to Karmarkar's Routine: Potential Reduction Algorithms.- 13.12 Methods Related to Karmarkar's Routine: A Homogeneous and Self-Dual Interior-Point, Method.- 14. Interior Point Algorithms for Solving Linear Complementarity Problems.- 14.1 Introduction.- 14.2 An Interior-Point, Path-Following Algorithm for LCP(q,M).- 14.3 An Interior-Point, Potential-Reduction Algorithm for LCP(q,M).- 14.4 A Predictor-Corrector Algorithm for Solving LCP(q,M).- 14.5 Large-Step Interior-Point Algorithms for Solving LCP(q,M).- 14.6 Related Methods for Solving LCP(q, M).- Appendix A: Updating the Basis Inverse.- Appendix B: Steepest Edge Simplex Methods.- Appendix C: Derivation of the Projection Matrix.- References.- Notation Index.