Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Facial Structure and Representation of Integer Hulls of Convex Sets
verfasst von : Vishnu Narayanan
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
For a convex set
S
, we study the facial structure of its integer hull,
S
ℤ
. Crucial to our study is the decomposition of the integer hull into the convex hull of its extreme points, conv(ext(
S
ℤ
)), and its recession cone. Although conv(ext(
S
ℤ
)) 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
S
ℤ
has an infinite number of extreme points if and only if conv(ext(
S
ℤ
)) has an infinite number of facets. Using these results, we provide a necessary and sufficient condition for semidefinite representability of conv(ext(
S
ℤ
)).