Concave Quadratic Cuts for Mixed-Integer Quadratic Problems

By Jaehyun Park, Stephen P. Boyd. 2015

5 citations recorded by the source corpus.

The technique of semidefinite programming (SDP) relaxation can be used to obtain a nontrivial bound on the optimal value of a nonconvex quadratically constrained quadratic program (QCQP). We explore concave quadratic inequalities that hold for any vector in the integer lattice Z n , and show that adding these inequalities to a mixed-integer nonconvex QCQP can improve the SDP-based bound on the optimal value. This scheme is tested using several numerical problem instances of the max-cut problem and the integer least squares problem.

Subfields: Computer Graphics and Computer-Aided Design, Industrial and Manufacturing Engineering, Numerical Analysis