0-1 変数に Sum of Squares を使ってみると

$x \in \{0,1\}$ という制約条件は、普通に連続緩和をすると $ 0 \le x \le 1$ になる。

これを、$-x^2(x-1)^2 \ge 0$ として、Sum of Squares の緩和をするとどうなるか。

得られる緩和は $ 0 \le x \le 1$ となって、連続緩和と強さが変わらない。

なるほど、なるほど。なかなかに面白い結果だ。