A framework for solving mixed-integer semidefinite programs. (4th May 2018)

• Record Type: Journal Article
• Authors: Gally, Tristan; Pfetsch, Marc E.; Ulbrich, Stefan
• Is Part Of: Optimization methods and software. Volume 33:Number 3(2018)
• Page Start: 594
• Page End: 632
• Publication Date: 2018-05-04
• Subjects: mixed-integer semidefinite programming -- branch-and-bound -- strong duality -- dual fixing -- branching rules; 90C11 -- 90C22; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1322081
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : 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.