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

Sven de Vries () and Bernd Perscheid ()
Additional contact information
Sven de Vries: Trier University
Bernd Perscheid: Trier University

Journal of Global Optimization, 2022, vol. 84, issue 3, No 3, 606 pages

Abstract: Abstract Cutting planes from the Boolean Quadric Polytope can be used to reduce the optimality gap of the $$\mathcal {NP}$$ NP -hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chvátal–Gomory closure of the Boolean Quadric Polytope are A-odd cycle inequalities. We obtain a compact extended relaxation of all A-odd cycle inequalities, which allows to optimize over the Chvátal–Gomory closure without repeated calls to separation algorithms and has less inequalities than the formulation provided by Boros et al. (SIAM J Discrete Math 5(2):163–177, 1992) for sparse matrices. In a computational study, we confirm the strength of this relaxation and show that we can provide very strong bounds for the BoxQP, even with a plain linear program. The resulting bounds are significantly stronger than these from Bonami et al. (Math Program Comput 10(3):333–382, 2018), which arise from separating A-odd cycle inequalities heuristically.

Keywords: Nonconvex quadratic programming; Linear relaxation; Chvátal–Gomory closure; Extended formulation (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01157-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:84:y:2022:i:3:d:10.1007_s10898-022-01157-9

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-022-01157-9

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().