Seminar by Vishnu Narayanan
On the structure of integer hulls of convex sets
Vishnu Narayanan
IIT Bombay
Date: Wednesday, February 5th, 2014
Time: 15:30 PM
Venue: CS101.Abstract:
Convex Integer Programming is an emerging area of research at present. However, several fundamental questions about the structure of these problems are still open. Here, we make an attempt to address some of these questions. For a convex set S, we study the facial structure of its integer hull, SZ. Crucial to our study is the decomposition of the integer hull into the convex hull of its extreme points, conv(ext(SZ)), and its recession cone. Although conv(ext(SZ)) might not be a polyhedron, or might not even be closed, we show that it shares several interesting properties with polyhedra: all faces are exposed, perfect, and isolated, and maximal faces are facets. We show that SZ has an infinite number of extreme points if and only if conv(ext(SZ)) has an infinite number of facets. Using these results, we provide a necessary and sufficient condition for semidefinite representability of conv(ext(SZ)).