Eigendecomposition-based reformulations for convex MINLP in the SHOT solver

In this extended abstract, we describe how the SHOT solver utilizes
eigendecomposition to perform a lifted reformulation for convex mixed-integer problems with non-separable quadratic expressions. An eigenvalue decomposition is first performed on the non-diagonal matrices defining quadratic expressions in the problem, and is used for transforming the quadratic expressions into convex additively separable constraints. The resulting additively separable constraints are then further lifted into a form where SHOT generates polyhedral outer approximations of convex quadratic univariate functions. The reformulations have been integrated into SHOT’s automatic problem reformulation functionality.