Linear Programming. Foundations and Extensions

Preface
Preface to 2nd Edition
Preface to 3rd Edition
Preface to 4th Edition
Preface to 5th Edition
Part 1.  Basic Theory: The Simplex Method and Duality
	Chapter 1. Introduction
		1. Managing a Production Facility
			1.1. Production Manager as Optimist
			1.2. Comptroller as Pessimist
		2. The Linear Programming Problem
		Exercises
		Notes
	Chapter 2. The Simplex Method
		1. An Example
			1.1. Dictionaries, Bases, Etc.
		2. The Simplex Method
		3. Initialization
		4. Unboundedness
		5. Geometry
		Exercises
		Notes
	Chapter 3. Degeneracy
		1. Definition of Degeneracy
		2. Two Examples of Degenerate Problems
		3. The Perturbation/Lexicographic Method
		4. Bland\'s Rule
		5. Fundamental Theorem of Linear Programming
		6. Geometry
		Exercises
		Notes
	Chapter 4. Efficiency of the Simplex Method
		1. Performance Measures
		2. Measuring the Size of a Problem
		3. Measuring the Effort to Solve a Problem
		4. Worst-Case Analysis of the Simplex Method
		5. Empirical Average Performance of the Simplex Method
		Exercises
		Notes
	Chapter 5. Duality Theory
		1. Motivation: Finding Upper Bounds
		2. The Dual Problem
		3. The Weak Duality Theorem
		4. The Strong Duality Theorem
		5. Complementary Slackness
		6. The Dual Simplex Method
		7. A Dual-Based Phase I Algorithm
		8. The Dual of a Problem in General Form
		9. Resource Allocation Problems
		10. Lagrangian Duality
		Exercises
		Notes
	Chapter 6. The Simplex Method in Matrix Notation
		1. Matrix Notation
		2. The Primal Simplex Method
		3. An Example
			3.1. First Iteration
			3.2. Second Iteration
			3.3. Third Iteration
			3.4. Fourth Iteration
		4. The Dual Simplex Method
		5. Two-Phase Methods
		6. Negative-Transpose Property
		Exercises
		Notes
	Chapter 7. Sensitivity and Parametric Analyses
		1. Sensitivity Analysis
			1.1. Ranging
		2. Parametric Analysis and the Homotopy Method
		3. The Parametric Self-Dual Simplex Method
		Exercises
		Notes
	Chapter 8. Implementation Issues
		1. Solving Systems of Equations: LU-Factorization
		2. Exploiting Sparsity
		3. Reusing a Factorization
		4. Performance Tradeoffs
		5. Updating a Factorization
		6. Shrinking the Bump
		7. Partial Pricing
		8. Steepest Edge
		Exercises
		Notes
	Chapter 9. Problems in General Form
		1. The Primal Simplex Method
		2. The Dual Simplex Method
		Exercises
		Notes
	Chapter 10. Convex Analysis
		1. Convex Sets
		2. Carathéodory\'s Theorem
		3. The Separation Theorem
		4. Farkas\' Lemma
		5. Strict Complementarity
		Exercises
		Notes
	Chapter 11. Game Theory
		1. Matrix Games
		2. Optimal Strategies
		3. The Minimax Theorem
		4. Poker
		Exercises
		Notes
	Chapter 12. Data Science Applications
		1. Measures of Mediocrity
		2. Multidimensional Measures: Regression Analysis
		3. L2-Regression
		4. L1-Regression
		5. Iteratively Reweighted Least Squares
		6. An Example: How Fast Is The Simplex Method?
			6.1. Random Problems
		7. Character Recognition: A Support Vector Machine
		Exercises
		Notes
	Chapter 13. Financial Applications
		1. Portfolio Selection
			1.1. Reduction to a Linear Programming Problem
			1.2. Solution via Parametric Simplex Method
		2. Option Pricing
		Exercises
		Notes
Part 2.  Network-Type Problems
	Chapter 14. Network Flow Problems
		1. Networks
		2. Spanning Trees and Bases
		3. The Primal Network Simplex Method
		4. The Dual Network Simplex Method
		5. Putting It All Together
		6. The Integrality Theorem
			6.1. König\'s Theorem
		Exercises
		Notes
	Chapter 15. Applications
		1. The Transportation Problem
		2. The Assignment Problem
		3. The Shortest-Path Problem
			3.1. Network Flow Formulation
			3.2. A Label-Correcting Algorithm
				3.2.1. Method of Successive Approximation
				3.2.2. Efficiency
			3.3. A Label-Setting Algorithm
		4. Upper-Bounded Network Flow Problems
		5. The Maximum-Flow Problem
		Exercises
		Notes
	Chapter 16. Structural Optimization
		1. An Example
		2. Incidence Matrices
		3. Stability
		4. Conservation Laws
		5. Minimum-Weight Structural Design
		6. Anchors Away
		Exercises
		Notes
Part 3.  Interior-Point Methods
	Chapter 17. The Central Path
		Warning: Nonstandard Notation Ahead
		1. The Barrier Problem
		2. Lagrange Multipliers
		3. Lagrange Multipliers Applied to the Barrier Problem
		4. Second-Order Information
		5. Existence
		Exercises
		Notes
	Chapter 18. A Path-Following Method
		1. Computing Step Directions
		2. Newton\'s Method
		3. Estimating an Appropriate Value for the Barrier Parameter
		4. Choosing the Step Length Parameter
		5. Convergence Analysis
			5.1. Measures of Progress
			5.2. Progress in One Iteration
			5.3. Stopping Rule
			5.4. Progress Over Several Iterations
		Exercises
		Notes
	Chapter 19. The KKT System
		1. The Reduced KKT System
		2. The Normal Equations
		3. Step Direction Decomposition
		Exercises
		Notes
	Chapter 20. Implementation Issues
		1. Factoring Positive Definite Matrices
			1.1. Stability
		2. Quasidefinite Matrices
			2.1. Instability
		3. Problems in General Form
		Exercises
		Notes
	Chapter 21. The Affine-Scaling Method
		1. The Steepest Ascent Direction
		2. The Projected Gradient Direction
		3. The Projected Gradient Direction with Scaling
		4. Convergence
		5. Feasibility Direction
		6. Problems in Standard Form
		Exercises
		Notes
	Chapter 22. The Homogeneous Self-Dual Method
		1. From Standard Form to Self-Dual Form
		2. Homogeneous Self-Dual Problems
			2.1. Step Directions
			2.2. Predictor–Corrector Algorithm
			2.3. Convergence Analysis
			2.4. Complexity of the Predictor–Corrector Algorithm
			2.5. The KKT System
		3. Back to Standard Form
			3.1. The Reduced KKT System
		4. Simplex Method vs Interior-Point Methods
		Exercises
		Notes
Part 4.  Extensions
	Chapter 23. Integer Programming
		1. Scheduling Problems
		2. The Traveling Salesman Problem
		3. Fixed Costs
		4. Nonlinear Objective Functions
		5. Branch-and-Bound
		6. Gomory Cuts
		Exercises
		Notes
	Chapter 24. Quadratic Programming
		1. The Markowitz Model
		2. The Dual
		3. Convexity and Complexity
		4. Solution via Interior-Point Methods
		5. Practical Considerations
		Exercises
		Notes
	Chapter 25. Convex Programming
		1. Differentiable Functions and Taylor Approximations
		2. Convex and Concave Functions
		3. Problem Formulation
		4. Solution via Interior-Point Methods
		5. Successive Quadratic Approximations
		6. Merit Functions
		7. Parting Words
		Exercises
		Notes
	Appendix A. Source Listings
		1. The Self-Dual Simplex Method
		2. The Homogeneous Self-Dual Method
	Answers to Selected Exercises
	Bibliography
	Index