¶ Integer-Programming
Laut Wolsey geht es beim Integer Programming darum Optimierungsprobleme mit diskreten oder ganzzahligen Variablen zu lösen. Solche Variablen werden verwendet um Unteilbarkeit zu modellieren, und binäre Variablen(0/1) werden verwendet um ja/nein Entscheidungen zum Kauf, zur Investition, zur Einstellung und weiterem darzustellen. Probleme wie diese treten in allen Lebensbereichen auf, unter anderem bei der Entwicklung von Fahr/-Flugpläne für Züge und Flugzeuge, bei der Erstellung von Arbeitsplänen in einer Produktionslinie oder eines Wartungsteams, oder in der Planung der täglichen oder wöchentlichen Stromerzeugung auf nationaler oder regionaler Ebene.[1] Integer Programming ist im Deutschen auch als ganzzahlige lineare Optimierung bekannt.
¶ Beispiel
Dabei ist eine -Matrix, eine -dimensionaler Zeilenvektor, ein -dimensionaler Spaltenvekor und ein -dimensionaler Spaltenvekor aus Variablen und Unbekannten.[1:1]
¶ Sonderform: Binary-Integer-Programming
Beim Binary-Integer-Programming ist der Wertebereich der Variablen auf 0 und 1 beschränkt. Es eignet sich deshalb hervorragend zur Modellierung allgemeiner Logik-Probleme.
¶ Modellierung von Bedingungen
Die wahrscheinlich wichtigste Bedingung im Binary-Integer-Programming sieht folgendermaßen aus.
Sie modelliert eine logische Formel der Form:
Man kann mit Binary-Integer-Programming jede Aussagenlogische Formel lösen, da man diese über das Sequenzkalkül in (möglicherweise mehrere) Formeln der oben genannten Form bringen kann.
Beispiel:
Ausgangsformel:
Ableitung durch Sequenzkalkül:
Resultierende Bedingungen:
¶ Referenzen und Arbeitsaufteilung
Einleitung und allgemeines IP Beispiel: Dominik Milas
Sonderform: Binary-Integer-Programming: Valentin Stöcker