Abstract
In this paper, we consider polytopes P that are contained in the unit hypercube. We provide conditions on the set of 0, 1 vectors not contained in P that guarantee that P has a small Chvátal rank. Our conditions are in terms of the subgraph induced by these infeasible 0, 1 vertices in the skeleton graph of the unit hypercube. In particular, we show that when this subgraph contains no 4-cycle, the Chvátal rank is at most 3; and when it has tree width 2, the Chvátal rank is at most 4. We also give polyhedral decomposition theorems when this graph has a vertex cutset of size one or two.
Similar content being viewed by others
References
Abdi, A., Cornuéjols, G., Pashkovich, K.: Ideal clutters that do not pack. Math. Oper. Res. (2017). https://doi.org/10.1287/moor.2017.0871
Angulo, G., Ahmed, S., Dey, S.S., Kaibel, V.: Forbidden vertices. Math. Oper. Res. 40, 350–360 (2015)
Bockmayr, A., Eisenbrand, F., Hartmann, M., Schulz, A.S.: On the Chvátal rank of polytopes in the 0/1 cube. Discrete Appl. Math. 98, 21–27 (1999)
Chvátal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4, 305–337 (1973)
Chvátal, V., Cook, W., Hartmann, M.: On cutting-plane proofs in combinatorial optimization. Linear Algebra Appl. 114/115, 455–499 (1989)
Cornuéjols, G., Li, Y.: On the rank of mixed 0, 1 polyhedra. Math. Program. Ser. A 91, 391–397 (2002)
Cornuéjols, G., Li, Y.: Deciding emptiness of the Gomory–Chvátal closure is NP-complete, even for a rational polyhedron containing no integer point. In: Louveaux, Q., Skutella, M. (eds.) IPCO, vol. 9682, pp. 387–397. LNCS (2016)
Cornuéjols, G., Lee, D., Li, Y.: On the rational polytopes with Chvátal rank 1. Submitted
Dadush, D., Dey, S.S., Vielma, J.P.: On the Chvátal–Gomory closure of a compact convex set. Math. Program. Ser. A 145, 327–348 (2014)
Dunkel, J., Schulz, A.S.: The Gomory–Chvátal closure of a nonrational polytope is a rational polytope. Math. Oper. Res. 38, 63–91 (2013)
Eisenbrand, F., Schulz, A.S.: Bounds on the Chvátal rank of polytopes in the 0/1 cube. Combinatorica 23, 245–261 (2003)
Ghouila-Houri, A.: Caractérisation des matrices totalement unimodulaires. Compt. Rendus Hebd. Scé. l’Acad. Sci. (Paris) 254, 1192–1194 (1962)
Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Am. Math. Soc. 64, 275–278 (1958)
Hartmann, M.E., Queyranne, M., Wang, Y.: On the Chvátal rank of certain inequalities. In: Cornuéjols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO, vol. 1610, pp. 218–233. LNCS (1999)
Pokutta, S., Schulz, A.S.: Integer-empty polytopes in the 0/1-cube with maximal Gomory–Chvátal rank. Oper. Res. Lett. 39, 457–460 (2011)
Rothvoss, T., Sanitá, L.: 0/1 polytopes with quadratic Chvátal rank. In: Goemans, M., Correa, J. (eds.) IPCO, vol. 7801, pp. 349–361. LNCS (2013)
Schrijver, A.: On cutting planes. Ann. Discrete Math. 9, 291–296 (1980)
Acknowledgements
This work was supported in part by NSF Grant CMMI1560828 and ONR Grant N00014-15-12082. We would like to thank the referees for carefully reading an earlier draft of the paper and providing valuable comments.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cornuéjols, G., Lee, D. On some polytopes contained in the 0, 1 hypercube that have a small Chvátal rank. Math. Program. 172, 467–503 (2018). https://doi.org/10.1007/s10107-017-1226-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-017-1226-4