Waarom is dit belangrijk?
Planners gebruiken combinatorische optimalisatie om dienstroosters te maken waarin elke dienst bezet is en verplichte rusttijden blijven gelden. In de zorg wijst een ziekenhuis met deze aanpak verpleegkundigen toe aan dagdiensten, avonddiensten en nachtdiensten. Patiënten en werknemers krijgen zo een bezette afdeling, maar wensen van personeel zijn vaak geen harde eis en een snelle berekening levert soms geen volledig passend rooster.
Zo werkt het in de praktijk
Bezorgbedrijven gebruiken combinatorische optimalisatie om routes voor een vloot voertuigen te kiezen. George Dantzig en John Ramser pasten dit in 1959 toe op benzineleveringen. Varianten behandelen ook het ophalen van vast afval.
De TU Delft onderzoekt met steun van NWO of één algoritme veel problemen oplost. Nu maken informatici vaak een apart algoritme per combinatorisch probleem. Het project wil zo het maken van methoden voor treindienstregelingen en productieplannen in fabrieken vereenvoudigen.
Combinatorische optimalisatie hoort bij operations research, een werkwijze met wiskundige modellen voor beslissingen. Veel vragen worden als geheeltallig programmeren gezet: elke keuze is een heel getal. Branch-and-bound zoekt systematisch en kapt zwakke takken af. Branch-and-cut berekent grenzen met een lineair rekenmodel.




