Best ellipsoidal relaxation to solve a nonconvex problem. (Q1421225)

The author presents an ellipsoidal relaxation of the problem \[ (P)\quad\min\{\frac{1}{2}x^{T}Ax+b^{T}x\mid x\in\{0,1\}^{n}\} \] where \(A\) is an \(n\times n\) symmetric matrix. He shows that the problem \((P)\) and its dual are strictly feasible; so strong duality holds. The numerical results presented indicate the fact that the discribed relaxation is efficient.