211service.com
Nieuw algoritme kan oplossingen voor het 'Max Flow'-probleem drastisch stroomlijnen
Het vinden van de meest efficiënte manier om items over een netwerk zoals het Amerikaanse snelwegsysteem of internet te vervoeren, is een probleem dat wiskundigen en computerwetenschappers al tientallen jaren belast.
Om het probleem aan te pakken, hebben onderzoekers traditioneel een maximum-flow-algoritme gebruikt, ook bekend als max flow, waarin een netwerk wordt weergegeven als een grafiek met een reeks knooppunten, ook wel hoekpunten genoemd, en verbindingslijnen ertussen, randen genaamd.
Aangezien elke rand een maximale capaciteit heeft - net als de wegen of de glasvezelkabels die worden gebruikt om informatie over internet te verzenden - proberen dergelijke algoritmen de meest efficiënte manier te vinden om goederen van het ene knooppunt in de grafiek naar het andere te sturen, zonder deze beperkingen.
Maar aangezien de omvang van netwerken zoals internet exponentieel is gegroeid, is het volgens Jonathan Kelner, universitair hoofddocent toegepaste wiskunde aan het MIT en lid van de MIT-groep, vaak onbetaalbaar om deze problemen op te lossen met behulp van traditionele computertechnieken. Laboratorium voor computerwetenschappen en kunstmatige intelligentie (CSAIL).
Dus in een paper die deze week wordt gepresenteerd op het ACM-SIAM-symposium over discrete algoritmen in Portland, Oregon, zullen Kelner en zijn collega Lorenzo Orecchia, een instructeur toegepaste wiskunde, samen met afgestudeerde studenten Yin Tat Lee en Aaron Sidford, een nieuw theoretisch algoritme dat het aantal bewerkingen dat nodig is om het max-flow-probleem op te lossen drastisch kan verminderen, waardoor het mogelijk wordt om zelfs grote netwerken zoals internet of het menselijk genoom aan te pakken.
AFBEELDING: CHRISTINE DANILOFF / MET
Er is onlangs een explosie geweest in de grootte van grafieken die worden bestudeerd, zegt Kelner. Als u bijvoorbeeld verkeer op internet wilt routeren, alle verbindingen op Facebook wilt bestuderen of genomische gegevens wilt analyseren, kunt u gemakkelijk grafieken krijgen met miljoenen, miljarden of zelfs biljoenen randen.
Eerdere max-flow-algoritmen hebben het probleem één rand of pad tegelijk bereikt, zegt Kelner. Dus wanneer bijvoorbeeld items van knooppunt A naar knooppunt B worden verzonden, sturen de algoritmen een deel van de goederen langs het ene pad, totdat ze de maximale capaciteit hebben bereikt, en beginnen dan met het verzenden van een deel langs het volgende pad.
Veel eerdere algoritmen, zegt Kelner, zouden een pad van punt A naar punt B vinden, er wat stroom langs sturen en dan zeggen: 'Kan ik, gezien wat ik al heb gedaan, een ander pad vinden waarlangs ik meer kan sturen?' Wanneer men stroom tegelijkertijd langs veel verschillende paden moet sturen, leidt dit tot een intrinsieke beperking van de snelheid van het algoritme.
Maar in 2011 ontwikkelden Kelner, CSAIL-afgestudeerde student Aleksander Madry, wiskundestudent Paul Christiano en collega's van Yale University en de University of Southern California een techniek om alle paden tegelijkertijd te analyseren.
De onderzoekers zagen de grafiek als een verzameling elektrische weerstanden en stelden zich vervolgens voor om een batterij aan te sluiten op knooppunt A en een aarde op knooppunt B, en de stroom door het netwerk te laten stromen. Elektrische stroom kiest niet slechts één pad, het stuurt een klein beetje stroom over elke weerstand in het netwerk, zegt Kelner. Dus het onderzoekt de hele grafiek globaal en bestudeert tegelijkertijd vele paden.
Hierdoor kon het nieuwe algoritme het max-flow-probleem aanzienlijk sneller oplossen dan eerdere pogingen.
Nu heeft het MIT-team een techniek ontwikkeld om de looptijd nog verder te verkorten, waardoor het mogelijk wordt om zelfs gigantische netwerken te analyseren, zegt Kelner.
In tegenstelling tot eerdere algoritmen, die alle paden in een grafiek als gelijken beschouwden, identificeert de nieuwe techniek die routes die een knelpunt binnen het netwerk vormen. Het algoritme van het team verdeelt elke grafiek in clusters van goed verbonden knooppunten en de paden daartussen die knelpunten creëren, zegt Kelner.
Ons algoritme berekent welke delen van de grafiek gemakkelijk kunnen routeren wat ze nodig hebben, en welke delen de knelpunten zijn. Hierdoor kun je je concentreren op de knelpunten en de structuur op hoog niveau, in plaats van veel tijd te besteden aan het nemen van onbelangrijke beslissingen, waardoor je je tijd veel efficiënter kunt besteden, zegt hij.
Het resultaat is een bijna lineair algoritme, zegt Kelner, wat betekent dat de hoeveelheid tijd die nodig is om een probleem op te lossen bijna recht evenredig is met het aantal knooppunten op het netwerk. Dus als het aantal knooppunten in de grafiek wordt vermenigvuldigd met 10, zou de hoeveelheid tijd worden vermenigvuldigd met iets dat heel dicht bij 10 ligt, in plaats van vermenigvuldigd met 100 of 1.000, zegt hij. Dit betekent dat het in wezen zo goed schaalt als je zou kunnen hopen met de grootte van de invoer, zegt hij.
Shanghua Teng, een professor in computerwetenschappen aan de Universiteit van Zuid-Californië die niet betrokken was bij het laatste artikel, zegt dat het een grote doorbraak betekent in grafische algoritmen en optimalisatiesoftware.
Dit artikel, dat op de [ACM-SIAM]-conferentie de prijs voor het beste papier heeft gewonnen, is het resultaat van de aanhoudende inspanningen van Kelner en zijn collega's bij het toepassen van elektrische stromen om efficiënte grafiekalgoritmen te ontwerpen, zegt Teng. De paper bevat een verbazingwekkende reeks technische bijdragen.