2020年3月
A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems
Computational Optimization and Applications
- ,
- 巻
- 75
- 号
- 2
- 開始ページ
- 493
- 終了ページ
- 513
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1007/s10589-019-00153-2
- 出版者・発行元
- SPRINGER
We consider a cutting-plane algorithm for solving mixed-integer semidefinite optimization (MISDO) problems. In this algorithm, the positive semidefinite (psd) constraint is relaxed, and the resultant mixed-integer linear optimization problem is solved repeatedly, imposing at each iteration a valid inequality for the psd constraint. We prove the convergence properties of the algorithm. Moreover, to speed up the computation, we devise a branch-and-cut algorithm, in which valid inequalities are dynamically added during a branch-and-bound procedure. We test the computational performance of our cutting-plane and branch-and-cut algorithms for three types of MISDO problem: random instances, computing restricted isometry constants, and robust truss topology design. Our experimental results demonstrate that, for many problem instances, our branch-and-cut algorithm delivered superior performance compared with general-purpose MISDO solvers in terms of computational efficiency and stability.
- リンク情報
- ID情報
-
- DOI : 10.1007/s10589-019-00153-2
- ISSN : 0926-6003
- DBLP ID : journals/coap/KobayashiT20