4.1. Discrete Mathematics and OptimizationProgramme leader: C. Roos, A. Schrijver
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.
Status of the programme.
Important problems in engineering and system theory can be modelled as specially structured optimization problems over convex cones (like the semi-definite cone and the ice-cream cone). These problems admit an elegant duality theory and can be efficiently solved by interior point methods.
One of the main aims of the project is to find new search directions for interior point methods and to provide a thorough mathematical analysis of the proposed methods.
On the other hand, some important non-convex optimization problems admit natural relaxations of this type and therefore can be approximately solved with efficient randomization and derandomization schemes.
The research is supported by several grants of NWO and the European Community.
In the ``Training and Mobility of Researchers'' programme ``Discrete Optimization Network'' of the EC, we cooperate with the universities of Bonn, Oxford, London, Paris, Louvain-la-Neuve, and Rome.
In one of the NWO-projects (a ``Groot Project''), research groups from EUR, UU, TUE, en TUD cooperate.
Furthermore we cooperate with research groups at Haifa, Geneva,Würzburg, Graz, Coimbra, Atlanta, Iowa, Stanford, Los Angeles, Tokyo, Tsukuba, Beying, Nanjing, Yale University, IBM Research, Waterloo (Canada), Bell Communications Research, Houston, and Budapest.
Research staff (situation at January 1, 2007)
- Permanent staff
- Dr.ir. F.D. Barb (EUR)
- Prof.dr. P.E.M. Borm (UvT)
- Dr. J. Brinkhuis (EUR)
- Dr.ir. E.R. van Dam (UvT)
- Dr. A.M.B. De Waegenaere (UvT)
- Dr. J.G.B. Frenk (EUR)
- Prof.dr.ir. A.M.H. Gerards (TUE/CWI)
- Dr.ir. W.H. Haemers (UvT)
- Prof.dr. D. den Hertog (UvT)
- Dr. E. de Klerk (UvT)
- Dr. H. van Maaren (TUD)
- Dr. H.M. Mulder (EUR)
- Dr.ir.ing M.J.P. Peeters (UvT)
- Prof.dr.ir. C. Roos (TUD)
- Prof.dr. P.H.M. Ruys (UvT)
- Prof.dr. A. Schrijver (UvA/CWI)
- Dr. L. Stougie (TUE/CWI)
- Prof.dr. A.J.J. Talman (UvT)
- Prof.dr. S.H. Tijs (UvT)
- Dr. M. Voorneveld (UvT)
- Dr. R.L.P. Hendrickx (UvT-NWO)
- Dr. D.C. Gijswijt (UvA)
- Dr. R. Sotirov (UvT-NWO)
- Ph. D. students
- Drs. J. Byrka (TUE/CWI)
- Drs. C. Dobre (UvT)
- G. Elabwabi Msc (TUD)
- Drs. N. Gvozdenović (UvA/CWI)
- Drs. I. Ivanov (TUD)
- Drs. E.J. van Leeuwen (UvA/CWI)
- Ir. A.Y.D. Siem (UvT)
- Drs. M. Vieira (TUD)
- CWI participants
- Dr.ir. K.I. Aardal
- Dr. S. Kelk
- Dr. M. Laurent
- Prof.dr. J.K. Lenstra