*Programme leaders: C. Roos, A. Schrijver*

Aim of the programme:

- The analysis of large and complex combinatorial structures (like networks)
with mathematical methods (algebra, geometry, topology, graph theory).

- The design of efficient and robust
(modelling and algorithmic) methods for optimization and decision problems, and
testing and applying the results
to problems from practice (logistics, distribution, transport, engineering).

Some results in the evaluation period:

- CWI and UvA
*Stable sets.*
D.C. Gijswijt and A. Schrijver showed that the -stable set
polyhedron of graphs not containing a bad -subdivision
is determined by the edge and odd circuit inequalities.
*Combinatorial Optimization - Polyhedra and Efficiency.*
A. Schrijver finished the book
``Combinatorial Optimization - Polyhedra and Efficiency'', which
will appear in 2003 at Springer-Verlag.
*Combinatorial Optimization - Semidefinite Relaxations.*
M. Laurent proved a linear lower bound for the number of iterations
needed for representing the cut polytope of a complete graph
as projection of semidefinite relaxations;
she gave concise semidefinite representations for the polytopes whose
vertices form a real variety associated to a radical zero-dimensional
ideal, extending results of Lasserre in the grid case, and also
proved combinatorial analogues of results of Curto and Fialkow
about flat extensions of moment matrices, with applications
to semidefinite representations of polytopes.
*Binary matroids.*
J.F. Geelen (Canada), A.M.H. Gerards, and G. Whittle (New Zealand) continued
their work towards a grid theorem for binary matroids. First they
proved, in cooperation with N. Robertson (USA), a bound on the
excluded minors for the matroids with branch-width (to appear
in *Journal on Combinatorial Theory, Series B*) and a
structural characterization for high branch-witdh in matroids
representable over fixed finite fields (a report is almost
finished). Later they proved that matroids that are representable
over a fixed finite field have large grid-minors if they have huge
branch-width. This provides (among other things) evidence for
Rota's conjecture.
*Polyhedral Combinatorics.*
A.M.H. Gerards, G. Maroti, and A. Schrijver derived very short and easy proofs
for recently
appeared results of Aguilera, Escalante, and Nasini, on the
disjunctive index of relaxations of stable set polyedra.

- TUD and EUR
*Barrier functions for convex cones.*
Jointly with A. Nemirovski and A. Ben-Tal (Technion, Haifa), Roos wrote
a paper on a generalized matrix cube problem.
A monograph (with Peng and Terlaky)
on new, so-called self-regular barrier functions for primal-dual interior
point methods was published by Princeton University Press. The research
on this subject was continued and has led to some new and interesting barrier
functions,
some of them being not self-regular but nevertheless sharing all the good
properties of self-regular barriers, and with improved complexity results when
compared
with the classical logarithmic barrier function.
*Non-convex Quadratic Optimization, Semidefinite Optimization.*
E. de Klerk, D. Pasechnik (jointly with D. Grigoriev, IRMAR, Univ. Rennes I)
proved a -upper bound for the complexity of -variate
quadratic optimization subject to (not necessarily convex) quadratic
constraints. This bound in particular implies the sharpest known
upper bound on the complexity of general semidefinite programming,
claimed without a proof by L. Khachiyan and L. Porkolab in 1997.
This result also shows that the so-called extended trust region subproblem
is polynomially solvable (thus settling an open problem).

E. de Klerk, C. Roos (jointly with M. Halicka, Comenius Univiversity, Bratislava) gave a
new characterization of the strict complementarity property for semidefinite programming in terms of the limiting behavior of the central path.
*Convex Optimization.*
J. Brinkhuis worked on unification of necessary conditions (with Tikhomirov). A
monograph on optimization theory based on these results will be
finished in 2003 and published by Princeton University Press.
The concept D-induced duality was developed (with Zhang).
*Minimax results.*
J.B.G. Frenk was able to prove that some well known minimax results for infinite
dimensional topological spaces
using only finite dimensional separation. Moreover, a chain of well known
minimax theorems starting with the famous
minimax result of von Neumann published in 1928 were derived from each other
using
very elementary properties of compact sets and lower semi-continuous functions.
Finally, some of these results were extended to the larger class of Borel
probability
measures by means of the Riesz representation theorem for the dual space of the
set of continuous functions on a compact Haussdorff space, the Banach-Alaoglu
theorem and the Fubini-Tonelli theorem.

- TUE

L. Stougie, in cooperation with others, obtained several results.
*On-line routing.*
Together with S. Krumke, D. Poensgen and W. de Paepe, M. Lipmann, X. Lu and
R. Sitters several results have been obtained. A first step
to study on-line elevator systems has been made.
Together with R. Sitters and W. de Paepe the CNN-conjecture has been proven.
This is considered one of the most important open problems in on-line
optimization.
*Minimum test set.*
Together with K.M.J. de Bontridder, B. Haldersson, M. Haldersson, C.A.J.
Hurkens, J.K.Lenstra, and R. Ravi, a problem important in medical diagnostics
and
biological identification has been studied. Both approximation results has been
obtained and exact algorithms have been designed.
*Randomized Algorithms and Counting.*
Together with M. Dyer and R. Kannan a work on fast randomized algorithms for
convex optimization has been completed. Together with M. Dyer the complexity
of stochastic programming problems has been studied. Together with
M. Dyer, M. Cryan and H. Mueller vertices of transportation polytopes have
been counted approximately using Markov Chain techniques.
*Transportation polytopes.*
A first strongly polynomial bound on the diameter of the transportation
polytope was derived. Together with J. van den Heuvel the cubic bound
was improved to a quadratic bound, which was afterwards, together with
Graham Brightwell, improved to a linear bound.

*Prizes and awards*

- On June 15, 2002, A. Schrijver received a honorary doctorate of
mathematics from the University of Waterloo in Waterloo, Ontario.

- Jiming Peng received the Stieltjes price for the best mathematical
thesis in 2001 of the Stieltjes Institute.

- H. van Maaren and M. Heule were awarded for developing the second best SAT-solver
in the category on random benchmarks at the SAT-solver Competition 2002 at
the 5th International Symposium on Theory and Applications of Satisfiability
Testing, Cincinatti.