(260a) Spectral Outer-Approximation Algorithms for Binary Semidefinite Problems

Integer semidefinite programming (ISDP) has recently gained attention due to its connection to binary quadratically constrained quadratic programs (BQCQPs), which can be exactly reformulated as binary semidefinite programs (BSDPs)¹. These reformulations offer new modeling opportunities for process and energy systems applications, where nonconvex and combinatorial structures are commonly modeled as mixed-integer nonlinear programs (MINLPs)². However, existing ISDP solvers are general-purpose and do not exploit the specific structure of BSDPs derived from BQCQPs.

In this work, we propose a novel spectral outer approximation algorithm tailored for BSDPs derived from BQCQP reformulations. Our approach is inspired by polyhedral and second-order representable regions that outer approximate the feasible set of a semidefinite program relying on a spectral decomposition of a matrix that simultaneously diagonalizes the objective matrix and an aggregation of the constraint matrices. We benchmark our approach on a collection of BSDPs reformulated from representative BQCQPs. Computational experiments demonstrate that our method is competitive with, and in some cases outperforms, state-of-the-art ISDP solvers such as SCIP-SDP³ and PAJARITO^4,5 in both runtime and solution quality. The results suggest that integer semidefinite programming is a promising framework for solving binary quadratic problems and offers a viable computational alternative to conventional global MINLP solvers. Our algorithm opens new directions for scalable, structure-exploiting ISDP methods and contributes to the broader development of integer conic optimization.

Reference:

[1] De Meijer, F., & Sotirov, R. (2024). On integrality in semidefinite programming for discrete optimization. SIAM Journal on Optimization, 34(1), 1071-1096.

[2] Grossmann, I. E., & Kravanja, Z. (1995). Mixed-integer nonlinear programming techniques for process systems engineering. Computers & chemical engineering, 19, 189-204.

[3] Gally, T., Pfetsch, M. E., & Ulbrich, S. (2018). A framework for solving mixed-integer semidefinite programs. Optimization Methods and Software, 33(3), 594-632.

[4] Lubin, M., Yamangil, E., Bent, R., & Vielma, J. P. (2018). Polyhedral approximation in mixed-integer convex optimization. Mathematical Programming, 172, 139-168.

[5] Coey, C., Lubin, M., & Vielma, J. P. (2020). Outer approximation with conic certificates for mixed-integer convex problems. Mathematical Programming Computation, 12(2), 249-293.