Pseudo-Boolean Constraints

Idee:

• Klausel: v₁ $\vee$ $\overline{v}_{2}^{}$ $\vee$ v₃
• Ungleichung: v₁ + $\overline{{v_2}}$ + v₃$\ge$1

pseudo-Boolesches Constraint (PBC) ist Ungleichung

c₁v₁ +...+ c_nv_n$$\ge$$d,

mit Koeffizienten c₁,..., c_n, d $\in$ $\mathbb {Z}$ für Unbekannte v₁,...$\in$ $\mathbb {B}$ = {0, 1}.

PBC-Optimierungsaufgabe: Menge von PBC und Zielfunktion z₁v₁ +...+ z_nv_n

Lösung davon ist Belegung, die alle Constraints erfüllt und Zielfunktion maximiert.