Colloquium Mathematics - Dr. Tony Huynh (ULB, Belgium)

Title:
Strengthening Convex Relaxations of 0/1-Sets Using Boolean Formulas

Abstract:
In integer programming, various procedures have been developed to strengthen relaxations of sets of integer points. On the one hand, there exist several general-purpose methods that strengthen relaxations without specific knowledge of the set S of feasible integer points, such as popular linear programming or semi-definite programming hierarchies. On the other hand, various methods have been designed for obtaining strengthened relaxations for very specific sets S that arise in combinatorial optimization.

We propose a new and extremely simple method that interpolates between these two approaches. Our procedure strengthens any convex set containing a set S of 0/1-points by exploiting certain additional information about S. Namely, the required extra information will be in the form of a Boolean formula F defining the target set S. The new relaxation is obtained by ''feeding'' the convex set into the formula F.

We finish by giving several applications of our method.  No knowledge of combinatorial optimization or circuit complexity will be assumed.

This is joint work with Samuel Fiorini and Stefan Weltge.

Colloquium coordinators are Prof.dr. A.J. van der Schaft (a.j.van.der.schaft rug.nl), Dr. A.V. Kiselev (e-mail: a.v.kiselev rug.nl)