Konstruktionsheuristik

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

Heuristiken, die anhand eines BIP:

$\min \left\{c^{\top }x:x\in X\right\},X=\left\{x\in \{0,1{\}}^n:Ax\ge b\right\}$ mit LP-Relaxierung $\min \left\{c^{\top }x:x\in P\right\},P=\left\{x\in [0,1{]}^n:Ax\ge b\right\}$ arbeitet.

• Tauchheuristik
  • Dive-and-Fix
• Feasibility Pump