MIP に対する LP & SDP 緩和

MIP（混合整数計画問題) の解法において LP(線形計画) 緩和問題を用いるというのは普通の発想であり、実際に多くのMIP ソルバーで採用されている。この LP 緩和問題の代わりに SDP (半正定値計画)緩和問題を使うとどうなるのかについては、今までにも様々な研究が行われている。ただし、理論的研究かつ小さな規模の問題での実験なので、高度に発達してきた現在の SDP ソルバーと分枝限定法の大規模な並列実装技術と組み合わせるとどうなるのかについては、まだ未知の領域となる。
一般論で言うと、

緩和値の良さ： SDP 緩和; 良い > LP 緩和; 悪い
実行時間： LP 緩和; 速い > SDP 緩和; 遅い

となる。SDP 緩和問題を解くには時間がかかるので、同じ時間で LP 緩和問題を何回も解けば同程度以上の精度の解が得られる可能性があるが、これは様々な要因が絡むので何とも言えない。一つ言えることは、ある MIP に対しては最適な LP 緩和問題と SDP 緩和問題の組み合わせがあるということである。以前から非凸最適化問題に対しては、

一つの SDP 緩和問題 v.s. 複数の LP 緩和問題(いわゆる CPA (Cutting Plane Algorithm))

という戦いがあるが、同時間内の実行では後者が優勢である事が多かったように記憶している。一方、分枝限定法の大規模な並列実行環境では、同時に以下の三つのソルバーの選択と組み合わせが考えられる。

1: MIP ソルバー(子問題において整数変数の多くが固定された状態であれば、MIP ソルバーで子問題を最適に解いてしまう）
2: LP ソルバー(子問題が大きなとき)
3: SDP ソルバー(子問題の大きさ的には 1 と 2 の中間ぐらい)

SDP 緩和問題についてだが、LP は SDP に含まれる(線形等式＆不等式の制約は SDP に組み込むことができる)ので、非負かつ半正定値(DNN : doubly non‐negative)制約を含んだ SDP 緩和問題を作ることができる。この緩和問題は非常に強力だが、問題の規模が巨大になるという弱点があるので、主双対内点法の枠組みで解くのはかなり厳しい。しかし、一度 DNN 制約付き SDP 緩和問題を解いてから、分枝するようにしていけば、大きな MIP も意外と速く解けてしまうという可能性がある。なぜならば、DNN 制約付き SDP 緩和問題の最適解を最も近い整数値にシフトすると、それが本来の MIP の最適解にかなり類似しているという性質が見られるからである。
実現のためには解決すべき課題がたくさんあるが、可能性も大きそうである。