In 1958, Ralph E. Gomory transformed the field of integer programming when he published a short paper that described his cutting-plane algorithm for pure integer programs and announced that the method could be refined to give a finite algorithm for integer programming. In January of 2008, to commemorate the anniversary of Gomory`s seminal paper, a special session celebrating fifty years of integer programming was held in Aussois, France, as part of the 12th Combinatorial Optimization Workshop. This book is based on the material presented during this session.

50 Years of Integer Programming offers an account of featured talks at the 2008 Aussois workshop, namely

- Michele Conforti, Grard Cornujols, and Giacomo Zambelli: Polyhedral Approaches to Mixed Integer Linear Programming

- William Cook: 50+ Years of Combinatorial Integer Programming

- Francois Vanderbeck and Laurence A. Wolsey: Reformulation and Decomposition of Integer Programs

The book contains reprints of key historical articles together with new introductions and historical perspectives by the authors: Egon Balas, Michel Balinski, Jack Edmonds, Ralph E. Gomory, Arthur M. Geoffrion, Alan J. Hoffman & Joseph B. Kruskal, Richard M. Karp, Harold W. Kuhn, and Ailsa H. Land & Alison G. Doig.

It also contains written versions of survey lectures on six of the hottest topics in the field by distinguished members of the integer programming community:

- Friedrich Eisenbrand: Integer Programming and Algorithmic Geometry of Numbers

- Raymond Hemmecke, Matthias Kppe, Jon Lee, and Robert Weismantel: Nonlinear Integer Programming

- Andrea Lodi: Mixed Integer Programming Computation

- Francois Margot: Symmetry in Integer Linear Programming

- Franz Rendl: Semidefinite Relaxations for Integer Programming

- Jean-Philippe P. Richard and Santanu S. Dey: The Group-Theoretic Approach to Mixed Integer Programming

Integer programming holds great promise for the future, and continues to build on its foundations. Indeed, Gomory`s finite cutting-plane method for the pure integer case is currently being reexamined and is showing new promise as a practical computational method. This book is a uniquely useful celebration of the past, present and future of this important and active field. Ideal for students and researchers in mathematics, computer science and operations research, it exposes mathematical optimization, in particular integer programming and combinatorial optimization, to a broad audience.

Front Matter....Pages 1-6

Solution of a Large-Scale Traveling-Salesman Problem....Pages 7-28

The Hungarian Method for the Assignment Problem....Pages 29-47

Integral Boundary Points of Convex Polyhedra....Pages 49-76

Outline of an Algorithm for Integer Solutions to Linear Programs and An Algorithm for the Mixed Integer Problem....Pages 77-103

An Automatic Method for Solving Discrete Programming Problems....Pages 105-132

Integer Programming: Methods, Uses, Computation....Pages 133-197

Matroid Partition....Pages 199-217

Reducibility Among Combinatorial Problems....Pages 219-241

Lagrangian Relaxation for Integer Programming....Pages 243-281

Disjunctive Programming....Pages 283-340

Front Matter....Pages 341-342

Polyhedral Approaches to Mixed Integer Linear Programming....Pages 343-385

Fifty-Plus Years of Combinatorial Integer Programming....Pages 387-430

Reformulation and Decomposition of Integer Programs....Pages 431-502

Front Matter....Pages 503-504

Integer Programming and Algorithmic Geometry of Numbers....Pages 505-559

Nonlinear Integer Programming....Pages 561-618

Mixed Integer Programming Computation....Pages 619-645

Symmetry in Integer Linear Programming....Pages 647-686

Semidefinite Relaxations for Integer Programming....Pages 687-726

The Group-Theoretic Approach in Mixed Integer Programming....Pages 727-801

Back Matter....Pages 1-2

- Author: Vaek Chvtal, William Cook, George B. Dantzig, Delbert R. Fulkerson, Selmer M. Johnson (auth.), Michael Jnger, Thomas M. Liebling, Denis Naddef, George L. Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, Laurence A. Wolsey (eds.)
- Edition: 1
- Publication Date: 2010
- Publisher: Springer-Verlag Berlin Heidelberg
- ISBN-10: 3540682740
- ISBN-13: 9783540682745
- Pages: 811
- Format: pdf
- Size: 5.6M