Handbooks in Operations Research and Management Science

The handbook will be able to learn about discrete optimization.

All of the chapters in this handbook are written by the authors. Herewith a brief introduction to the chapters of the handbook.

'On the history of combinatorial optimization (until 1960)' goes on to assume the problem of assignment,
maximum flow, shortest tree, shortest path and traveling salesman.

The branch-and-cut algorithm of integrative programming is the computational workhorse of discrete optimization. It provides the CPLEX
and Xpress MP that make it possible to solve the problem of supply chain, manufacturing, telecommunications and many other areas.
"Computational integer programming and cutting plans" presents the key ingredients
of these algorithms.

Still, the branch-and-cut based on linear programming is the most widely used integer programming algorithm, other approaches are
needed to solve instances for which branch-and-cut performs poorly and to understand the structure of integral polyhedra. The next three chapters discuss alternative approaches.

"The structure of group relaxations" a family of polyhedra completed by dropping certain
nonnegativity restrictions on integer programming problems.

Although integer programming is NP-hard in general, it is polynomially solvable in fixed dimension. "Integer programming, lattices, and results in fixed dimension". Integer programs that are capable of solving certain classes of integer programs that defy solution by branch-and-cut.

Relaxation or dual methods, such as cutting plane algorithms, progressively remove infeasibility while I am optimized to the relaxed problem. Such algorithms have the disadvantage of
possibly obtaining feasibility only when the algorithm terminates.Primal methods for integer programs, which was moved from a feasible solution to a better solution, were studied in the 1960's
but did not appear to be competitive with dual methods. However, recent development in the primal method presented in "Primal integer programming".

The study of matrices that yield integral polyhedra has a long tradition in integer programming. A major breakthrough occurred in the 1990s with the development of polyhedral and structural results
and recognition algorithms for balanced matrices. "Balanced matrices" is a tutorial on the
subject.

Submodular function minimization generalizes some linear combinatorial optimization as it is solvable in polynomial
time. "Submodular function minimization" presents the theory and algorithms of this subject.

In the search for tighter relaxations of combinatorial optimization problems, semidefinite; and a generalization of
linear programming that give better approximations and is still polynomially solvable. This subject is discussed in "Semidefinite programming and integer programming".

Many real world problems have probabilistically. Stochastic programming treats this topic,
stochastic linear programs. Stochastic integer programming is now a high profile research and development area
"Algorithms for stochastic mixed-integer programming
models ".

Resource constrained scheduling is an example of a class of combinatorial optimization problems.
not work well. "Constraint programming" presents an alternative enumerative approach that is complementary to branch-and-cut. Constraint programming, designed for feasibility problems, does not use a relaxation to obtain bounds. Instead nodes of the search tree are
pruned by constraint propagation, which tightens bounds on a variable.

1. On the History of Combinatorial Optimization (till 1960) (A. Schrijver). 2. Computational Integer Programming and Cutting Planes (A. Fügenschuh, A. Martin). 3. The Structure of Group Relaxations (RR Thomas). 4. Integer programming, lattices, and results in fixed dimension (K. Aardal, F. Eisenbrand). 5. Primal Integer Programming (B. Spille, R. Weismantel). 6. Balanced Matrices (G. Cornuéjols, M. Conforti). 7. Submodular Function Minimization (T. McCormick). 8. Semidefinite Programming and Integer Programming (M. Laurent, F. Rendl). 9. Algorithms for Stochastic Mixed-Integer Programming Models (S. Sen). 10. Constraint Programming (A. Bockmayr, JN Hooker).