Optimization over Integers
Optimization over Integers
by Dimitris Bertsimas and Robert Weismantel
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 book is used in the PhD level class Integer and Combinatorial Optimization at the Massachusetts Institute of Technology.
Distinguishing Characteristics
- 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 basis methods
- 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 methods - Provides a unified treatment of mixed integer and robust discrete optimization
- Includes a large number of examples and exercises developed through extensive classroom use
This book consists of four parts:
- Part 1: Formulations and Relaxations
- Part 2: Algebra and Geometry of Integer Optimization
- Part 3: Algorithms for Integer Optimization
- Part 4: Extensions of Integer Optimization
Resources
Cplex formulations and the data for the hands-on exercises organized by chapter for the book. Click here to initiate download.
For Instructors
Solution manual available to qualified instructors upon request. A solution manual is available to qualified instructors upon request. An instructor resource form with solutions to the exercises will be provided upon request. Please fill out the form in the "For Instructors" section under Resources.