HANDBOOKS IN OPERATIONS RESEARCH AND MANAGEMENT SCIENCE, 12
Discrete Optimization To order this title, and for more information, click here
Edited By K. Aardal, Centrum voor Wiskunde en Informatica, 1090 GB, Amsterdam, The Netherlands George Nemhauser, School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA R. Weismantel, Otto-von-Guericke-University of Magdeburg, 39106 Magdeburg, Germany
Description The chapters of this Handbook volume covers nine main topics that are representative of recent
theoretical and algorithmic developments
in the field. In addition to the nine papers that present the state of the art, there is an article on
the early history of the field.
The handbook will be a useful reference to experts in the field as well as students and others who want to learn about discrete optimization.
All of the chapters in this handbook are written by authors who have made significant original contributions to their topics. Herewith
a brief introduction to the chapters of the handbook.
"On the history of combinatorial optimization (until 1960)" goes back to work
of Monge in the 18th century on the assignment problem and presents six problem areas: assignment, transportation,
maximum flow, shortest
tree, shortest path and traveling salesman.
The branch-and-cut algorithm of integer programming is the computational workhorse of
discrete optimization. It provides the tools that have been implemented in commercial software such as CPLEX
and Xpress MP that make
it possible to solve practical problems in supply chain, manufacturing, telecommunications and many other areas.
"Computational integer
programming and cutting planes" presents the key ingredients
of these algorithms.
Although branch-and-cut based on linear programming
relaxation 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 better the structure of integral polyhedra. The next three chapters discuss alternative approaches.
"The structure of group relaxations" studies a family of polyhedra obtained 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" presents results in this area including algorithms that use reduced bases of integer
lattices 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 maintaining optimality to the relaxed problem. Such
algorithms have the disadvantage of
possibly obtaining feasibility only when the algorithm terminates.Primal methods for integer programs,
which move from a feasible solution to a better feasible solution, were studied in the 1960's
but did not appear to be competitive with
dual methods. However,recent development in primal methods presented in "Primal integer programming" indicate that this approach is not
just interesting theoretically but may have practical implications as well.
The study of matrices that yield integral polyhedra has
a long tradition in integer programming. A major breakthrough occurred in the 1990's 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 problems such as minimum cut and is one of the fundamental problems of the field that
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 programming provides a generalization of
linear programming
that can give better approximations and is still polynomially solvable. This subject is discussed in "Semidefinite programming and integer
programming".
Many real world problems have uncertain data that is known only probabilistically. Stochastic programming treats this
topic, but until recently it was limited, for computational reasons, to
stochastic linear programs. Stochastic integer programming is
now a high profile research area and recent developments are presented in
"Algorithms for stochastic mixed-integer programming
models".
Resource constrained scheduling is an example of a class of combinatorial optimization problems that is not naturally formulated with
linear constraints so that linear programming based methods do
not work well. "Constraint programming" presents an alternative enumerative
approach that is complementary to branch-and-cut. Constraint programming,primarily 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 variables
until their values are fixed or their domains are shown to be empty.
Audience
Operation Researchers
Contents 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 (R. R. 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, J.N. Hooker).
Books and book related electronic products are priced in US dollars (USD), euro (EUR), and Great Britain Pounds (GBP). USD prices apply to the Americas and Asia Pacific. EUR prices apply in Europe and the Middle East. GBP prices apply to the UK and all other countries.
Home | Elsevier Sites | Privacy Policy | Terms and Conditions | Feedback | Site Map | A Reed Elsevier Company