Gemischt-ganzzahliges lineares Optimierungsproblem

Gemischt-ganzzahliges Optimierungsproblem

Ein Optimierungsproblem mit $x$ gemischt-ganzzahlig und linearen Nebenbedingungen

$$\begin{array}{rl}\min c^{\top }x& \\ & Ax\le b\\ & x\in {\mathbb{Z}}^p\times {\mathbb{R}}^{n-p}\end{array}$$

Spezialfälle

• $p=0$ → Linear Program
• $p=n$ → Integer Program
• $p=n$ und $x\in \{0,1{\}}^n$ → Binary Integer Program

Beispiele

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