Je leest:

Spinozaprijs voor Alexander Schrijver

Spinozaprijs voor Alexander Schrijver

Professor Alexander Schrijver ontvangt de prestigieuze prijs, die ook wel de Nederlandse Nobelprijs wordt genoemd, voor zijn voortreffelijke, baanbrekende en inspirerende onderzoek op het gebied van combinatoriek en algoritmiek.

Prof. dr. Alexander Schrijver is een van de winnaars van de Spinozapremie 2005. Dit werd vanochtend bekend gemaakt door de Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO). Schrijver (1948) is onderzoeker aan het Centrum voor Wiskunde en Informatica te Amsterdam. Daarnaast is hij als deeltijdhoogleraar verbonden aan de Universiteit van Amsterdam. Hij ontvangt de prestigieuze prijs, die ook wel de ‘Nederlandse Nobelprijs’ wordt genoemd, voor zijn voortreffelijke, baanbrekende en inspirerende onderzoek op het gebied van combinatoriek en algoritmiek.

De Spinozapremie is de grootste onderscheiding in de wetenschap in Nederland en bestaat uit een bedrag van anderhalf miljoen euro – te besteden aan onderzoek naar keuze – en een beeldje van Spinoza. De officiële uitreiking van het geldbedrag en het beeldje aan Schrijver en drie andere laureaten vindt plaats op woensdag 23 november 2005.

Prof. dr. Alexander Schrijver, een van de Spinoza-prijswinnaars 2005. bron: NWO, Paul Wapenaar

Slimme algoritmen voor complexe vragen

De huidige technologische samenleving stelt door de ontwikkeling van computer en digitale communicatie meer en meer vragen van combinatorische en algoritmische aard: hoe verdeel ik frequenties over zendmasten voor mobiele telefonie, hoe rooster ik treinen zó in, dat er voldoende zitplaatsen zijn en hoe laat ik de verbindingen op een elektronische chip lopen?

De oplossing van dit soort vraagstukken bestaat steeds uit het maken van een keuze uit een zeer groot aantal mogelijkheden. Stuk voor stuk nalopen is niet haalbaar en dus zijn er slimme reken- en volgorde-methoden nodig. Dat is waar de combinatoriek en de algoritmiek zich mee bezighoudt en dat is het vakgebied waarin Lex Schrijver al ruim 25 jaar in uitblinkt, in het bijzonder de combinatorische optimalisering (de combinatie van algoritmiek en combinatoriek), de polyedrale combinatoriek en netwerkentheorie. Dit vakgebied verbindt de wiskunde met de informatica en speelt zich af op een zeer fundamenteel niveau.Toch kan het tot zeer praktische toepassingen leiden.

Roosterprobleem: zet in elk wit hokje een 1, 2, 3, 4, 5 of 6, maar zet niet hetzelfde cijfer tweemaal in dezelfde rij of kolom. Kan dit? In dit probleem stellen de rijen bijvoorbeeld de klassen 1 t/m 10 voor, en de kolommen de docenten A t/m J. Een wit hokje in positie B3 geeft aan dat docent B aan klas 3 een les gaat geven. Het cijfer in het hokje geeft aan in welk lesuur die les valt. Schrijver vond een algemene oplossing in 12 n stappen, waarbij er n docenten en n klassen zijn. Ook algemenere problemen zijn met zijn methode op te lossen: zoals een school met meer lesuren – of het benaderen van Ising’s constante uit de vaste-stof scheikunde!

Koplopers

Een voorbeeld van een toepassing is de recente oplossing van een ogenschijnlijk eenvoudig probleem van de Nederlandse Spoorwegen, waarover Schrijver zich jarenlang het hoofd heeft gebroken. De NS gebruikt treinen van het type koploper, waarvan sommige drie rijtuigen hebben en andere vier. Daar zit hem het probleem, want daardoor is het moeilijk de omloop van de treinen zo te roosteren, dat er op gewenste tijden voldoende zitplaatsen zijn. Het heeft geen zin de trein voor de helft uit ‘drietjes’ en de andere helft uit ‘viertjes’ te laten bestaan, ‘want’, legt Schrijver uit ‘aan het eind van een trein koppelen ze af en aan het begin worden rijtuigen toegevoegd. Bovendien worden op sommige stations treinen gesplitst of juist samengevoegd. Dit maakt het tot een heel lastig combinatorisch probleem. Naarmate het probleem onoplosbaarder lijkt,’ aldus Schrijver, ‘ben je meer geneigd er moeilijker modellen op los te laten en het is leuk als je dan uiteindelijk een oplossing vindt.’

Elegantie

Eén van Schrijvers verdiensten is dat hij boeken heeft geschreven ‘waar iedereen op zat te wachten’, zoals een collega het formuleert, en waardoor een gebied dat 25 jaar geleden nog een collectie prachtige, maar vaak op zichzelf staande problemen en resultaten vormde, tot een vakdiscipline werd gesmeed. Van wereldniveau is het driedelige standaardwerk Combinatorial Optimization – Polyhedra and Efficiency (2003), waarvoor hij persoonlijk bij uitgever Springer bedong dat het betaalbaar zou zijn en waarvoor hij de Lanchester Prize won. Zijn vakgenoten roemen zijn diepgaandheid en de elegantie van zijn presentatie. Zij zijn unaniem van mening dat het een monumentaal werk is, dat de komende decennia een gids zal zijn voor alle jonge onderzoekers over de hele wereld in dit vakgebied.

Veel eerder al maakte Lex Schrijver naam met zijn boek Theory of Linear and Integer Programming (1986). Een boek, waarin hij schrijvenderwijs onderzoek deed naar witte plekken in de theorie. Het geeft een zeer fundamentele en complete behandeling van met name de wiskundige aspecten van de lineaire en geheeltallige optimalisering, ook met het oog op de berekeningscomplexiteit. Ook dit is een standaardwerk in het vakgebied en ook hiervoor ontving hij de Lanchester Prize.

Verbind de twee punten A met een pad, net als de twee punten B, de twee punten C en de twee punten D. Doe dit op zo’n manier dat twee verschillende paden niet eenzelfde straat of kruispunt gebruiken (ook geen eindpunt.) Kan dit? Dit probleem doet zich voor bij het ontwerpen van een chip. De punten stellen dan contacten voor die onderling moeten worden verboden met een elektrische verbinding. Het gaat dan vaak om duizenden verbindingen. Schrijver vond een methode voor dit probleem die gebaseerd is op de topologie van de chip.

CV

Lex Schrijver studeerde wiskunde aan de Vrije Universiteit in Amsterdam, waar hij ook promoveerde (1977). Van 1983 tot 1989 was hij hoogleraar in Tilburg, waarna hij in dienst trad bij het Centrum voor Wiskunde en Informatica (CWI). Hij is er lid van het Management Team en leider van het onderzoekscluster Probability, Networks and Algorithms. Daarnaast is hij sinds 1990 ook deeltijdhoogleraar in de Discrete wiskunde en optimalisering aan de Universiteit van Amsterdam.

Schrijver was als gastonderzoeker in Oxford, Szeged, Bonn, ENS Paris, Rutgers University, Yale University, was consultant bij Bell Communications Research en Microsoft Research en kreeg in 2002 een eredoctoraat wiskunde van de University of Waterloo, Ontario, Canada.

Sinds 1995 is Lex Schrijver lid van de Koninklijke Nederlandse Akademie van Wetenschappen en sinds kort ook buitenlands lid van de Nordrhein-Westfälische Akademie der Wissenschaften.

Behalve zes boeken publiceerde Schrijver meer dan 120 artikelen en ontving hij een groot aantal prijzen, waaronder tweemaal de Fulkerson Prize van de American Mathematical Society (in 1982 en 2003), de Dantzig Prize van de Mathematical Programming Society en Society for Industrial and Applied Mathematics (2003) en tweemaal de Lanchester Prize van de Operations Research Society of America (in 1987 en 2004).

Meer weten

Dit artikel is een publicatie van Centrum Wiskunde & Informatica (CWI).
© Centrum Wiskunde & Informatica (CWI), alle rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 06 juni 2005

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.