zbMATH — the first resource for mathematics

Geometric proofs for convex hull defining formulations. (English) Zbl 1408.90193
Summary: A conjecture appeared recently in [V. Cacchiani et al., ibid. 41, No. 1, 74–77 (2013; Zbl 1266.90129)] that a proposed LP relaxation of a certain integer programming problem defines the convex hull of its integer points. We review a little known technique described in [the author, A set theoretic approach to lifting procedures for \(0, 1\) integer programming. New York, NY: Columbia University (Ph.D. thesis) (2004)] that can be used to construct geometric proofs that an LP relaxation is convex hull defining. In line with this technique, we show that their conjecture is correct.

90C10 Integer programming
52B55 Computational aspects related to convexity
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX Cite
Full Text: DOI
[1] Balas, E.; Ceria, S.; Cornuéjols, G., A lift-and-project cutting plane algorithm for mixed 0-1 programs, Math. Program., 58, 295-324, (1993) · Zbl 0796.90041
[2] Bienstock, D.; Zuckerberg, M., Subset algebra lifting methods for 0-1 integer programming, SIAM J. Optim., 15, 63-95, (2004) · Zbl 1077.90041
[3] Cacchiani, V.; Caprara, A.; Maróti, G.; Toth, P., On integer polytopes with few nonzero vertices, Oper. Res. Lett., 41, 1, 74-77, (2013) · Zbl 1266.90129
[4] Deza, M.; Laurent, M., On integer polytopes with few nonzero vertices, (1997), Springer
[5] Lasserre, J. B., An explicit exact sdp relaxation for nonlinear 0-1 programs, Lecture Notes in Comput. Sci., 293-303, (2001) · Zbl 1010.90515
[6] Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 166-190, (1991) · Zbl 0754.90039
[7] Sherali, S.; Adams, W., A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3, 411-430, (1990) · Zbl 0712.90050
[8] Zuckerberg, M., A set theoretic approach to lifting procedures for 0,1 integer programming, (2004), Columbia University, (Ph.D. thesis)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.