AMS Seminar: Jon Lee (University of Michigan) @ Whitehead 304
Title: Comparing relaxations via volume for nonconvex optimization
Abstract: Practical exact methods for global optimization of mixed-integer nonlinear optimization formulations rely on convex relaxation. Then, one way or another (via refinement and/or disjunction), global optimality is sought. Success of this paradigm depends on balancing tightness and lightness of relaxations. We will investigate this from a mathematical viewpoint, comparing polyhedral relaxations via their volumes. Specifically, I will present some results concerning: fixed charge problems, vertex packing in graphs, boolean quadratic formulations, and convexification of monomials in the context of spatial branch-and-bound” for factorable formulations. Our results can be employed by users (at the modeling level) and by algorithm designers/implementers alike.