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

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 Chvatal-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 Chvatal-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.

Automated summary

This paper investigates the use of cutting planes from the Boolean Quadric Polytope to reduce the optimality gap of the NP-hard nonconvex quadratic program with box constraints (BoxQP). By obtaining a compact extended relaxation of all A-odd cycle inequalities, optimization over the Chvatal-Gomory closure can be achieved without repeated calls to separation algorithms and with fewer inequalities. Computational studies confirm the strength of this relaxation and demonstrate that strong bounds can be obtained for the BoxQP, even with a plain linear program, which are significantly stronger than those obtained using heuristic separation of A-odd cycle inequalities by Bonami et al. (Math Program Comput 10(3):333-382, 2018).