Cuts and heuristics for nonconvex quadratic optimization
1 : Gurobi Optimization
Solving nonconvex quadratic optimization problems to global optimality is a challenging task. For this problem class Gurobi takes a branch-and-bound approach, so the building blocks for the solver are: A relaxation of the problem to solve at the nodes, cutting planes to reduce the feasible region of the relaxation, and heuristics to compute primal feasible solutions. Here we discuss the latter two building blocks in more detail, focussing on so-called PSD cuts, and a heuristic based on an interior point method.