Hybrid LP/SDP Bounding Procedure

The principal idea of this paper is to exploit Semidefinite Programming (SDP) relaxation within the framework provided by Mixed Integer Nonlinear Programming (MINLP) solvers when tackling Binary Quadratic Problems (BQP). SDP relaxation is well-known to provide strong bounds for BQP in practice. However, the method is not typically implemented in many state-of-the-art MINLP solvers based on Linear Programming (LP) relaxation. This paper demonstrates that this idea could be computationally useful. The Quadratic Stable Set Problem (QSSP) is adopted as the case study. The tests indicate that the Hybrid LP/SDP Bounding Procedure allows a noticeable reduction of computing time and a cut of almost one order of magnitude for the branching nodes. Furthermore, we propose and test a new linearization technique which outperforms the standard one for many classes of QSSP instances.



View Hybrid LP/SDP Bounding Procedure