1st Edition

Linear Optimization and Duality A Modern Exposition

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

Also available as eBook on:

Taylor & Francis eBooks
(Institutional Purchase)Opens in new tab or window

Description

Linear Optimization and Duality: 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... Read more

Linear Optimization and Duality: 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.

Features

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 development

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.

Read less

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