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.
View Tight compact extended relaxations for nonconvex quadratic programming problems with box constraints