On September 21, 2018 at 10:00 in room no. 641 prof. Ruth Misener from the Imperial College London will deliver a scientific talk on Learning-based Cutting Plane Approximation of Quadratic Programming Convex (SDP) Relaxations.
Speaker: prof. Ruth Misener, Imperial College, UK
Title: Learning-based Cutting Plane Approximation of Quadratic Programming Convex (SDP) Relaxations
Date, time, place: September 21, 2018, 10:00, room no. 641 (6th floor, B block)
Convex and in particular semidefinite relaxations (SDP) for non-convex continuous quadratic optimization can provide tighter bounds than traditional linear relaxations. However, using SDP relaxations directly in Branch-&-Cut is impeded by lack of warm starting and inefficiency when combined with other cut classes, i.e. the reformulation-linearization technique. We present a general framework based on machine learning for a strong linear outer-approximation that can retain most tightness of such SDP relaxations, in the form of few strong low dimensional linear cuts selected offline. The cut selection complexity is taken offline by using a neural network estimator (trained before installing solver software) as a selection device for the strongest cuts. Lastly, we present results of our method on several non-convex application problems. This is joint work with with Radu Baltean-Lugojan (Imperial), Pierre Bonami (IBM CPLEX), and Andrea Tramontani (IBM CPLEX).