Linear Programming with Duals: A Modern Exposition.pdf
This textbook presents a theoretical treatment of linear programming, network flows and applications, integer programming, and computational complexity. The author includes a rigorous discussion of theory, numerous examples and exercises, and geometric intuitive explanations. He also offers computational tips and interpretation of software input. Unlike other books, this text incorporates duality throughout its chapters, rather than treating it as an add-on topic. It also discusses computational complexity theory, which can be used to classify problems according to the appropriate solution method.
Introduction Notation What Is Linear Programming? Visualizing LP Presolving LP Problems Formulating and Solving Linear Programs Three Classic Primal/Dual Formulation Pairs LP Modeling Methods More Examples of LP Formulation Using Software to Solve LPs Dual Variables as Shadow Prices Problems Polyhedra Separation Fourier-Motzkin Elimination Theorems of the Alternative Extreme Points and Optimal Solutions Two Ways to Represent Polyhedra Problems The Simplex Method and Its Variants The Simplex Method Complications Variants High Level Computational Issues The Geography of Mount Duality Variants of Farkas's Lemma and of Strong Duality To and From Helly's Theorem Other Walking Trails on the TV Mountain Sensitivity Analysis and Other Predictions The Mathematical Justification of Shadow Prices Sensitivity Analysis Column Generation Degeneracy Parametric Programming Networks Network Models Network Simplex Method Dijkstra's Algorithm for Shortest Paths Max Flow Min Cut Algorithms Hungarian Algorithm for Assignment as Primal-Dual Method Integrality and Duality Logarithmic Barrier and Other Interior-Point Methods Column Geometry of Simplex and Affine Scaling Algorithms Logarithmic Barrier and the Central Path Sparseness and Factorization Degeneracy, Crossover, and Other Considerations Advanced Topics on Polyhedra Polarity Separation Characterization of Convexity Polyhedral Cones Facets of Polyhedra Formulating and Solving Integer Programs Examples of IP Formulation Tighter Formulations Solving IPs Computational Complexity Introduction Complexity, and NP-Hardness The Straight Dope: Theory and Practice YES/NO Form The Nuts and Bolts of NP-Hardness Proofs Spotting Complexity Illustrations of Common Pitfalls Examples of NP-Hardness Proofs Dealing with NP-Hard Problems Other Complexity Classifications Conclusions and Recommended Reading Answers to Questions