QAPLIB と SDP 緩和

QAPLIB に　Esc64a という問題があって、現時点での最良の上界は 116 になっている。詳しくは添付の図を参考にしていただきたいが、上界の値 116 は Simulated Annealing で求められているが、下界の値　105 は SDP 緩和で今回求めることが出来た。
ただし、この SDP 緩和問題は非常に数値的な性質が悪い。SDPA, CSDP, SDPT3, SeDuMi では最適解を求めることが出来なかった(添付の図を参照)。ただし SDPA-DD では高精度で最適解を求めることが出来た。もちろん SDPA-QD, SDPA-GMP でも可能だが、実行速度から判断すると SDPA-DD がお勧めとなる。