Solving Standard Quadratic Programming By Cutting Planes
Speaker:
Andrea Lodi, Polytechnique Montréal
Date and Time:
Wednesday, July 5, 2017 - 3:30pm to 4:00pm
Location:
Fields Institute, Room 230
Abstract:
Standard quadratic programs are non-convex quadratic programs with the only constraint that variables must belong to a simplex. By a famous result of Motzkin and Straus, those problems are connected to the clique number of a graph. We propose cutting planes to obtain strong bounds: our cuts are derived in the context of Spatial Branch & Bound, where linearization variables represent products. Their validity is based on Motzkin-Straus result. We study the relation between these cuts and the ones obtained by the first RLT level. We present extensive computational results using the cuts in the context of the Spatial Branch & Bound implemented by the commercial solver CPLEX.