TY - JOUR
T1 - On maximal S-free convex sets*
AU - Morán R., Diego A.
AU - Dey, Santanu S.
PY - 2011
Y1 - 2011
N2 - Let S ℤn satisfy the property that conv(S) n ℤn = S. Then a convex set K is called an S-free convex set if int(K) S = Ø. A maximal S-free convex set is an S-free convex set that is not properly contained in any S-free convex set. We show that maximal S-free convex sets are polyhedra. This result generalizes a result of Basu et al. [SIAM J. Discrete Math., 24 (2010), pp. 158- 168] for the case where S is the set of integer points in a rational polyhedron and a result of Lovász [Mathematical Programming: Recent Developments and Applications, M. Iri and K. Tanabe, eds., Kluwer, Dordrecht, 1989, pp. 177-210] and Basu et al. [Math. Oper. Res., 35 (2010), pp. 704-720] for the case where S is the set of integer points in some affine subspace of Rn.
AB - Let S ℤn satisfy the property that conv(S) n ℤn = S. Then a convex set K is called an S-free convex set if int(K) S = Ø. A maximal S-free convex set is an S-free convex set that is not properly contained in any S-free convex set. We show that maximal S-free convex sets are polyhedra. This result generalizes a result of Basu et al. [SIAM J. Discrete Math., 24 (2010), pp. 158- 168] for the case where S is the set of integer points in a rational polyhedron and a result of Lovász [Mathematical Programming: Recent Developments and Applications, M. Iri and K. Tanabe, eds., Kluwer, Dordrecht, 1989, pp. 177-210] and Basu et al. [Math. Oper. Res., 35 (2010), pp. 704-720] for the case where S is the set of integer points in some affine subspace of Rn.
KW - Cutting planes
KW - Integer nonlinear programming
KW - Maximal lattice-free convex sets
UR - http://www.scopus.com/inward/record.url?scp=79958255009&partnerID=8YFLogxK
U2 - 10.1137/100796947
DO - 10.1137/100796947
M3 - Article
AN - SCOPUS:79958255009
VL - 25
SP - 379
EP - 393
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
SN - 0895-4801
IS - 1
ER -