Description |
1 online resource (xx, 803 pages) : illustrations |
Contents |
Cover -- Contents -- Part I: The Early Years -- 1 Solution of a Large-Scale Traveling-Salesman Problem -- 2 The Hungarian Method for the Assignment Problem -- 3 Integral Boundary Points of Convex Polyhedra -- 4 Outline of an Algorithm for Integer Solutions to Linear Programs and An Algorithm for the Mixed Integer Problem -- 5 An Automatic Method for Solving Discrete Programming Problems -- 6 Integer Programming: Methods, Uses, Computation -- 7 Matroid Partition -- 8 Reducibility Among Combinatorial Problems -- 9 Lagrangian Relaxation for Integer Programming -- 10 Disjunctive Programming -- Part II: From the Beginnings to the State-of-the-Art -- 11 Polyhedral Approaches to Mixed Integer Linear Programming -- 11.1 Introduction -- 11.2 Polyhedra and the fundamental theorem of integer programming -- 11.3 Union of polyhedra -- 11.4 Split disjunctions -- 11.5 Gomory8217;s mixed-integer inequalities -- 11.6 Polyhedrality of closures -- 11.7 Lift-and-project -- 11.8 Rank -- References -- 12 Fifty-Plus Years of Combinatorial Integer Programming -- 12.1 Combinatorial integer programming -- 12.2 The TSP in the 1950s -- 12.3 Proving theorems with linear-programming duality -- 12.4 Cutting-plane computation -- 12.5 Jack Edmonds, polynomial-time algorithms, and polyhedral combinatorics -- 12.6 Progress in the solution of the TSP -- 12.7 Widening the field of application in the 1980s -- 12.8 Optimization 8801; Separation -- 12.9 State of the art -- References -- 13 Reformulation and Decomposition of Integer Programs -- 13.1 Introduction -- 13.2 Polyhedra, reformulation and decomposition -- 13.3 Price or constraint decomposition -- 13.4 Resource or variable decomposition -- 13.5 Extended formulations: problem specific approaches -- 13.6 Hybrid algorithms and stronger dual bounds -- 13.7 Notes -- References -- Part III: Current Topics -- 14 Integer Programming and Algorithmic Geometry of Numbers -- 14.1 Lattices, integer programming and the geometry of numbers -- 14.2 Informal introduction to basis reduction -- 14.3 The Hermite normal form -- 14.4 Minkowski8217;s theorem -- 14.5 The LLL algorithm -- 14.6 Kannan8217;s shortest vector algorithm -- 14.7 A randomized simply exponential algorithm for shortest vector -- 14.8 Integer programming in fixed dimension -- 14.9 The integer linear optimization problem -- 14.10 Diophantine approximation and strongly polynomial algorithms -- 14.11 Parametric integer programming -- References -- 15 Nonlinear Integer Programming -- 15.1 Overview -- 15.2 Convex integer maximization -- 15.3 Convex integer minimization -- 15.4 Polynomial optimization -- 15.5 Global optimization -- 15.6 Conclusions -- References -- 16 Mixed Integer Programming Computation -- 16.1 Introduction -- 16.2 MIP evolution -- 16.3 MIP challenges -- 16.4 Conclusions -- References -- 17 Symmetry in Integer Linear Programming -- 17.1 Introduction -- 17.2 Preliminaries -- 17.3 Detecting symmetries -- 17.4 Perturbation -- 17.5 Fixing variables -- 17.6 Symmetric polyhedra and related topics -- 17.7 Partitioning problems -- 17.8 Symmetry breaking inequalities -- 17.9 Pruning the enumeration tree -- 17.10 Group representation and operations -- 17.11 Enumerating all non-isomorphic solutions -- 17.12 Furthering the reach of isomorphism pruning -- 17.13 Choice of f |
Summary |
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, Gérard Cornuéjols, 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 Köppe, 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 |
Notes |
Selected conference papers |
Bibliography |
Includes bibliographical references and index |
Notes |
Print version record |
Subject |
Integer programming -- Congresses
|
|
Combinatorial optimization -- Congresses
|
|
Combinatorial optimization
|
|
Integer programming
|
Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
Form |
Electronic book
|
Author |
Jünger, M. (Michael)
|
ISBN |
9783540682790 |
|
3540682791 |
|