4.1. Discrete Mathematics and Optimization

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 branch-and-cut, 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 interior-point methods (Karmarkar), basis reduction (Lenstra-Lenstra-Lovász), branch-and-cut, semi-definite 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 interior-point methods for linear and non-linear optimization. After the succesful polynomial-time methods of this type for linear optimization the research now focuses on polynomial-time methods for semi-definite and other cone-optimization problems and randomized approximation schemes for non-convex optimization problems. Besides this also multi-criteria decision analysis and multi-objective optimization is a field of interest.