Full name: Monique Laurent
Formal name: Prof.dr. M. Laurent
Function: Group leader, Scientific Staff Member

Email: M.Laurent@cwi.nl
Telephone +31(0)20 592 4105
Room:  M238

Research group: (PNA1) Algorithms Combinatorics and Optimization

Monique Laurent is head of the research group Algorithms, Combinatorics and Optimization. She started her career at CWI in 1997.

How can the distribution of goods between factories and customers be planned most efficiently? What is the optimal route for the trucks? Or how to assign a minimum number of frequencies to radio stations while avoiding interference? Combinatorial optimization, the research area of Laurent, deals with this type of problems. "In many real-world problems, the number of solutions is finite," Laurent says, "yet astronomically large. Finding the optimal solution is like looking for a needle in a haystack. Our challenge is to discover a clever way to find the needle."

To do that, as Laurent explains, one first needs to understand the structure of the problem. This often involves the use of sophisticated mathematical tools. For instance, symmetry in a problem can be used to reformulate the problem in a simpler way, with fewer variables. On the other hand, embedding the problem in a larger dimensional space often helps to find better solutions. An example of this is semi-definite programming, a very successful technique that relies on replacing vectors - the natural model for a combinatorial problem - by matrices with useful algebraic properties. "The models we use are derived for instance from graph theory, discrete mathematics, geometry and algebra," she says. "A commonly used strategy is divide and conquer: smaller problems are easier to solve."

While this type of research is motivated by its many practical applications, Laurent finds most satisfaction in the fundamental challenge of designing mathematical models that lead to better and more efficient solutions. What she likes most is the interplay between different mathematical areas. "We borrow and combine tools from various disciplines," she says.  "Often you find an unexpected link between them, for instance between real algebraic geometry and optimization. An old idea of D. Hilbert of relaxing positivity by sums of squares has now become very useful for minimizing polynomial functions. The reason for this is that efficient software for semi-definite programming is now available for computing sums of squares."

The biggest challenge? Laurent smiles. "Distinguishing whether problems aresimple, or in fact difficult. Although we now have lots of evidence, there is still no formal proof that some problems are fundamentally more difficult than others. That is what makes our work so fascinating."

More about Monique Laurent:

http://homepages.cwi.nl/~monique/

collapse