Algebraic and Geometric Ideas in the Theory of Discrete Optimization

A textbook for students in mathematics, computer science and OR that presents new techniques in the area of discrete optimization.

Jesús A De Loera (Author), Raymond Hemmecke (Author), Matthias Koppe (Author)

9781611972436

Paperback / softback, published 30 December 2012

341 pages
25.8 x 18.4 x 2.1 cm, 0.69 kg

In recent years, many new techniques have emerged in the mathematical theory of discrete optimization that have proven to be effective in solving a number of hard problems. This book presents these recent advances, particularly those that arise from algebraic geometry, commutative algebra, convex and discrete geometry, generating functions, and other tools normally considered outside of the standard curriculum in optimization. These new techniques, all of which are presented with minimal prerequisites, provide a transition from linear to nonlinear discrete optimization. This book can be used as a textbook for advanced undergraduates or first-year graduate students in mathematics, computer science or operations research. It is also appropriate for mathematicians, engineers, and scientists engaged in computation who wish to gain a deeper understanding of how and why algorithms work.

List of figures
List of tables
List of algorithms
Preface
Part I. Established Tools of Discrete Optimization: 1. Tools from linear and convex optimization
2. Tools from the geometry of numbers and integer optimization
Part II. Graver Basis Methods: 3. Graver bases
4. Graver bases for block-structured integer programs
Part III. Generating Function Methods: 5. Introduction to generating functions
6. Decompositions of indicator functions of polyhedral
7. Barvinok's short rational generating functions
8. Global mixed-integer polynomial optimization via the summation method
9. Multicriteria integer linear optimization via Barvinok–Woods integer projection
Part IV. Gröbner Basis Methods: 10. Computations with polynomials
11. Gröbner bases in integer programming
Part V. Nullstellensatz and Positivstellensatz Relaxations: 12. The Nullstellensatz in discrete optimization
13. Positivity of polynomials and global optimization
14. Epilogue
Bibliography
Index.

Subject Areas: Miscellaneous items [WZ]