A POLYHEDRAL APPROACH FOR NONCONVEX QUADRATIC-PROGRAMMING PROBLEMS WITH BOX CONSTRAINTS

We apply a linearization technique for nonconvex quadratic problems wi th box constraints. We show that cutting plane algorithms can be desig ned to solve the equivalent problems which minimize a linear function over a convex region. We propose several classes of valid inequalities of the convex region which are closely related to the Boolean quadric polytope. We also describe heuristic procedures for generating cuttin g planes. Results of preliminary computational experiments show that o ur inequalities generate a polytope which is a fairly tight approximat ion of the convex region.