Hij houdt van problemen die je makkelijk kunt formuleren, maar die je juist moeilijk kunt oplossen. Een optimale treindienstregeling, of een optimaal schoolrooster bijvoorbeeld. Problemen die en passant tot de heilige graal van zijn vakgebied kunnen leiden. Een miljoen dollar en eeuwige roem voor wie de graal vindt. Maar Schrijver gaat het om de wiskunde erachter.
Uit een boekenkast vol specialistische wiskundeboeken trekt hij een ogenschijnlijk buitenbeentje: ‘Blauwe Tramlijnen in Kleur’. Een boek vol herinneringen aan de tram van de Noord-Zuid-Hollandse Vervoersmaatschappij, die in de jaren vijftig tussen Amsterdam en Zandvoort reed, precies langs zijn geboortehuis aan de Admiraal de Ruijterweg in de hoofdstad. Deze tramlijn wekte in de kleuterschooljaren al zijn belangstelling voor de tak van wiskunde die hij later ging beoefenen. De jonge Lex Schrijver zag dat de samenstelling van de passerende trams varieerde: verschillende typen rijtuigen, soms langer, soms korter. Hij probeerde er systeem in te ontdekken, en zo kon hij na een tijdje voorspellen in welke samenstelling de tram op een bepaald tijdstip voorbij reed.
Het was de tijd waarin hij samen met zijn vier broers ook eigenhandig dienstregelingen in elkaar knutselde. Ze verzonnen routes door de stad en trokken er met de fiets op uit. In welke tijd moesten ze een stuk fietsen om alle stukken op elkaar te laten aansluiten? Een dienstregeling voor fietsers. Niet dat je er iets aan hebt. Gewoon voor een leuke middag fietsen en puzzelen.
Grensvlak
Vijftig jaar later houdt wiskundige Lex Schrijver (1948) zich nog steeds met planningsproblemen bezig: hoe ontwerp je een optimale treindienstregeling, een optimaal schoolrooster of een optimale postbezorging? Allemaal problemen die vaak onmogelijk veel rekentijd kosten om alle mogelijke combinaties te doorzoeken en dan de beste uit te kiezen. De uitdaging voor de wiskundige is dan om snellere oplossingen te vinden, zonder alle mogelijkheden af te lopen. Combinatoriek, heet het vakgebied. Schrijver werkt aan het Centrum Wiskunde & Informatica (CWI) in Amsterdam en is deeltijdhoogleraar aan de Universiteit van Amsterdam. In 2005 won hij de hoogste Nederlandse wetenschappelijke prijs voor zijn werk, de Spinozaprijs. Ook in het buitenland sleepte hij talloze prijzen in de wacht.
“Mijn vakgebied ligt op het grensvlak van zuiver en toegepast onderzoek”, zegt Schrijver. “Er zijn diepere takken van wiskunde dan combinatoriek. En er zijn ook lastigere praktische problemen. Daar kijk ik allebei niet naar. Ik kijk naar combinatorische problemen die je met mooie wiskunde mooi kunt lossen. En daar zijn er gelukkig meer dan genoeg van.”
Dat zijn wiskundige oplossingsmethoden praktische toepassingen hebben, doet hem uiteraard plezier, maar, zegt hij, wat hem echt drijft is toch het wiskundig puzzelen zelf. Dat ongrijpbare, abstracte denkproces van talloze nieuwe wegen inslaan, de een na de ander zien doodlopen, weer nieuwe wegen ontdekken, en langs een van die wegen opeens een oplossing ontwaren. Schrijver: “Er wordt wel gezegd dat je wiskundige doorbraken voor je dertigste doet. Ik merk echter dat hoe langer ik bezig ben, hoe beter ik combinatorische structuren doorzie. Door deze ervaring bouw je intuïtie op voor welke wegen je wel of niet bewandelt.”
In principe hanteert hij het criterium dat als hij na een paar weken stoeien nog geen vooruitgang heeft geboekt, hij het vraagstuk terzijde legt. ‘Treinproblemen’ noemt hij ze. Ze zijn te riskant om je er dag in dag uit op te storten. Je mag er alleen maar in de trein aan werken – in uren die anders toch maar in het niets glijden. Maar dat terzijde schuiven is lastig, want vaak blijft een probleem ongevraagd knagen. Zo begon hij in 1978 aan een theoretisch probleem, dat hij een paar jaar later opgaf bij gebrek aan vooruitgang. Twintig jaar later schoot de oplossing hem midden in de nacht te binnen, toen hij zijn dochter de fles gaf.
Korter en eleganter
De Hongaar László Lovász, winnaar van de Wolf Prijs – een soort Oscar voor een wiskundige carrière – en ook van de Nederlandse Brouwermedaille, vertelt telefonisch over zijn collega: “Naast prachtige, specialistische wiskundige bewijzen, heeft Schrijver hét standaardwerk over combinatorische optimalisering geschreven: een driedelig boekwerk dat iedereen in het vakgebied bestudeert. Het is uitzonderlijk zorgvuldig geschreven en er ligt uitzonderlijk zorgvuldig literatuur- en historisch onderzoek aan ten grondslag. Daarnaast presenteert hij nieuwe bewijzen, nieuwe manieren om over een probleem na te denken en vooral ook een overkoepelende manier om tegen combinatorische problemen aan te kijken.”
In 1978 begon Schrijver aan het boek. Een jaar had hij er voor uit getrokken. Het werden er 25. Schrijver: “Ik heb het in eerste instantie geschreven voor mezelf. Anders hou je het niet al die jaren vol. Ik heb overal op mijn eigen manier over nagedacht. Steeds vroeg ik me af: kan het niet korter, eleganter, simpeler? In 25 jaar een dik boek schrijven is geen kunst. De uitdaging was om het aantal pagina’s te minimaliseren.”
Moeilijker blijkt makkelijker
Lange tijd werkte Schrijver aan puur theoretische vraagstukken. Dat veranderde toen de NS begin jaren negentig aanklopte met een praktisch probleem. Het bedrijf wilde het beschikbare materieel zo inzetten dat zoveel mogelijk reizigers konden zitten. Specifiek ging het om zogeheten Koplopers, die in kortere en langere uitvoeringen voorkomen. Beide uitvoeringen kun je combineren, en ze worden onderweg soms bij- of afgekoppeld. Omdat ze een verschillend aantal zitplaatsen hebben, bepaalt het verwachte aantal reizigers de mogelijke treincombinaties per rit. Maar er zijn heel veel mogelijkheden. Te veel voor de NS. En te veel voor een softwarebedrijf dat er aan begon.
“Uiteindelijk duurde het tien jaar voor ik de oplossing vond. Je kunt het probleem vertalen in een meetkundig vraagstuk met duizend dimensies. Wat ik ook probeerde, ik kwam op een gegeven moment niet verder. Tot ik het aantal dimensies gingen uitbreiden tot zo’n dertigduizend. Intuïtief denk je dat het probleem daardoor alleen maar moeilijker wordt, maar het werd juist makkelijker. Dat is het rare. Ineens vond ik een snelle oplossing voor het NS-probleem.” Later legde Schrijver samen met CWI-collega Adri Steenbeek ook de wiskundige basis voor de geheel nieuw opgezette NS-dienstregeling, die eind 2006 werd ingevoerd.
Naar aanleiding van krantenartikelen over Schrijvers werk klopte de Universiteit van Maastricht in 1995 aan met een ander nijpend probleem. Co-assistenten dreigden de universiteit met juridische stappen als ze niet op tijd hun co-schappen konden lopen. Door de invoering van een nieuwe studiefinanciering, dreigde voor sommige studenten de studiefinanciering te stoppen voordat ze al hun co-schappen hadden afgerond. Om aan de eisen van de studiefinanciering te voldoen, wilden ze alle co-schappen binnen een bepaalde tijd lopen. Ook dit planningsprobleem werd met collega Adri Steenbeek opgelost.
Schrijver pakt praktische problemen alleen aan als hij er wetenschappelijke grenzen voor moet verleggen. “Anders concurreren we met belastinggeld met de markt, en dat mag natuurlijk niet.” Het grootste deel van zijn Spinozaprijs van anderhalf miljoen euro besteedt Schrijver aan het samenbrengen van fundamentele wiskunde met concrete toepassingen, want daar valt nog een wereld te winnen, vindt hij.
Niveauverlaging
Een klein deel van het prijzengeld gaat naar het interesseren van middelbare scholieren voor het vak. Schrijver heeft een uitgesproken mening over de recente historie van het wiskundeonderwijs in Nederland: “Het axioma is: wiskunde is belangrijk, dus moet iedereen het kunnen. En als niet iedereen het kan, verlagen we het niveau. Wiskundeopgaven worden in een verhaaltje gegoten, maar het achterliggende wiskundeprobleem is vaak makkelijk op te lossen. Voor de potentiële wiskundestudent is dat geen uitdaging meer. Volgens mij kiezen scholieren minder voor wiskunde omdat het te makkelijk is geworden. Omdat het geen wiskunde meer is.”
Juist om scholieren wel uit te dagen, heeft hij samen met een onafhankelijk projectbureau voor natuurwetenschappelijk onderwijs en wetenschapscommunicatie, De Praktijk, het project DisWis opgezet, afkorting voor Discrete Wiskunde. “We willen wiskunde presenteren als een vak met open problemen in plaats van als een vak dat af is. Want dat is de indruk die veel scholieren hebben: een soort gereedschapskist die al compleet is. De lessen worden gegeven door wiskundestudenten. Zij confronteren scholieren in de vijfde klas van het VWO met uitdagende problemen die dicht tegen de praktijk aan liggen. Ook gaan de scholieren op excursie naar een bedrijf dat daadwerkelijk tegen zo’n probleem aanloopt.”
Heilige graal
Veel wiskundige problemen waaraan Schrijver werkt, hebben te maken met de heilige graal van zijn vakgebied. Voor wie deze vindt, ligt een miljoen dollar klaar. Dat is het bedrag dat het Clay Mathematics Institute in het jaar 2000 uitloofde voor de eerste die een antwoord vindt op de vraag waarom sommige combinatorische problemen een snelle oplossingsmethode hebben en andere problemen niet, of beter gezegd: niemand heeft nog een snelle methode gevonden.
Officieel heet de heilige graal het ‘P versus NP’-probleem. NP-problemen zijn problemen waarvan je gemakkelijk kunt testen of een gegeven oplossing correct is, maar moeilijk de correcte oplossing kunt vinden. Een befaamd – sommigen zien het eerder als ‘berucht’ – voorbeeld is het handelsreizigersprobleem. Daarbij staat een handelsreiziger voor de vraag hoe hij de kortste rondreis kan bepalen langs een gegeven aantal plaatsen die hij allemaal moet bezoeken. Dat probleem loopt zo snel uit de hand dat voor vijftig steden al meer dan 10^62 mogelijke routes ontstaan, ofwel een 1 met 62 nullen.
Schrijver: “De naïeve gedachte is dat als je maar genoeg computerkracht combineert, je ook wel alle problemen met een eindig aantal oplossingen kunt doorrekenen. Dat is niet zo. Al zou je kunnen rekenen met alle atomen in het heelal, en dat zelfs vanaf de oerknal, dan nog kun je niet alle oplossingen doorrekenen.”
P staat voor die klasse van problemen waarvoor je wel snel een oplossing kunt vinden, zoals het kortsterouteprobleem. Daarvan wordt de oplossingsmethode – ontwikkeld door de Nederlander Edsger Dijkstra – tegenwoordig standaard in TomTom’s gebruikt. De grote vraag is of je voor alle NP-problemen snelle oplossingsmethoden kunt vinden, zodat het P-problemen worden. Voor het handelsreizigersprobleem, het schoolroosterprobleem en het dienstregelingprobleem is zo’n methode nooit gevonden. Veel wiskundigen denken dat er geen snelle methode bestaat, maar hoe bewijs je dat?
Een wiskundig probleem kraken dat aan de ene kant zo fundamenteel is, en aan de andere kant zoveel praktische toepassingen heeft – dat moet toch de ultieme uitdaging voor een wiskundige zijn. Heeft Schrijver zich er wel eens aan gewaagd? “Af en toe in een vrij uurtje denk je eraan. Maar het probleem is te gevaarlijk. Niemand weet waar hij moet zoeken. Misschien ligt de oplossing om de hoek, maar ja, welke hoek? In de natuurkunde bouwen ze voor een paar miljard een nieuwe deeltjesversneller. Dan heb je een goede kans dat je iets nieuws vindt. Bij onze heilige graal ligt dat anders. Het is niet zo dat als je een paar miljard in het onderzoek stopt, iemand ook gegarandeerd een oplossing vindt. We hebben nog niet eens het begin van een oplossing.”
