4.1. Discrete Mathematics
and Optimization Programme 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)
- Post-Docs
- 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
| 
