'Wanneer is software snel?' Deze vraag onderzoekt CWI-promovenda Sophie Huiberts in haar artikel in AG Connect van 7 december 2021. 'Als we begrijpen wat een algoritme snel maakt, dan kan dat misschien helpen bij het ontdekken van nog snellere algoritmes'. (Overname met toestemming.)
Wanneer is software snel?
Mysteries rond MIP-software verklaard
Welke algoritmes zijn snel en welke zijn langzaam? Dit is een belangrijke vraag voor softwareontwikkelaars, want waar een berekening met een snel algoritme in seconden klaar kan zijn, kan dezelfde berekening met een langzaam algoritme wel weken duren. Ook voor wetenschappers is deze vraag belangrijk, ziet Sophie Huiberts. Als we begrijpen wat een algoritme snel maakt, dan kan dat misschien helpen bij het ontdekken van nog snellere algoritmes.
Er is geen enkele theorie die de snelheid van alle algoritmes kan verklaren. Maar door verschillende modellen te bestuderen, kunnen we toch bepaalde praktische observaties tot harde wiskunde maken.
Mijn onderzoek aan het Centrum Wiskunde & Informatica gaat over algoritmes in planningsoftware uit de operations research. Planningssoftware is voor veel bedrijven en organisaties een belangrijk deel van de digitale strategie. Of het nou gaat om je lokale pakketbezorger, grote bedrijven met internationale supply chains, of het matchen van nierdonoren met patiënten, overal worden processen geoptimaliseerd met dit soort software. Dat gebeurt niet voor niks. Een betere planning berekenen kan 2-15% kosten besparen, of zorgen dat je betere resultaten haalt met de middelen die je hebt. Maar ondanks dat slimme planningssoftware onmisbaar is in zo veel organisaties, weten wetenschappers nog maar weinig over waarom deze software zo goed werkt als ze het doet.
en concreet voorbeeld hiervan is software voor het oplossen van 'mixed integer programs' (MIPs). MIP is een wiskundige manier om verschillende praktische planningsproblemen te formuleren, bestaande software kan deze MIPs inlezen en vervolgens een goede planning uitrekenen. Er bestaan open source solvers voor MIP en ook verschillende commerciële leveranciers verkopen MIP software, waaronder Gurobi, IBM en SAS. Er zit zelfs een MIP solver ingebouwd in Microsoft Excel.
Slechtstegevalanalyse
Deze MIP software is omgeven van wetenschappelijke mysteries. Dit komt door een populaire theorie uit de informatica genaamd de 'slechtstegevalanalyse'. Volgens deze theorie is een algoritme langzaam, als er invoer bestaat waarop het algoritme langzaam is. Op het eerste gezicht klinkt dat redelijk. Maar wat blijkt? Volgens de slechtstegevalanalyse zijn MIPs moeilijk op te lossen. MIP is namelijk 'NP-volledig', wat inhoud dat wetenschappers geloven dat elk algoritme voor MIP langzaam is volgens de slechtstegevalanalyse. Toch bestaan er solvers die elke dag vele MIPs oplossen. Blijkbaar zijn de MIPs die we tegenkomen in het echte wereld veel makkelijker dan de MIPs die we 'in het lab' kunnen maken. Hoe dat komt, dat is een groot raadsel.
Vergelijk het met de wet van Murphy: als iets mis kan gaan, dan gaat het mis.
Dit lijkt een beetje op de slechtstegevalanalyse, waarin we verwachten dat we de moeilijkst mogelijke invoer zullen zien. Het mag duidelijk zijn dat de wet van Murphy vaak geen realistische verwachtingen schept. Op meerdere plekken in de theoretische informatica zien we dat de slechtstegevalanalyse niet genoeg is om te begrijpen welke algoritmes goed werken. Naast MIP zijn andere grote voorbeelden ‘local search algoritmes’, de ‘caching policies’ die in bijvoorbeeld besturingssystemen zitten, en recent ook AI-methoden zoals neurale netwerken. Deze algoritmes zijn allemaal heel succesvol in de praktijk, ondanks dat er voorbeelden bekend zijn waarop ze langzaam zijn of slechte uitvoer geven. Ze werken dus significant beter dan de klassieke theorie voorspelt.
Sinds de eeuwwisseling kijken wetenschappers steeds vaker naar manieren om voorbij de slechtstegevalanalyse te gaan. Steeds meer theoretische modellen worden bedacht om de snelheid van algoritmes te bestuderen. De oudste hiervan is de ‘gemiddelde gevalsanalyse’. Hierin kiest de onderzoeker een mooie kansverdeling over invoer voor het algoritme en bewijst vervolgens dat de gemiddelde looptijd klein is. Het probleem is alleen dat willekeurige invoer vaak helemaal niet lijkt op invoer uit de praktijk, zoals te zien in de figuur.
Bijschrift: Een typische afbeelding lijkt niet op een willekeurige afbeelding.
Zo heeft ieder theoretisch model wel een zwakte. Maar door genoeg verschillende modellen te bestuderen kunnen we toch een wiskundige onderbouwing geven voor de intuïties achter de algoritmes.
Een beetje ruis
In één project onderzochten we het effect van een beetje willekeurige ruis toevoegen aan de invoer van het zogeheten simplexalgoritme, een belangrijk onderdeel van alle bestaande MIP-software. We wisten te bewijzen dat dit algoritme veel sneller is als je een beetje ruis toevoegt door kleine willekeurige getallen op te tellen bij alle invoerdata. In de praktijk zien we iets soortgelijks, want de best beschikbare MIP-software gebruikt ook een beetje ruis om het interne simplexalgoritme sneller te maken. De details verschillen nog behoorlijk tussen de ruis in de praktijk en in de theoretische analyse, maar de eerste stappen zijn gezet.
Recent hadden we een ander project, waarin we keken naar een getal genaamd de ‘integrality gap.’ Dit is een getal dat je voor iedere MIP kunt schatten, en in de praktijk geeft dit getal een goede voorspelling voor de snelheid van het ‘branch-and-bound’-algoritme. Dit algoritme is ook een belangrijk onderdeel van alle bestaande MIP-software. We konden bewijzen dat de integrality gap in een gemiddelde gevalsanalyse ook een goede voorspeller is voor de looptijd. Zo heeft deze vuistregel uit de praktijk dus een wiskundige onderbouwing gekregen.
Het begrijpen van algoritmes vergt een constante zoektocht naar goede modellen om te bestuderen, zodat we een rigoureuze theoretische basis kunnen geven aan praktische observaties. Hoewel al een aantal successen is geboekt, blijven nog veel open vragen voor toekomstig onderzoek.
Wat is MIP?
Een optimisatieprobleem is een MIP als het is op te schrijven als:
minimaliseer cTx
onder voorwaarde dat Ax = b
x ≥ 0
Hier kiest de gebruiker de matrix A, de vectoren b en c, en welke coördinaten van x geheeltallig moeten zijn. Vervolgens is de taak van de MIP solver om een x te vinden die aan alle voorwaarden voldoet, en om uit alle mogelijke x’en die aan alle voorwaarden voldoen, degene te vinden die het inproduct cTx zo klein mogelijk maakt.
Dit klinkt wellicht heel abstract, en dat klopt ook. De kracht van MIP is dat het heel abstract en veelzijdig is, daarom kunnen veel verschillende praktische problemen als MIP worden uitgedrukt. Hier een paar problemen die met MIP opgelost kunnen worden:
- de kortste autoroute die elk adres op een lijst bezoekt
- video stabiliseren
- zo goed mogelijk (kopieën van) bestanden verdelen over servers
Op het eerste gezicht hebben deze problemen weinig met elkaar te maken,. Dat is precies waarom MIP zo nuttig is.
Een groot voordeel van MIP is dat je als gebruiker enkel de voorwaarden beschrijft waar de uitvoer aan moet voldoen, en dat de MIP software vervolgens alles achter de schermen regelt. Doordat je zelf niks met de implementatie te maken hebt, blijft je eigen code overzichtelijk en kun je er makkelijk aanpassingen in maken.
Hoewel MIP software vanuit theoretisch perspectief nog slecht begrepen wordt, is deze software in de praktijk heel betrouwbaar en efficiënt. Het wordt door veel bedrijven en instanties gebruikt, zoals AMD, Google en de Amerikaanse communicatiewaakhond FCC.
Een goede introductie voor optimalisatiesoftware en vergelijking tussen verschillende producten is te vinden op https://neos-server.org.
SOPHIE HUIBERTS is promovenda aan het Centrum Wiskunde & Informatica (CWI).
- Sophie Huiberts: https://www.cwi.nl/people/sophie-huiberts
- Privé homepage Sophie Huiberts: https://sophie.huiberts.me/
