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

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.

Article

Download

View PDF