4.1. Discrete Mathematics
and Optimization
Programme leader: A.
Schrijver, A.J.J. Talman
Description of the programme.
Analyzing and optimizing large and complex combinatorial structures (like
networks) with mathematical methods (algebra, geometry, topology, graph theory),
designing efficient algorithms for optimization and decision problems, and
testing and applying the results to problems from practice (logistics,
distribution, transport).
We search for new methods and techniques to
analyze large and complex networks and to design optimal subsystems (like routes,
flows, or arcs). The research focuses on decomposing large networks by treewidth,
on visualizing them by 3D embeddings using new tools based on forbidden minors
and eigenvalue methods, on designing fast methods for routing problems in
networks on surfaces based on homotopy and groups, on developing new algorithms
for assignment, scheduling and timetabling using graphs, linear programming, and
branchandcut, and on testing and applying the new techniques to practice (like
at Dutch Rail).
We also focus on solving algorithmic problems with
geometric and algebraic methods.
Combining the classical tool of linear
programming with modern techniques like interiorpoint methods (Karmarkar), basis
reduction (LenstraLenstraLovász), branchandcut,
semidefinite programming, and computer algebra (Gröbner bases), turns out
to be very powerful, both to estimate the complexity of combinatorial
and optimization problems, and to obtain efficient and practical algorithms to
solve them. The full power of these methods is still to be uncovered, but seems
potentially very high.
Part of this programme is devoted to the recent
interest in interiorpoint methods for linear and nonlinear optimization. After
the succesful polynomialtime methods of this type for linear optimization the
research now focuses on polynomialtime methods for semidefinite and other
coneoptimization problems and randomized approximation schemes for nonconvex
optimization problems. Besides this also multicriteria decision analysis and
multiobjective optimization is a field of interest.
