50 Years of Integer Programming 1958-2008

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.