Optimization Over Integers
by Dimitris Bertsimas and Robert Weismantel
Dynamic Ideas, Belmont, Massachusetts, May, 2005.
The purpose of this book is to provide a unified, insightful, and modern treatment of the theory of integer optimization with an eye towards the
future. We have selected those topics that we feel have influenced the current state of the art and most importantly we feel will affect the future of the field. We depart from earlier treatments of integer optimization by placing significant emphasis on strong formulations, duality, algebra and most importantly geometry.
The chapters of the book are logically organized in four parts:
Part I: Formulations and relaxations includes Chapters 1–5 and discusses how to formulate integer optimization problems, how to enhance the formulations to improve the quality of relaxations, how to obtain ideal formulations, the duality of integer optimization and how to solve the resulting relaxations both practically and theoretically.
Part II: Algebra and geometry of integer optimization includes Chapters 6–8 and
develops the theory of lattices, oulines ideas from algebraic geometry that have had an impact on integer optimization, and most importantly discusses the geometry of integer optimization, a key feature of the book. These chapters provide the building blocks for developing algorithms.
Part III: Algorithms for integer optimization
includes Chapters 9–12 and develops cutting plane methods, integral basis methods, enumerative and
heuristic methods and approximation algorithms. The key characteristic of our treatment is that
our development of the algorithms is naturally based on the algebraic and geometric developments of Part II.
Part IV: Extensions of integer optimization
includes Chapters 13 and 14, and treats mixed integer optimization and robust discrete optimization. Both areas are
practically significant as real world problems have very often both continuous and discrete variables and have
elements of uncertainty that need to be addressed in a tractable manner.
Distinguishing Characteristics Of This Book:
- Develops the theory of integer optimization from a new geometric
perspective via integral generating sets
- Emphasizes strong formulations, ways to improve them, integral
polyhedra, duality, and relaxations
- Discusses applications of lattices and algebraic geometry to integer
optimization, including Gröbner bases, optimization over
polynomials and counting integer points in polyhedra
- Contains a unified geometric treatment of cutting plane and integral
- Covers enumerative and heuristic methods, including local search
over exponential neighborhoods and simulated annealing
- Presents the major methods to construct approximation algorithms:
primal-dual, randomized rounding, semidefinite and enumerative
- Provides a unified treatment of mixed integer and robust discrete
- Includes a large number of examples and exercises developed
through extensive classroom use
Download Cplex formulations and the data for the hands-on exercises organized by chapter for the book. You may click the button to initiate a file download of this material.
Dimitris Bertsimas is the Boeing Professor of Operations
Research at the Massachusetts Institute of Technology and
Robert Weismantel is the head of the
Institute for Operations Research, ETH Zurich, Switzerland.