0/1 Polytopes with Quadratic Chvátal Rank

References

• Balas E (1985) Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM. J. Algebraic and Discrete Methods 6(3):466–486.Crossref, Google Scholar
• Balas E, Ceria S, Cornuéjols G (1993) A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Program. 58(1):295–324.Crossref, Google Scholar
• Bockmayr A, Eisenbrand F, Hartmann ME, Schulz AS (1999) On the Chvátal rank of polytopes in the 0/1 cube. Dis. App. Math. 98(1–2):21–27.Crossref, Google Scholar
• Bödi R, Herr K, Joswig M (2013) Algorithms for highly symmetric linear and integer programs. Math. Program. 137(1):65–90.Crossref, Google Scholar
• Chvátal V, Cook W, Hartmann M (1989) On cutting-plane proofs in combinatorial optimization. Linear Algebra Appl. 114–115(0):455–499. Special Issue Dedicated to Alan J. Hoffman.Crossref, Google Scholar
• Chlamtáč E, Tulsiani M (2011) Convex relaxations and integrality gaps. Anjos MF, Lasserre JB, eds. Handbook on Semidefinite, Cone and Polynomial Optimization (Springer, New York), 139–169.Google Scholar
• Conforti M, Del Pia A, Di Summa M, Faenza Y, Grappe R (2013) Reverse Chvátal-Gomory Rank. Goemans M, Correa J, eds. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 7801 (Springer, Berlin), 133–144.Crossref, Google Scholar
• Dadush D, Dey SS, Vielma JP (2011) The Chvátal-Gomory closure of a strictly convex body. Math. Oper. Res. 36(2):227–239.Link, Google Scholar
• Dadush D, Dey SS, Vielma JP (2011) On the Chvátal-Gomory closure of a compact convex set. Günlük O, Woeginger GJ, eds. Proc. 15th Internat. Conf. Integer Programming Combinatorial Optimization, IPCO ’11 (Springer, Berlin), 130–142.Crossref, Google Scholar
• Dunkel J, Schulz AS (2010) The Gomory-Chvátal closure of a non-rational polytope is a rational polytope. http://www.optimization-online.org/DB_HTML/2010/11/2803.html.Google Scholar
• Eisenbrand F (1999) On the membership problem for the elementary closure of a polyhedron. Combinatorica 19(2):297–300.Crossref, Google Scholar
• Eisenbrand F, Schulz AS (1999) Bounds on the Chvátal rank of polytopes in the 0/1-cube. Cornuéjols G, Burkard RE, Woeginger GJ, eds. Integer Programming and Combinatorial Optim., Lecture Notes in Computer Science, Vol. 1610 (Springer, Berlin), 137–150.Crossref, Google Scholar
• Eisenbrand F, Schulz AS (2003) Bounds on the Chvátal rank of polytopes in the 0/1-cube. Combinatorica 23(2):245–261.Crossref, Google Scholar
• Lasserre J (2001a) An explicit exact SDP relaxation for nonlinear 0–1 programs. Aardal K, Gerards B, eds. Proc. 8th Internat. Conf. Integer Programming Combinatorial Optimization, IPCO ’01 (Springer, Berlin), 293–303.Crossref, Google Scholar
• Lasserre J (2001b) Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817.Crossref, Google Scholar
• Laurent M (2003) A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0–1 programming. Math. Oper. Res. 28(3):470–496.Link, Google Scholar
• Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1(2):166–190.Crossref, Google Scholar
• Pokutta S, Schulz AS (2011) Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvátal rank. Oper. Res. Lett. 39(6):457–460.Crossref, Google Scholar
• Pokutta S, Stauffer G (2011) Lower bounds for the Chvátal-Gomory rank in the 0/1 cube. Oper. Res. Lett. 39(3):200–203.Crossref, Google Scholar
• Rothvoß T, Sanità L (2013) 0/1 polytopes with quadratic Chvátal rank. Goemans M, Correa J, eds. Proc. 16th Internat. Conf. Integer Programming Combinatorial Optimization, IPCO ’13 (Springer, Berlin), 349–361.Crossref, Google Scholar
• Sherali H, Adams W (1990) A hierarchy of relaxation between the continuous and convex hull representations. SIAM J. Dis. Math. 3(3):411–430.Crossref, Google Scholar
• Schrijver A (1980) On cutting planes. Annals of Discrete Mathematics 9:291–296.Crossref, Google Scholar
• Singh M, Talwar K (2010) Improving integrality gaps via Chvátal-Gomory rounding. Serna M, Shaltiel R, Jansen K, Rolim J, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Lecture Notes in Computer Science, Vol. 6302 (Springer, Berlin), 366–379.Crossref, Google Scholar
• Ziegler GM (2000) Lectures on 0/1-polytopes. Kalai G, Ziegler GM, eds. Polytopes—Combinatorics and Computation, DMV Sem., Vol. 29 (Birkhäuser, Basel, Switzerland), 1–41.Crossref, Google Scholar