1st Edition

Linear Optimization and Duality A Modern Exposition

By Craig A. Tovey Copyright 2021
    586 Pages 100 B/W Illustrations
    by Chapman & Hall

    586 Pages 100 B/W Illustrations
    by Chapman & Hall

    586 Pages 100 B/W Illustrations
    by Chapman & Hall

    Linear Optimization and Dualiyy: A Modern Exposition departs from convention in significant ways. Standard linear programming textbooks present the material in the order in which it was discovered. Duality is treated as a difficult add-on after coverage of formulation, the simplex method, and polyhedral theory. Students end up without knowing duality in their bones.

    This text brings in duality in Chapter 1 and carries duality all the way through the exposition. Chapter 1 gives a general definition of duality that shows the dual aspects of a matrix as a column of rows and a row of columns. The proof of weak duality in Chapter 2 is shown via the Lagrangian, which relies on matrix duality. The first three LP formulation examples in Chapter 3 are classic primal-dual pairs including the diet problem and 2-person zero sum games.

    For many engineering students, optimization is their first immersion in rigorous mathematics. Conventional texts assume a level of mathematical sophistication they don’t have. This text embeds dozens of reading tips and hundreds of answered questions to guide such students.


    • Emphasis on duality throughout
    • Practical tips for modeling and computation
    • Coverage of computational complexity and data structures
    • Exercises and problems based on the learning theory concept of the zone of proximal


    • Guidance for the mathematically unsophisticated reader

    About the Author

    Craig A. Tovey is a professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Institute of Technology. Dr. Tovey received an AB from Harvard College, an MS in computer science and a PhD in operations research from Stanford University. His principal activities are in operations research and its interdisciplinary applications. He received a Presidential Young Investigator Award and the Jacob Wolfowitz Prize for research in heuristics. He was named an Institute Fellow at Georgia Tech, and was recognized by the ACM Special Interest Group on Electronic Commerce with the Test of Time Award. Dr. Tovey received the 2016 Golden Goose Award for his research on bee foraging behavior leading to the development of the Honey Bee Algorithm.

    What Is Linear Programming?
    Visualizing LP
    Presolving LP

    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

    Fourier-Motzkin Elimination
    Theorems of the Alternative
    Extreme Points and Optimal Solutions
    Two Ways to Represent Polyhedra

    The Simplex Method and Its Variants
    The Simplex Method
    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
    Parametric Programming

    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
    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


    Craig A. Tovey is a professor at Georgia Tech. Institute.