Optimization Online


Hybrid LP/SDP Bounding Procedure

Fabio Furini (fabio.furini***at***lipn.univ-paris13.fr)
Emiliano Traversi (emiliano.traversi***at***math.tu-dortmund.de)

Abstract: 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.

Keywords: Binary Quadratic Problem, Semidefinite Relaxation, Continuous Relaxation, Branch and Cut, Quadratic Stable Set Problem

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 10/24/2012
Entry Accepted: 10/24/2012
Entry Last Modified: 10/24/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society