Integer Linear Programming: Der Algorithmus, der Rucksäcke packt und Frequenzen plant
Algorithmus des Monats Dieser Algorithmus steckt hinter vielen alltäglichen Problemen, ist aber fast unbekannt. Er gehört zu den komplexesten Problemen und beschäftigt Mathematiker seit Jahrzehnten.
Selten ist der Name eines Algorithmus so irreführend wie Integer Linear Programming (ILP), zu deutsch ganzzahlig-lineare Optimierung. Denn obwohl er einfach klingt – Berechnungen mit Ganzzahlen sind einfacher und schneller als mit Gleitkommazahlen – zählt er zu den NP-vollständigen Problemen.
Auch hat er mit Programmierung nicht direkt etwas zu tun. Wir erklären, was es damit auf sich hat, warum der Algorithmus so wichtig ist, dass der Entwickler der Grundidee dafür vom US-Präsidenten ausgezeichnet wurde, und wie Mathematiker seiner Komplexität zu Leibe rücken.
