Optimization Online


A Framework for Solving Mixed-Integer Semidefinite Programs

Tristan Gally(gally***at***mathematik.tu-darmstadt.de)
Marc E. Pfetsch(pfetsch***at***mathematik.tu-darmstadt.de)
Stefan Ulbrich(ulbrich***at***mathematik.tu-darmstadt.de)

Abstract: Mixed-integer semidefinite programs 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 like 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 mixed-integer semidefinite programs can successfully be solved using a general purpose solver.

Keywords: mixed-integer semidefinite programming; branch-and-bound; strong duality; dual fixing; branching rules

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Optimization Software and Modeling Systems


Download: [PDF]

Entry Submitted: 04/05/2016
Entry Accepted: 04/05/2016
Entry Last Modified: 04/05/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society