Optimization Online


A Branch-and-Cut Algorithm for Solving Mixed-integer Semidefinite Optimization Problems

Ken Kobayashi (ken-kobayashi***at***jp.fujitsu.com)
Yuichi Takano (ytakano***at***sk.tsukuba.ac.jp)

Abstract: This paper is concerned with a cutting-plane algorithm for solving mixed-integer semidefinite optimization (MISDO) problems. In this algorithm, the positive semidefinite constraint is relaxed, and the resultant mixed-integer linear optimization problem is repeatedly solved with valid inequalities for the relaxed constraint. We prove 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 in the process of a branch-and-bound procedure. We test the computational performance of our cutting-plane and branch-and-cut algorithms for three types of MISDO problems: random instances, computing restricted isometry constants, and robust truss topology design. Experimental results demonstrate that for many problem instances, our branch-and-cut algorithm delivered superior performance compared with a general-purpose MISDO solver in terms of computational efficiency and stability.

Keywords: mixed-integer optimization, semidefinite optimization, cutting-plane algorithm, branch-and-cut algorithm

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

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

Category 3: Global Optimization


Download: [PDF]

Entry Submitted: 09/08/2018
Entry Accepted: 09/08/2018
Entry Last Modified: 06/24/2019

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