Wij volgen optimalisatieonderzoek en dragen bij aan open source

Optimalisatie begon als een planningsprobleem in oorlogstijd en groeide uit tot een vakgebied. De simplexmethode verscheen in 1947, en de vijftien jaar daarna leverden het meeste gereedschap op dat vandaag nog draait: dynamisch programmeren, snijvlakken, branch and bound, kortste paden, en de decomposities waarmee één groot probleem als een reeks kleine wordt opgelost.

Toen liet Karp in 1972 zien waarom het werk nooit af zou zijn. Een hele familie gewone planningsproblemen heeft geen bekend efficiënt exact algoritme, en er is er sindsdien geen gevonden. Het antwoord was niet één beter algoritme maar vele, geleend waar ze maar te vinden waren: simulated annealing bij de metallurgie, tabu search bij het idee van een kort geheugen, genetische algoritmen en ant colony optimisation bij de biologie, constraint programming bij de logica, en large neighbourhood search bij de vaststelling dat een goed plan meestal één kleine wijziging van een beter plan verwijderd is.

Geen ervan heeft gewonnen, en dat is precies het punt. Elk is sterk op een vorm van probleem die de andere slecht aankunnen, dus hield het vakgebied ze allemaal en leerde het ze te combineren: exact zoeken gestuurd door heuristieken, constraintpropagatie ondersteund door clause learning, en sinds kort vertakkingsbeslissingen geleerd uit data. De laatste jaren kwamen daar eerste-orde-methoden en GPU's bij, die lineaire programma's heropenen op groottes waarvoor de simplexmethode nooit bedoeld was.

Julia is waar veel van het huidige optimalisatieonderzoek geschreven wordt. Het draait op de snelheid die solvers nodig hebben en leest dicht bij de wiskunde, zodat een artikel en zijn implementatie herkenbaar hetzelfde blijven.

JuMP ligt daarbovenop. Beschrijf een probleem één keer, in bijna wiskundige syntaxis, en geef het door aan een van de meer dan 30 solvers achter één interface. Het is de de-factostandaard in de Julia-gemeenschap en de ruggengraat van optimalisatieonderzoek aan Europese universiteiten, waaronder UCLouvain, waar een deel van ons team is opgeleid.

Wij werken eraan, niet alleen ermee. Teamleden dienen pull requests in op de kernpakketten, onderhouden solverinterfaces en presenteren op de JuMP-dev-workshop.

Gebouwd op