Decomposition-Based Reformulation of Nonseparable Quadratic Expressions in Convex MINLP

In this paper, we present a reformulation technique for convex mixed-integer nonlinear programming (MINLP) problems with nonseparable quadratic terms. For each convex non-diagonal matrix that defines quadratic expressions in the problem, we show that an eigenvalue or LDLT decomposition can be performed to transform the quadratic expressions into convex additively separable constraints. The reformulated problem type is more suitable for a polyhedral outer approximation (POA)-based MINLP solver such as the Supporting Hyperplane Optimization Toolkit (SHOT). Results from computational experiments on MINLPLib instances and generated test problems indicate enhanced performance with these reformulations on convex MINLP problems with dense quadratic structures when SHOT utilizes MIP subsolvers without quadratic support, such as Cbc and HiGHS.

Article

Download

View PDF