北大・日立新概念コンピューティングコンテスト2018の参考文献を読んだのでコンテストに関係ありそうなところを雑にまとめました。

Reduction by substitution

$x_1 x_2$ を $w$ に置換することで次元を下げることを考えます。この時、元の数式を $x_1 x_2$ に依存する部分と依存しない部分に分けると、

$f(x)=x_1 x_2 A(x)+B(x)$

と書けます。 $w$ について最小化した時に $w=x_1 x_2$ が満たされるように、ペナルティ項のついた形に書き換えて

$\tilde{f}(x;w)=wA(x)+B(x)+Mp(x_1,x_2;w)$

となるような定数 $M$ と高々2次の多項式 $p$ を探します。これは $M$ がとても大きく、 $p$ が $w=x_1 x_2$ の時だけ0でそれ以外は正となれば良いです。具体的には $M$ が $A$ の絶対値の最大値より大きく、

$p(x;w)=x_1 x_2 -2x_1 w-2x_2 w+3w$

とすれば良いです。

Reducing negative-coefficient terms

係数が負の項については以下の式で次元を下げることができます。

$-x_1x_2\cdots x_d = \min_{w \in \{0,1\}} w\left((d-1)- \sum_{j=1}^{d} x_j \right)$

左辺が0の時は $\min$ の中が0以上となるので、 $w$ は0となり両辺が一致します。左辺が-1の時は $\min$ の中が-1となるので、 $w$ は1となり両辺が一致します。

Higher-order clique reduction

$x_1 x_2 x_3$ の次元を良い感じに下げることを考えます。元の式が対称式なので、変形後も $x$ についての対称式になっているものを考えます。変形後は高々2次なので $S_1=x_1+x_2+x_3$ と $S_2=x_1 x_2+x_2 x_3+x_3 x_1$ だけ考慮すれば良いです。頑張って探すと、

$x_1 x_2 x_3 = \min_w w(-S_1 +1 ) + S_2$

であることが分かります。同様にして4次の場合は、

$x_1 x_2 x_3 x_4= \min_w w(-2S_1 +3 ) + S_2$

となります。5次の場合はこのままではできませんが、追加する変数を増やすことにより

$x_1 x_2 x_3 x_4 x_5 = \min_{v,w} (v(-2S_1 +3) + w(-S_1 + 3 ) ) + S_2$

とできます。一般化すると、 $n_d=\left\lfloor \frac{d-1}{2} \right\rfloor$ として、次数が偶数の時は

$x_1 \cdots x_d = \min_w \sum_{i=1}^{n_d} w_i(-2S_1 +4i-1 ) + S_2$

であり、次数が奇数の時は

$x_1 \cdots x_d = \min_w \left( \sum_{i=1}^{n_d-1} w_i(-2S_1 +4i-1 ) + w_{n_d}(-S_1+2n_d-1)\right) + S_2$

とできます。

Splitting of common parts

ここまでは項を一つずつ潰していましたが、ここではある変数を含む項について一気に次数を下げることを考えます。 $x_1$ を含む項のうち、係数が正のものを全部持ってきて

$\sum_{H \in \mathcal{H}} \alpha_H \prod_{j \in H} x_j = \min_{y \in \{0,1\}} \left( \left( \sum_{H \in \mathcal{H} } \alpha_H \right) x_1 y + \sum_{H \in \mathcal{H}} \alpha_H \prod_{j \in H \backslash \{1\}} x_j - \sum_{H \in \mathcal{H}} \alpha_H y \prod_{j \in H \backslash \{1\}} x_j \right)$

とすると、 $\min$ の中の第3項だけ次数が下がってないんですが、これは係数が負になるので前に紹介した方法で解決します。この式は Alexander Fix et al. (2011) のFigure 2を見るとイメージが分かって、 $x_1$ のとる値で場合分けしていて、 $x_1=0$ には $y=1$ が対応して、 $x_1=1$ には $y=0$ が対応します。