A framework for solving mixed-integer semidefinite programs
A framework for solving mixed-integer semidefinite programs
复制标题
DOI：
10.1080/10556788.2017.1322081
复制
发表时间：
2018-01-01
影响因子：
2.2
通讯作者：
Ulbrich, Stefan
中科院分区：
文献类型：
--
作者：
Gally, Tristan;Pfetsch, Marc E.;Ulbrich, Stefan
混合整数半定规划在许多应用中都有出现，近年来研究了几种求解方法。在本文中，我们研究了一个通用的分支定界框架来解决这些问题。我们首先表明，严格的对偶的半定松弛继承的子问题。然后求解器组件，如双固定，分支规则，和原始算法。我们展示了所提出的方法对三种问题的实施的适用性。结果表明，不同的求解器组件的积极的计算影响，这取决于所使用的半定规划求解器。这表明可以使用通用求解器成功解决实际相关的MISDP。
Mixed-integer semidefinite programs (MISDPs) arise in many applications and several problem-specific solution approaches have been studied recently. In this paper, we investigate a generic branch-and-bound framework for solving such problems. We first show that strict duality of the semidefinite relaxations is inherited to the subproblems. Then solver components such as dual fixing, branching rules, and primal heuristics are presented. We show the applicability of an implementation of the proposed methods on three kinds of problems. The results show the positive computational impact of the different solver components, depending on the semidefinite programming solver used. This demonstrates that practically relevant MISDPs can successfully be solved using a general purpose solver.