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 A eine m \times n-Matrix, c eine n-dimensionaler Zeilenvektor, b ein m-dimensionaler Spaltenvekor und x ein n-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