Konstruktionsheuristik

Heuristik, die möglichst schnell eine (gute) zulässige Lösung findet.

Heuristiken, die anhand eines BIP:

min⁡{c⊤x:x∈X},X={x∈{0,1}n:Ax≥b}\min \left\{c^{\top} x: x \in X\right\}, \quad X=\left\{x \in\{0,1\}^{n}: A x \geq b\right\}

mit LP-Relaxierung

min⁡{c⊤x:x∈P},P={x∈[0,1]n:Ax≥b}\min \left\{c^{\top} x: x \in P\right\}, \quad P=\left\{x \in[0,1]^{n}: A x \geq b\right\}

arbeitet.