Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/307497 
Year of Publication: 
2022
Citation: 
[Journal:] Journal of Global Optimization [ISSN:] 1573-2916 [Volume:] 84 [Issue:] 3 [Publisher:] Springer US [Place:] New York, NY [Year:] 2022 [Pages:] 591-606
Publisher: 
Springer US, New York, NY
Abstract: 
Cutting planes from the Boolean Quadric Polytope 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 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.
Subjects: 
Nonconvex quadratic programming
Linear relaxation
Chvátal–Gomory closure
Extended formulation
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.