Je leest:

Optimaal combineren

Optimaal combineren

Auteur: | 24 november 2005

Wie combineert, doet dat graag optimaal. Het vakgebied dat dit soort vraagstukken onderzoekt heet combinatorische optimalisering. De beste combinatie selecteren door alle combinaties stuk voor stuk langs te gaan kost vaak veel te veel tijd. Een meetkundige aanpak blijkt effectiever.

Of je nu de meubels in je huis of je boodschappen combineert, of de tafel schikt en je vrienden koppelt, optimaliteit telt. Een school wil klassen en docenten combineren in een optimaal schoolrooster, de NS wil optimale treincombinaties, en een servicebedrijf wil opdrachten combineren in optimale werkpakketten. Een telefoonmaatschappij wil gesprekken optimaal combineren in gecomprimeerde berichten, een chipfabrikant wil verbindingen optimaal combineren op een chip, en een transportfirma wil de leveringen combineren in een optimale bezorgroute. Dit probleem vraagt naar de kortste rondreis langs een gegeven verzameling steden: bijvoorbeeld de kortste rondreis langs de 12 provinciehoofdsteden van Nederland.

Het handelsreizigersprobleem

Het handelsreizigersprobleem werd al in 1832 beschreven in Der Handlungsreisende – wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein, een handleiding voor de succesvolle handelsreiziger.

Hoewel er nauwelijks nog handelsreizigers rondreizen, is het probleem nog steeds zeer actueel. Zo komt een transportbedrijf het probleem tegen bij het bezorgen van goederen, de post bij het bezorgen van post en bij het lichten van brievenbussen, en de huisdokter bij het bezoeken van patiënten.

In de industrie komt het probleem ook voor, bijvoorbeeld bij het bepalen van de kortste route van een robotarm die gaatjes moet boren in een printplaat, of van de optimale volgorde langs een assemblagelijn. In het algemeen doet het probleem zich voor bij het bepalen van een optimale volgorde van handelingen voor mens of machine.

Dit komen we ook tegen in het dagelijkse leven. Wie snel de zaterdagse boodschappen bijeen wil winkelen, lost een handelsreizigersprobleem op. Zelfs op vakantie ontkom je er niet aan, als je in een vreemde stad efficiënt de vereiste bezienswaardigheden wilt bezien.

Figuur 1: De kortste rondreis langs de 12 Nederlandse provinciehoofdsteden

Universaliteit

Bovendien blijkt het handelsreizigersprobleem een universeel probleem, in de zin dat de meeste combinatorische optimaliseringsproblemen ertoe te herleiden zijn. (In het jargon van de complexiteitstheorie heet het handelsreizigersprobleem daarom een NP-volledig probleem.)

Het impliceert dat als er een efficiënte oplossingsmethode wordt gevonden voor het handelsreizigersprobleem, dan kunnen ook de meeste andere combinatorische optimaliseringsproblemen efficiënt worden opgelost. Hier wordt met ‘efficiënt’ bedoeld: binnen tijd proportioneel aan een vaste (bijvoorbeeld vierde) macht van de probleemgrootte.

De strekking van het handelsreizigersprobleem is dus veel wijder dan de naam suggereert. Terecht is veel onderzoekstijd gestoken in oplossing van dit probleem.

Combinatorische explosie

Met de komst van de computer zou men kunnen denken dat het handelsreizigersprobleem is op te lossen door simpelweg alle mogelijke rondreizen na te gaan en daaruit de kortste te kiezen. Dit zou voor 12 steden nog wel lukken: dan zijn er 19.958.400 verschillende rondreizen. En met wat puzzelen lukt het in dat geval ook nog wel met hoofd en hand.

Het aantal mogelijkheden loopt echter zeer snel (exponentieel) op: de combinatorische explosie. Dit wordt duidelijk uit het beeld dat oprijst uit de tabel met het aantal mogelijke rondreizen bij een oplopend aantal steden (tabel 1).

Tabel 1: Aantal steden – aantal rondreizen

Voor 50 steden bestaan er dus al meer dan 3 × 1062 mogelijke rondreizen. Dit betekent dat als een triljoen (miljoen x miljoen x miljoen – red.) computers elk een triljoen routes per seconde zouden kunnen nagaan (iets wat natuurkundig buiten bereik is), dan zou dat nog steeds meer dan een triljoen jaar duren – langer dan de leeftijd van het heelal. Betere methoden moeten worden gevonden.

Meetkundige voorstelling

De sleutel tot de oplossing werd in 1948 door Tjalling Koopmans gesuggereerd. Koopmans, een promovendus van Tinbergen, was in de oorlog uitgeweken naar de Verenigde Staten en daar te werk gesteld bij de Combined Shipping Adjustment Board, een instelling die wereldwijd de routes van scheepsconvooien vaststelde (aangezien deze onder militaire bescherming moesten varen).

Voor deze problemen ontwikkelde Koopmans een stroomtechniek. De methode vormde een basis voor de lineaire programmering, waarvoor hij in 1975 met Kantorovich de Nobelprijs voor de economie ontving.

Koopmans’ idee voor het handelsreizigersprobleem was als volgt. Beschouw de steden met alle tussenliggende verbindingen als een netwerk en beschouw elke rondreis als een stroom in dit netwerk. Het vinden van de kortste rondreis komt dan neer op het vinden van een optimale stroom in het netwerk. Een rondreis is een stroom van een voorgeschreven type: elke stroomwaarde is 0 of 1, en de stroom moet alle steden verbinden. Of een bepaalde verbindingen al of niet in de rondreis wordt opgenomen, wordt aangegeven met 1 of 0.

Je kunt een rondreis dan voorstellen als een uit nullen en enen bestaande vector in een hoogdimensionale ruimte. (Voor elke directe verbinding tussen twee steden voer je een dimensie in.) Dan correspondeert elke rondreis met een punt in deze ruimte, noem het een rondreispunt.

Alle rondreizen tezamen geven een verzameling punten in deze ruimte. Nu is de essentiële truc in deze aanpak dat je de ruimte (ook die tussen de rondreispunten) kunt gebruiken om de kortste rondreis te zoeken. Want zodra je een ruimte hebt, kun je er een zoektocht in maken, op zoek naar het optimale rondreispunt. In je zoektocht wil je wel graag in de buurt van de rondreispunten blijven. Dit kan bereikt worden door het convexe omhulsel van de rondreispunten te bepalen (figuur 2 geeft een voorbeeld van een convex omhulsel in twee dimensies).

Figuur 2: Elf punten en (in grijs) hun convexe omhulsel.

Het convexe omhulsel van de rondreispunten vormt een polytoop (figuur 3), welke de zoekruimte `omheint’. Dit polytoop heet het handelsreizigerspolytoop. De zijvlakken van het polytoop (die dus de omheining vormen) heten de facetten. Door binnen dit polytoop te zoeken, in een richting die bepaald wordt door de afstanden tussen de steden, kun je de kortste rondreis vinden. Er zijn methoden beschreven die de ribben van het polytoop volgen (de simplexmethode), en ook die dwars door het polytoop heen gaan (de inwendige puntmethode).

Figuur 3: Een polytoop

Toepassing op het handelsreizigersprobleem

Het centrale probleem in de bovenbeschreven methode is de bepaling van die facetten. Dit is een wiskundig probleem, dat in een aantal gevallen is opgelost, maar in veel gevallen niet – ook niet in het geval van het handelsreizigersprobleem. Wel is een wat ruimere benadering van het handelsreizigerspolytoop gevonden, die het zoekgebied redelijk omheint. Met behulp van deze aanpak konden Dantzig, Fulkerson en Johnson in 1954 de kortste rondreis langs de 48 staatshoofdsteden van de Verenigde Staten en Washington D.C. vinden (figuur 4).

Figuur 4: De kortste rondreis langs Washington D.C. en de 48 staatshoofdsteden van de Verenigde Staten.

In de loop der jaren zijn op deze manier steeds grotere handelsreizigersproblemen opgelost. Zo vond Grötschel in 1977 de kortste rondreis langs 120 steden in Duitsland en vonden Padberg en Rinaldi in 1987 de kortste route langs 2.392 te boren gaatjes in een printplaat (figuur 5). Op dit moment staat het record op naam van Applegate, Bixby, Chvátal, Cook en Helsgaun, die in 2004 de kortste rondreis langs 24.978 Zweedse steden hebben bepaald (figuur 6).

Benadrukt moet overigens worden dat voor het handelsreizigersprobleem deze meetkundige methode niet efficiënt is in de zin dat de looptijd begrensd wordt door een vaste macht van de probleemgrootte. (Dit doordat de facetten van het handelsreizigerspolytoop niet volledig bekend zijn.) De grote, nog onbeantwoorde vraag is of een efficiënte methode voor dit probleem wel bestaat. Dit is equivalent met de centrale vraag in de complexiteitstheorie, die technisch geformuleerd wordt als: Is NP ≠ P?

De oplossing van het Zweedse probleem heeft inderdaad een enorme rekentijd gekost, parallel op vele computers wereldwijd. Het directe praktische nut is niet duidelijk – we mogen aannemen dat geen handelsreiziger die Zweedse rondreis zal gaan maken. Wel hebben de berekeningen verder inzicht opgeleverd in de reikwijdte van de methoden en deze verder verscherpt. Hierdoor werden kleinere, meer praktische problemen sneller oplosbaar, en de methoden bleken ook toepasbaar op andere soorten problemen.

Figuur 5: Links de kortste rondreis langs 120 Duitse steden en rechts de kortste rondreis langs 2.392 gaatjes in een printplaat

Koplopers

De meetkundige methode werd ook gebruikt om een materieelomloopprobleem van de Nederlandse Spoorwegen aan te pakken. De NS rijdt op veel van haar lijnen met gekoppelde treinstellen. Een van de daartoe gebruikte treintypes is de zogenaamde koploper (figuur 7).

Koplopers worden onder andere ingezet op het lijnennet genaamd ` de Noord-Oost’. Dit net bestaat uit de intercity-lijnen tussen de Randstad en Noord- en Oost-Nederland. Hierbij worden treinen onderweg samengevoegd en gesplitst (bijvoorbeeld in Utrecht en Zwolle). Koplopers bestaan in twee uitvoeringen: kortere (K) en langere (L). De twee uitvoeringen kunnen onderling worden gekoppeld. Dit geeft velerlei mogelijke combinaties, zoals KLL, LK, LKL, L, KKK.

Figuur 6: In het rood: de kortste rondreis langs 24.978 Zweedse steden

De twee uitvoeringen hebben een verschillend aantal zitplaatsen. Voor elke geplande treinbeweging heeft de NS het aantal reizigers geschat, en dat impliceert minimumeisen aan de mogelijke, voor die treinbeweging in te zetten treincombinaties.

Een trein kan bij sommige stations onderweg en aan de eindpunten worden verlengd of ingekort als het verwachte aantal reizigers dit nodig of mogelijk maakt. Afgekoppelde treinstellen komen dan beschikbaar voor bijkoppeling bij andere treinen.

Belangrijk hierbij zijn de koppelcondities die de NS stelt: een trein kan worden verlengd door vooraan treinstellen bij te koppelen, en worden ingekort door achteraan treinstellen af te koppelen. Er kan niet bij een zelfde treinstop zowel bij- als afgekoppeld worden. Het is dus nodig dat, als bijvoorbeeld van een trein in Deventer een korte koploper moet worden afgekoppeld, deze dan ook achteraan zit.

Wat is nu de optimale omloop, dat wil zeggen, de omloop die zo min mogelijk materieel vergt (of zo min mogelijk askilometers maakt)? Ook deze vraag kan meetkundig worden aangepakt. De keuze om wel of niet een bepaalde treincombinatie in te zetten op een bepaalde trein, kan met 1 of 0 worden aangegeven. Dan kan elke materieelomloop worden beschreven als een 0-1 vector – in een ruimte met zo’n 10.000 dimensies (voor de Noord-Oost).

De eisen die de NS stelt aan de minimale treincombinatie bleken eenvoudig te beschrijven in dit meetkundige model. Het bleek echter uiterst lastig de koppelcondities te vertalen in een nauwkeurige omheining van het zoekgebied. Lang heb ik hierover nagedacht, maar wat ik ook probeerde, het resulterende meetkundige zoekproces bleek veel te lang te duren.

Verrassend genoeg bleek de oplossing te liggen in het uitbreiden van het aantal dimensies – met nog zo’n 30.000 dimensies extra! In die hoger-dimensionale ruimte bleken de condities meetkundig veel nauwer te formuleren. Hierdoor werd ook de projectie (ontstaan door het weer weglaten van de extra dimensies) veel beter omheind.

Van die extra dimensies heb je geen last maar baat, doordat deze je als het ware ‘warm’ of ‘koud’ zeggen bij het zoeken. Met deze lifting-techniek vindt de NS nu efficiënte materieelomlopen voor de Noord-Oost.

Een koploper ( foto: NS)

Ellipsoïden

De bovenbeschreven meetkundige methode voor het oplossen van combinatorische optimaliseringsproblemen werkt efficiënt als het convexe omhulsel exact bepaald kan worden. Je kunt je afvragen of dat ook de enige manier is om een efficiënte oplossingmethode te vinden.

Met Martin Grötschel en László Lovász heb ik in 1980 bewezen dat dit in zekere zin inderdaad zo is. We konden laten zien dat een combinatorisch optimaliseringsprobleem efficiënt kan worden opgelost, als en alleen als alle facetten van het bijbehorende polytoop kunnen worden bepaald.

Dus de implicatie geldt ook de andere kant op. De vraag naar een efficiënte methode voor het handelsreizigersprobleem is equivalent met de vraag naar een volledige bepaling van de facetten van het handelsreizigerspolytoop. Overigens zouden we, om deze stelling precies te formuleren, moeten spreken over een klasse van optimaliseringsproblemen, en moeten we ook preciezer zeggen wat bedoeld wordt met het bepalen van de facetten. De stelling is gebaseerd op Khachiyan’s ellipsoïdemethode voor lineaire programmering, waarbij in een steeds kleiner wordende ellipsoïde (figuur 8) de optimale oplossing wordt gevangen.

Figuur 8: Een ellipsoïde

Vooruitblik

Recent wordt veel onderzoek gedaan naar een verdere verscherping van de meetkundige methode, door niet alleen platte vlakken als grens voor de zoekruimte toe te laten, maar ook gekromde oppervlakken. Als deze bepaald worden door een zogeheten semidefiniete matrix, blijkt de methode nog effectiever. Wel moet nog veel werk aan deze semidefiniete programmering worden gedaan om dit echt snel te laten werken in hogere dimensies.

Vaak hebben de betreffende matrices een grote symmetrie. Methoden uit de representatie- en invariantentheorie helpen je dan deze symmetrie te gebruiken om de dimensie te verkleinen. Methoden uit de tralietheorie zoals basisreductie kunnen helpen de beste computationele dimensies te bepalen – deze zijn vaak heel anders dan de dimensies waarin het probleem zich voordoet. Ook de reële algebraïsche meetkunde geeft methoden (zoals de Positivstellensatz) die de zoekruimte kunnen verkleinen, bijvoorbeeld door beperkingen voor te stellen als sommen van kwadraten van polynomen.

Dergelijke toepassingen van algebra en meetkunde in de optimalisering staan nog in de kinderschoenen maar hebben een grote potentie. Hierop wil ik de Spinozapremie richten.

Overigens is serendipiteit (het bij toeval ontdekken van waar niet naar gezocht wordt) cruciaal in de wetenschap, zeker in de wiskunde, want stellingen laten zich moeilijk plannen. Daarom houd ik ook capaciteit vrij voor mogelijke onverwachte nieuwe onderzoeksrichtingen.

Tenslotte: geen wiskunde zonder wiskundigen. Het hoge peil van de wiskunde in Nederland dreigt verloren te gaan door de lage studenteninstroom. Hoewel ik besef dat een kering van het tij een cultuuromslag vergt waarvoor zelfs anderhalf miljoen niet toereikend is, wil ik de Spinozapremie toch inzetten voor wat druppels op deze gloeiende plaat. Want wiskunde is belangrijk, en moeilijk, en juist daarom leuk!

Dank

Ik zie de toekenning van deze Spinozapremie ook als erkenning van de langjarige inspanningen van Cor Baayen en Jack van Lint de discrete wiskunde in Nederland op te bouwen. Naast hen dank ik ook het Centrum voor Wiskunde en Informatica en de Universiteit van Amsterdam voor de mogelijkheden mijn onderzoek te doen, mijn familie, vrienden en collega’s voor hun stimulerende belangstelling en samenwerking, en in het bijzonder mijn ouders, vrouw en dochters voor hun voortdurend toegewijde steun.

Dit artikel is een publicatie van Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO).
© Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO), alle rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 24 november 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.