組み合わせ最適化問題でSDPがLPよりも厳密な下界値(最小化問題の場合)を計算できるのに、分枝限定法であまり用いられないのには、単純にLPよりも計算時間が必要というだけでなく、SDPを解くのに使う内点法は制約を追加して解き直すのが難しいというのもあるのかな、と思った。
LPの場合の主流のアルゴリズムは単体法とバリア(内点法の一種)だけれど、単体法は制約を追加して解き直すのが(双対単体法を使って)容易にできるという利点があるので、LP緩和を用いた分枝限定法では、バリアを使うのは通常はルートノードだけで、木の途中のノードは単体法で解くのが普通。
専門家でないのでよく分かっていないけれど、バリアで単体法と同じ事ができないという特徴が内点法一般のものであれば、SDPが分枝限定法であまり使われないのも理解できる。
参考:
A Brief History of Linear and Mixed-Integer Programming Computation
<http://www.gurobi.com/pdf/a-brief-history-of-optimization.pdf>
In addition, the vast majority of LPs that are solved from scratch in practice are the root solves of MIPs, and a basis is then essential to exploit the advanced-start capabilities of simplex algorithms in the branch-and-bound (or now more correctly, branch-and-cut) search tree. Using barrier algorithms within the tree is generally impractical.