binary quadratic problem

Hybrid LP/SDP Bounding Procedure

  • Fabio Furini
  • Emiliano Traversi
    • Categories Quadratic Programming, Semi-definite Programming Tags , , , ,

    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 … Read more

    Second-Order Cone Relaxations for Binary Quadratic Polynomial Programs

  • Miguel F. Anjos
  • Bissan Ghaddar
  • Juan C. Vera
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    Several types of relaxations for binary quadratic polynomial programs can be obtained using linear, second-order cone, or semidefinite techniques. In this paper, we propose a general framework to construct conic relaxations for binary quadratic polynomial programs based on polynomial programming. Using our framework, we re-derive previous relaxation schemes and provide new ones. In particular, we … Read more