Gemischt-ganzzahlige lineare Optimierung

Gemischt-ganzzahlige lineare Optimierung

Gemischt-ganzzahlige Optimierung mit linearen Nebenbedingungen.

• Modellierung
• Gemischt-ganzzahliges lineares Optimierungsproblem

Beispiele für Gemischt-ganzzahlige lineare Optimierungsprobleme

• Uncapacitated Lot-Sizing Problem
• Capacitated Lot-Sizing Problem
• Traveling Salesman Problem
• Uncapacitated Facility Location Problem
• Knapsack Problem

Komplexität von MIPs

Erfüllbarkeitsproblem der Aussagenlogik

$\mathrm{SAT}$ ist in NPC

BIP ist NP, da eine Lösung in polynomieller Zeit verifiziert werden kann. Da man $SAT$ auf BIP polynomiell reduzieren kann ist BIP auch in NPC.

Es lässt sich zeigen, dass MIP auch in NP ist. Da man BIP auf MIP polynomiell reduzieren kann ist MIP auch in NPC.

LP ist in NP.