(251d) A Branch and Cut Solver for Mixed-Integer Semidefinite Programming: New Sparse Cutting Planes

Mixed-integer semidefinite programs (MISDPs) arise in a variety of areas: power systems engineering, compressed sensing and truss topology design, to name a few. The solution of these problems can also provide tight lower bounds to several mixed-integer non-convex quadratically constrained quadratic programming problems that abound in chemical engineering. Only a few solvers and algorithms are currently available to solve MISDPs.

Existing nonlinear branch and bound approaches entail solving semidefinite programs (SDPs) for lower bounding. The SDPs themselves are solved using interior point algorithms. A main drawback of the approach, referred to here as BB-SDP, is that interior point solvers have limited warm-starting capabilities. Further, guaranteed convergence of the interior point methods requires the satisfaction of Slater’s constraint qualification, which may be violated for some problems. Large-scale SDPs are prone to numerical issues and nonconvergence.

In contrast, branch and cut methods entail the solution of linear programs (LP) for lower bounding. These class of methods, referred to here as BC-LP, involve the generation of cutting planes based on the eigenvalue and eigenvector of the matrix that is required to be positive semidefinite. While LPs have far superior scalability and warm starting abilities than SDPs, branch and cut methods can also be slow in practice. This is because a large number eigenvalue-based cutting planes may be required for problem convergence. These cuts decelerate LP solutions as these are high-dimensional and very dense (with few non-zero coefficients).

In this work, we address this drawback in the BC-LP approach to solve MISDPs. We exploit the aggregate sparsity of the data matrices of MISDP (in the primal form) using the decomposition framework of Fukuda et al. [1]. A chordal extension of the aggregate sparsity pattern of the MISDP is first built, which then allows the positive semidefiniteness (PSD) constraint to be decomposed into a number of equivalent lower-dimensional PSD constraints. We generate lower dimensional eigenvalue-based cutting planes that correspond to each of these lower-dimensional PSD constraints.

GravitySDP, an MISDP solver based on sparse eigenvalue-based cutting planes, is implemented in C++ within the open-source modelling and optimization platform Gravity. The lower-dimensional PSD constraints are enforced in a lazy fashion via cutting planes that are progressively added to a mixed-integer linear program (MILP). The MILP is solved in this study using the state-of-the-art solver, Gurobi [2].

We illustrate the technique by comparing the performance of BC-LP with sparse cuts vs dense cuts for MISDPs. GravitySDP, with sparse cuts, is particularly effective when the problem aggregate sparsity pattern is near chordal. We also benchmark the performance of our sparse MISDP solver against the state-of-the-art BB-SDP solver, SCIP-SDP [3]. We find that our approach, on average, outperforms the branch and bound technique for MISDPs that arise in the design of truss topology.

References:

1. Mituhiro Fukuda, Masakazu Kojima, Kazuo Murota, and Kazuhide Nakata. Exploiting sparsity in semidefinite programming via matrix completion i: General framework. SIAM Journal on Optimization, 11(3):647–674, 2001
2. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual. 2024. https://www.gurobi.com
3. Frederic Matter and Marc E. Pfetsch. Presolving for mixed-integer semidefinite optimization. INFORMS Journal on Optimization, 5(2): 131-232, 2022