Formulierung

Ein Polyeder $P$ ist eine Formulierung für eine gemischt-ganzzahlige Menge $X$, wenn gilt

Eine Formulierung $P_1$ ist besser als $P_2$, wenn gilt $P_{1} \subsetneq 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