Integer Programming ist eine Unterart der mathematischen Optimierung. Dabei wird der Mathematischen Optimierung allerdings eingeschränkt, indem die vorhandenen Variablen nur noch ganzzahlige Werte annehmen dürfen.[3]
Bei der mathematischen Optimierung wird ein lineares Gleichungssystem gelöst, wobei eine der Gleichungen optimiert werden soll. Die anderen Gleichungen müssen als Nebenbedingungen ebenfalls erfüllt werden. Dabei spielt es keine Rolle, ob die zu optimierende Gleichung minimiert oder maximiert werden soll. Ein bekanntes Beispiel ist das "Zaun-am-Fluss"-Problem, welches auch in Schulbüchern für den Berliner Mathematik-Leistungskurs [2] behandelt werden kann. Dabei soll mit einer maximalen Zaunlänge ein möglichst großes und rechteckiges Areal an einem Fluss umzäunt werden. Dies kann man wie folgt modellieren:
s. t. ist hierbei eine Abkürzung für das Englische "subject to". Damit werden i. d. R. die Nebenbedingungen eingeleitet, da eine Lösung für die Optimierungsfunktion die Nebenbedingungen ebenfalls erfüllen muss. Das Feld unter max bzw. min gibt an, aus welchen Zahlenmengen die genutzten Variablen belegt werden können.
Mathematische Optimierung und Integer Programming werden in der Informatik hüfig angewendet, da sie eine gute Kombination aus menschenlesbaren Formeln sind, die trotzdem einfach in eine für einen computerlesbare Form gebracht werden können. Dabei spielt die Laufzeit, eine große Rolle.
Die Laufzeit beschreibt in der Informatik die Zeit, die ein Computer braucht, um das Ergebnis eines Programmes zu berechnen. Dabei gibt es verschiedene Werte, die eine Auskunft über die Laufzeit geben kann. Der häufigste Wert ist die Worst-Case-Laufzeit. Dieser gibt an, wie lange das Programm im schlimmsten Fall laufen muss, um ein Ergebnis zu berechnen. Ein weiterer interessanter Wert ist die Average-Case-Laufzeit, die angibt, wie lange das Programm im Durchschnitt läuft. Dabei können Worst-Case- und Average-Case-Laufzeit auch stark vonneinander abweichen, was für die praktische Anwendung einen erheblichen Unterschied machen kann.
Während die normale mathematische Optimierung effizient gelöst werden kann, ist Integer Programming im allgemeinen NP-Schwer[1]. NP-schwer bedeuted im Kontext des Integer-Programmings, dass es für den allgemeinen Fall keinen effizienten Algorithmus gibt, der das optimale Ergebnis berechnen kann. Da es beim Integer Programming keine Werte "zwischen" den einzelnen natürlichen Zahlen gibt heißt das, dass im Worst Case jede Wertkombination einmal ausprobiert werden muss.
Allerdings können spezielle Probleme durch programmiertechnische Kniffe eine deutlich bessere Average-Case-Laufzeit erreichen. Einer davon ist der "Branch and Bound"-Ansatz.
Bei diesem Ansatz wird zuerst das optimale Ergebnis für die normale mathematische Optimierung berechnet, ohne eine Festlegung auf ganzzahlige Werte zu machen. Danach wird durch iteratives Auf- oder Abrunden die optimale ganzzahlige Lösung gefunden.
Als praktischer Beispiel wird in [1] CPLEX genannt. Dieser kombiniert Branch and Bound mit weiteren Möglichkeiten zur Laufzeitverbesserung. In experimentellen Studien wurde berichtet, dass dadurch eine starke Laufzeitverbesserung, etwa um Faktor 3, erzielt wurde.
[1] M. Conforti, G. Cornuéjols, und G. Zambelli, Integer Programming, Bd. 271. in Graduate Texts in Mathematics, vol. 271. Cham: Springer International Publishing, 2014. doi: 10.1007/978-3-319-11008-0. Link
[2] H. Bigalke und K. Köhler, Mathematik – Sekundarstufe II: Leistungskurs, Berlin. Berlin, Deutschland: Cornelsen Verlag, o. J. Link
[3] IBM, „What is integer programming?“, IBM Documentation, Version 22.1.0. [Online]. Verfügbar unter: https://www.ibm.com/docs/en/icos/22.1.0?topic=problem-what-is-integer-programming. [Zugriff am: 18. Dez. 2025].