Optimization Online


Tight compact extended relaxations for nonconvex quadratic programming problems with box constraints

Sven de Vries (devries***at***uni-trier.de)
Bernd Perscheid (perscheid***at***uni-trier.de)

Abstract: Cutting planes from the Boolean Quadric Polytope (BQP) can be used to reduce the optimality gap of the NP-hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chvátal-Gomory closure of the BQP are A-odd cycle inequalities. We obtain a compact extended relaxation of all A-odd cycle inequalities, which permits to optimize over the Chvátal-Gomory closure without repeated calls to separation algorithms. In a computational study, we verify the strength of this relaxation and show that we can provide very strong bounds for the BoxQP, even with a plain linear program.

Keywords: Nonconvex quadratic programming, Linear relaxation, Chvátal-Gomory closure, Extended formulation

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Combinatorial Optimization (Graphs and Matroids )


Download: [PDF]

Entry Submitted: 09/05/2019
Entry Accepted: 09/05/2019
Entry Last Modified: 09/06/2019

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