In this paper a general framework to construct conic relaxations for binary quadratic polynomial programs (BQPP) based on polynomial programming is proposed.
BQPP is a classical combinatorial problem. It is of the form: \[ (\text{BQPP})\;\max x^T Qx+ p^T x, \]
\[ \text{s.t. }a^T_j x= b_j,\quad\forall j\in\{1,\dots, t\}, \]
\[ c^T_j x\leq d_j,\quad\forall_j\in \{1,\dots, u\}, \]
\[ x^T F_J x+ e^T_jx= k_j,\quad\forall_j\in \{1,\dots, v\}, \]
\[ x^T G_J x+ h^T_J x\leq l_j,\quad\forall_j\in \{1,\dots, w\}, \]
\[ x_i\in \{-1,1\},\quad\forall_i\in \{1,\dots, n\}. \] The proposed approach allows to re-derive previous relaxation schemes and provides new ones.
From the authors’ abstract: “In particular, we present three relaxations for binary quadratic polynomial programs. The first two relaxations, based on second-order cone and semidefinite programming, represent a significant improvement over previous practical relaxations for several classes of nonconvex binary quadratic polinomial problems. From a practical point of view, due to the computational cost, semidefinite based relaxations for binary quadratic polynomial problems can be used to solve small to midsize instances. To improve the computational efficiency for solving such problems, we propose a third relaxations based purely on second-order cone programming. Computational tests on different classes of nonconvex binary quadratic polynomial problems, including quadratic knapsack problems, show that the second-order-cone-based relaxation outperforms the semidefinite-based relaxations that are proposed in the literature in terms of computational efficiency, and it is comparable in terms of bounds.”