cplex が思っていた以上に時間がかかる

SOCP 付きの整数計画問題で厳密解がどうなっているかを知るために、あまり深く考えずに cplex にお任せしたら、想定以上に時間がかかっていることに気がついた。

変数の数は、0-1 変数が 1000, 連続変数も 1000 で、0-1 変数を 0<=x<=1 に緩和した SOCP は 0.1 秒もかからずに解けるので、それほど大きい問題ではないかと思い、そのまま cplex に丸投げしてある。

今のところ CPU 使用率が 1500% 程度を 24 時間ぐらいやってみて、上界と下界の差が 0.2% から縮まらない状態である。

分枝限定法での限定が上手くできないタイプの問題なのかもしれないが、もう少し定式化もいじってみようと思う。