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 grouprelaxations" 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.
General
Is the information for this product incomplete, wrong or inappropriate?
Let us know about it.
Does this product have an incorrect or missing image?
Send us a new image.
Is this product missing categories?
Add more categories.
Welcome to Loot.co.za!
Sign in / Register |Wishlists & Gift Vouchers |Help | Advanced search
