GuBoLi — The World’s Greatest Solver for Box-Constrained Nonconvex Quadratic Programs

I will first explain to you the standard methodology for finding globally optimal solutions to nonconvex quadratic programs. I then will tell you a couple simple tricks, inspired by integer programming, that can speed up these algorithms by multiple orders of magnitude. If time allows, I can discuss a result of theoretical interest that we use indirectly in our implementation. Specifically, we demonstrate the equivalence of the Chvatal-Gomory closure of the linear system defining the (sparse) Boolean Quadric Polytope and its “Odd-Cycle” closure.

Regardless of how much material I cover, I will stop talking promptly at 4:30PM, since as Rob so eloquently puts it, “Summer SILO is really about the beer.”

Joint with Oktay Guluk and Pierre Bonami (IBM). (Hopefully you can now get the joke about the name of our software. If not, see http://gurobi.com).