Formulierung

Ein Polyeder $P$ ist eine Formulierung für eine gemischt-ganzzahlige Menge $X$, wenn gilt $X=P\cap ({\mathbb{Z}}^p\times {\mathbb{R}}^{n-p})$ Eine Formulierung $P_1$ ist besser als $P_2$, wenn gilt $P_1⊊P_2$, da der optimale Zielfunktionswert von $P_1$ näher an dem echten optimalen Wert von $X$ ist.

Für rationale MIPs ist die konvexe Hülle von $X$ die beste Formulierung.

Beispiele