Linear Programming Computation

Preface to First Edition
	Acknowledgments
Preface to Second Edition
	References
Contents
About the Book
About the Author
Notation
Part I Foundations
	1 Introduction
		1.1 Error of Floating-Point Arithmetic
		1.2 From Real-Life Issue to LP Model
		1.3 Illustrative Applications
		1.4 Standard LP Problem
		1.5 Basis and Feasible Basic Solution
		References
	2 Geometry of Feasible Region
		2.1 Feasible Region as Polyhedral Convex Set
		2.2 Interior Point and Relative Interior Point
		2.3 Face, Vertex, and Extreme Direction
		2.4 Representation of Feasible Region
		2.5 Optimal Face and Optimal Vertex
		2.6 Graphic Approach
		2.7 Heuristic Characteristic of Optimal Solution
		2.8 Feasible Direction and Active Constraint
		References
	3 Simplex Method
		3.1 Simplex Algorithm: Tableau Form
		3.2 Getting Started
		3.3 Simplex Algorithm
		3.4 Degeneracy and Cycling
		3.5 Finite Pivot Rule
		3.6 Notes on Simplex Method
		References
	4 Implementation of Simplex Method
		4.1 Miscellaneous
		4.2 Scaling
		4.3 LU Factorization of Basis
		4.4 Sparse LU Factorization of Basis
		4.5 Updating LU Factors
		4.6 Crash Procedure for Initial Basis
		4.7 Harris Rule and Tolerance Expending
		4.8 Pricing for Reduced Cost
		References
	5 Duality Principle and Dual Simplex Method
		5.1 Dual LP Problem
		5.2 Duality Theorem
		5.3 Optimality Condition
		5.4 Dual Simplex Algorithm: Tableau Form
		5.5 Dual Simplex Algorithm
		5.6 Economic Interpretation of Duality: Shadow Price
		5.7 Dual Elimination
		5.8 Bilevel LP: Intercepting Optimal Set
		5.9 Notes on Duality
		References
	6 Primal-Dual Simplex Method
		6.1 Mixed Two-Phase Simplex Algorithm
		6.2 Primal-Dual Simplex Algorithm
		6.3 Self-Dual Parametric Simplex Algorithm
		6.4 Criss-Cross Algorithm Using Most-Obtuse-Angle Rule
		6.5 Perturbation Primal-Dual Simplex Algorithm
		6.6 Notes on Criss-Cross Simplex Algorithm
		References
	7 Sensitivity Analysis and Parametric LP
		7.1 Change in Cost
		7.2 Change in Right-Hand Side
		7.3 Change in Coefficient Matrix
			7.3.1 Dropping Variable
			7.3.2 Adding Variable
			7.3.3 Dropping Constraint
			7.3.4 Adding Constraint
			7.3.5 Replacing Row/Column
		7.4 Parameterizing Objective Function
		7.5 Parameterizing Right-Hand Side
	8 Generalized Simplex Method
		8.1 Generalized Simplex Algorithm
			8.1.1 Generalized Phase-I
		8.2 Generalized Dual Simplex Algorithm: Tableau Form
			8.2.1 Generalized Dual Phase-I
		8.3 Generalized Dual Simplex Algorithm
		8.4 Generalized Dual Simplex Algorithm with Bound-Flipping
		References
	9 Decomposition Method
		9.1 D-W Decomposition
			9.1.1 Starting-Up of D-W Decomposition
		9.2 Illustration of D-W Decomposition
		9.3 Economic Interpretation of D-W Decomposition
		9.4 Benders Decomposition
		9.5 Illustration of Benders Decomposition
		9.6 Dual Benders Decomposition
		References
	10 Interior-Point Method
		10.1 Karmarkar Algorithm
			10.1.1 Projective Transformation
			10.1.2 Karmarkar Algorithm
			10.1.3 Convergence
		10.2 Affine Interior-Point Algorithm
			10.2.1 Formulation of the Algorithm
			10.2.2  Convergence and Starting-Up
		10.3 Dual Affine Interior-Point Algorithm
		10.4 Path-Following Interior-Point Algorithm
			10.4.1 Primal–Dual Interior-Point Algorithm
			10.4.2 Infeasible Primal–Dual Algorithm
			10.4.3 Predictor–Corrector Primal–Dual Algorithm
			10.4.4 Homogeneous and Self-Dual Algorithm
		10.5 Notes on Interior-Point Algorithm
		References
	11 Integer Linear Programming (ILP)
		11.1 Graphic Approach
			11.1.1 Basic Idea Behind New ILP Solvers
		11.2 Cutting-Plane Method
		11.3 Branch-and-Bound Method
		11.4 Controlled-Cutting Method
		11.5 Controlled-Branch Method
			11.5.1 Depth-Oriented Strategy
			11.5.2 Breadth-Oriented Strategy
		11.6 ILP: with Reduced Simplex Framework
		References
Part II Advances
	12 Pivot Rule
		12.1 Partial Pricing
		12.2 Steepest-Edge Rule
		12.3 Approximate Steepest-Edge Rule
		12.4 Largest-Distance Rule
		12.5 Nested Rule
		12.6 Nested Largest-Distance Rule
		References
	13 Dual Pivot Rule
		13.1 Dual Steepest-Edge Rule
		13.2 Approximate Dual Steepest-Edge Rule
		13.3 Dual Largest-Distance Rule
		13.4 Dual Nested Rule
		References
	14 Simplex Phase-I Method
		14.1 Infeasibility-Sum Algorithm
		14.2 Single-Artificial-Variable Algorithm
		14.3 Perturbation of Reduced Cost
		14.4 Using Most-Obtuse-Angle Column Rule
		References
	15 Dual Simplex Phase-l Method
		15.1 Dual Infeasibility-Sum Algorithm
		15.2 Dual Single-Artificial-Variable Algorithm
		15.3 Perturbation of the Right-Hand Side
		15.4 Using Most-Obtuse-Angle Row Rule
		References
	16 Reduced Simplex Method
		16.1 Reduced Simplex Algorithm
		16.2 Dual Reduced Simplex Algorithm
			16.2.1 Dual Reduced Simplex Phase-I:Most-Obtuse-Angle
		16.3 Perturbation Reduced Simplex Algorithm
		16.4 Bisection Reduced Simplex Algorithm
		16.5 Notes on Reduced Simplex Algorithm
		References
	17 D-Reduced Simplex Method
		17.1 D-Reduced Simplex Tableau
		17.2 Dual D-Reduced Simplex Algorithm
			17.2.1 Dual D-Reduced Phase-I
		17.3 D-Reduced Simplex Algorithm
			17.3.1 D-Reduced Phase-I: Most-Obtuse-Angle Rule
		17.4 Bisection D-Reduced Simplex Algorithm
		Reference
	18 Generalized Reduced Simplex Method
		18.1 Generalized Reduced Simplex Algorithm
			18.1.1 Generalized Reduced Phase-I: Single Artificial Variable
		18.2 Generalized Dual Reduced Simplex Algorithm
			18.2.1 Generalized Dual Reduced Phase-I
		18.3 Generalized Dual D-Reduced Simplex Algorithm
	19 Deficient-Basis Method
		19.1 Concept of Deficient Basis
		19.2 Deficient-Basis Algorithm: Tableau Form
		19.3 Deficient-Basis Algorithm
			19.3.1 Computational Results
		19.4 On Implementation
			19.4.1 Initial Basis
			19.4.2 LU Updating in Rank-Increasing Iteration
			19.4.3 Phase-I: Single-Artificial-Variable
		19.5 Deficient-Basis Reduced Algorithm
			19.5.1 Phase-I: Most-Obtuse-Angle Rule
		References
	20 Dual Deficient-Basis Method
		20.1 Dual Deficient-Basis Algorithm: Tableau Form
		20.2 Dual Deficient-Basis Algorithm
		20.3 Dual Deficient-Basis D-Reduced Algorithm: Tableau Form
		20.4 Dual Deficient-Basis D-Reduced Algorithm
		20.5 Deficient-Basis D-Reduced Gradient Algorithm:Tableau Form
		20.6 Deficient-Basis D-Reduced Gradient Algorithm
		Reference
	21 Face Method with Cholesky Factorization
		21.1 Steepest Descent Direction
		21.2 Updating of Face Solution
		21.3 Face Contraction
		21.4 Optimality Test
		21.5 Face Expansion
		21.6 Face Algorithm
			21.6.1 Face Phase-I: Single-Artificial-Variable
			21.6.2 Computational Results
		21.7 Affine Face Algorithm
		21.8 Generalized Face Algorithm
		21.9 Notes on Face Method
		References
	22 Dual Face Method with Cholesky Factorization
		22.1 Steepest Ascent Direction
		22.2 Updating of Dual Face Solution
		22.3 Dual Face Contraction
		22.4 Optimality Test
		22.5 Dual Face Expansion
		22.6 Dual Face Algorithm
			22.6.1 Dual Face Phase-I
			22.6.2 Computational Results
		22.7 Dual Face Algorithm via Updating (BTB)-1
	23 Face Method with LU Factorization
		23.1 Decent Search Direction
		23.2 Updating of Face Solution
		23.3 Pivoting Operation
		23.4 Optimality Test
		23.5 Face Algorithm: Tableau Form
		23.6 Face Algorithm
		23.7 Notes on Face Method with LU Factorization
		Reference
	24 Dual Face Method with LU Factorization
		24.1 Key of Method
		24.2 Ascent Search Direction
		24.3 Updating of Dual Face Solution
		24.4 Pivoting Operation
		24.5 Optimality Test
		24.6 Dual Face Algorithm: Tableau Form
		24.7 Dual Face Algorithm
		24.8 Notes on Dual Face Method with LU Factorization
		References
	25 Simplex Interior-Point Method
		25.1 Column Pivot Rule and Search Direction
		25.2 Row Pivot Rule and Stepsize
		25.3 Optimality Condition and the Algorithm
		25.4 Computational Results
	26 Facial Interior-Point Method
		26.1 Facial Affine Face Interior-Point Algorithm
		26.2 Facial D-Reduced Interior-Point Algorithm
		26.3 Facial Affine Interior-Point Algorithm
		Reference
	27 Decomposition Principle
		27.1 New Decomposition Method
		27.2 Decomposition Principle: ``Arena Contest\'\'
		27.3 Illustration on Standard LP Problem
		27.4 Illustration on Bounded-Variable LP Problem
		27.5 Illustration on ILP Problem
		27.6 Practical Remarks
Appendix A On the Birth of LP and More
Appendix B MPS File
Appendix C Test LP Problems
Appendix D Empirical Evaluation for Nested Pivot Rules
Appendix E Empirical Evaluation for Primal and Dual Face Methods with Cholesky Factorization
Appendix F Empirical Evaluation for Simplex Interior-Point Algorithm
	References
Index