SCIP-SDP : SDPA 7.3.8 と SDPA 7.4.0

以下の SCIP-SDP 2.1.0 に SDPA をリンクして SDP の外部ソルバーとして利用することが可能である。

SCIP-SDP a mixed integer semidefinite programming plugin for SCIP

SCIP-SDP is a plugin for SCIP to solve mixed integer semidefinite programs (MISDPs). It combines the branch-and-bound framework of SCIP with interior-point SDP-solvers. It provides the data handling, some presolving and propagation as well as a reader for a modified sparse SDPA-format with additional lines for integrality constraints. It is possible to solve the resulting SDP-relaxations using a linear approximation procedure, but for full functionality one of the following SDP-solvers needs to be installed:
DSDP
SDPA

今回は SDPA 7.3.8 と SDPA 7.4.0 の違いで SCIP-SDP 2.1.0 の性能の違いが出るのか調べてみた。SDPA 7.4.0 を使用した方がかなり高速になっている。

◎ SCIP-SDP 2.1.0
◎ SDPA 7.3.8 or SDPA 7.4.0
◎ OpenBLAS 0.2.19dev

問題１：random_32_4_a.dat-s
◎SDPA 7.3.8
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 6.23
Solving Nodes : 20
Primal Bound : +1.26693009594114e+01 (2 solutions)
Dual Bound : +1.26693009594114e+01
Gap : 0.00 %

◎SDPA 7.4.0
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 3.07
Solving Nodes : 20
Primal Bound : +1.26693009594114e+01 (2 solutions)
Dual Bound : +1.26693009594114e+01
Gap : 0.00 %


問題２：bridge_2x5_5bars.dat-s
◎SDPA 7.3.8
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 17.34
Solving Nodes : 924
Primal Bound : +2.49705627484800e+00 (1 solutions)
Dual Bound : +2.49705627484800e+00
Gap : 0.00 %

◎SDPA 7.4.0
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 6.81
Solving Nodes : 924
Primal Bound : +2.49705627484800e+00 (1 solutions)
Dual Bound : +2.49705627484800e+00
Gap : 0.00 %


問題３：clique_20_k3_6_7.dat-s
◎SDPA 7.3.8
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 19.80
Solving Nodes : 220
Primal Bound : +1.46999986786081e+02 (1 solutions)
Dual Bound : +1.46999986786081e+02
Gap : 0.00 %

◎SDPA 7.4.0
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 5.46
Solving Nodes : 92
Primal Bound : +1.46999987743974e+02 (1 solutions)
Dual Bound : +1.46999987743974e+02
Gap : 0.00 %


◯計算サーバ
CPU : Intel(R) Xeon(R) CPU E5-2699 v3 @ 2.30GHz x 2 個
メモリ：512GB
OS : CentOS 7.2