We describe a method to generate cutting planes for quadratically constrained optimization problems. The method uses information from the simplex tableau of a linear relaxation of the problem in combination with McCormick estimators. The method is guaranteed to cut off a basic feasible solution of the linear relaxation that violates the quadratic constraints in the problem as long as finite bounds on all variables are available. These cutting planes are computationally cheap, and do not require any special structure in the input problem. The cuts generated by the method are the well-known Reformulation Linearization Technique (RLT) cuts. The procedure produces a large number of violated cuts. Several variants for selecting good cuts are tested. Instead of adding many cuts, one can also add auxiliary variables and a few cuts. Computational testing on benchmark test instances shows that on an average upto 30% of gap from the optimal can be closed.
Article
View Cutting planes from the simplex tableau for quadratically constrained optimization problems