×

When the Gomory-Chvátal closure coincides with the integer hull. (English) Zbl 1525.90273

Summary: Gomory-Chvátal cuts are prominent in integer programming. The Gomory-Chvátal closure of a polyhedron is the intersection of the half spaces defined by all its Gomory-Chvátal cuts. We prove that it is \(\mathcal{NP}\)-hard to decide whether the Gomory-Chvátal closure of a rational polyhedron \(P\) is identical to the integer hull of \(P\). An earlier version of this paper appeared in the proceedings of IPCO 2016.

MSC:

90C10 Integer programming
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Borosh, I.; Treybig, L. B., Bounds on positive integral solutions to linear Diophantine equations, Proc. Amer. Math. Soc., 55, 299-304 (1976) · Zbl 0291.10014
[2] Boyd, S.; Pulleyblank, W. R., Facet generating techniques, (Cook, W.; Lovász, L.; Vygen, J., Research Trends in Combinatorial Optimization (2009), Springer: Springer Berlin), 33-55 · Zbl 1359.90113
[3] Bunch, P. R., A Simplex Based Primal-Dual Algorithm for the Perfect \(b\)-Matching Problem - A Study in Combinatorial Optimization Algorithm in Engineering (1997), Purdue University, (Ph.D. thesis)
[4] Campelo, M.; Cornuéjols, G., Stable sets, corner polyhedra and the Chvátal closure, Oper. Res. Lett., 37, 375-378 (2009) · Zbl 1180.90183
[5] Caprara, A.; Fischetti, M., \(\{0, 1 / 2 \}\)-Chvátal-Gomory cuts, Math. Program., 74, 221-235 (1996) · Zbl 0855.90088
[6] Chandrasekaran, K.; Végh, L.; Vempala, S., The cutting plane method is polynomial for perfect matchings, Math. Oper. Res., 41, 23-48 (2016) · Zbl 1334.90077
[7] Chvátal, V., Edmonds polytope and a hierarchy of combinatorial problems, Discrete Math., 4, 305-337 (1973) · Zbl 0253.05131
[8] Conforti, M.; Gerards, A. M.H.; Zambelli, G., Mixed-integer vertex covers on bipartite graphs, (The Proceedings of IPCO 2007. The Proceedings of IPCO 2007, Lecture Notes in Computer Science, vol. 4513 (2007)), 324-336 · Zbl 1136.90488
[9] Cook, W.; Kannan, R.; Schrijver, A., Chvátal closures for mixed integer programs, Math. Program., 47, 155-174 (1990) · Zbl 0711.90057
[10] 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, (The Proceedings of IPCO 2016. The Proceedings of IPCO 2016, Lecture Notes in Computer Science, vol. 9682 (2016)), 387-398 · Zbl 1419.90068
[11] Del Pia, A.; Musitelli, A.; Zambelli, G., On matrices with the Edmonds-Johnson property arising from bidirected graphs, J. Combin. Theory, Ser. B (2017), published online first at https://doi.org/10.1016/j.jctb.2017.09.013 · Zbl 1384.05107
[12] Del Pia, A.; Zambelli, G., Half-integral vertex covers on bipartite bidirected graphs: total dual integrality and cut-rank, SIAM J. Discrete Math., 23, 1281-1296 (2009) · Zbl 1227.05209
[13] Edmonds, J., Maximum matching and a polyhedron with 0,1-vertices, J. Res. Nat. Bureau Stand. B, 69, 125-130 (1965) · Zbl 0141.21802
[14] Edmonds, J.; Johnson, E. L., Matching, Euler tours and the Chinese postman, Math. Program., 5, 88-124 (1973) · Zbl 0281.90073
[15] Eisenbrand, F., On the membership problem for the elementary closure of a polyhedron, Combinatorica, 19, 297-300 (1999) · Zbl 0947.90071
[16] Fischetti, M.; Lodi, A., Optimizing over the first Chvátal closure, Math. Program., 110, 3-20 (2007) · Zbl 1192.90125
[17] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide To the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman San Francisco · Zbl 0411.68039
[18] Gerards, A. M.H.; Schrijver, A., Matrices with the Edmonds-Johnson property, Combinatorica, 6, 365-379 (1986) · Zbl 0641.05039
[19] Goldreich, O., P, NP, and NP-Completeness: The Basics of Computational Complexity (2010), Cambridge University Press · Zbl 1230.68006
[20] Gomory, R. E., Outline of an algorithm for integer solutions to linear programs, Bull. Amer. Math. Soc., 64, 275-278 (1958) · Zbl 0085.35807
[21] Gomory, R. E., Some polyhedra related to combinatorial problems, Linear Algebra Appl., 2, 451-558 (1969) · Zbl 0184.23103
[22] Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197 (1981) · Zbl 0492.90056
[23] Hartmann, M. E.; Queyranne, M.; Wang, Y., On the Chvátal rank of certain inequalities, (Cornuéjols, G.; Burkard, R. E.; Woeginger, G. J., IPCO. IPCO, Lecture Notes in Computer Science, vol. 1610 (1999)), 218-233 · Zbl 0948.90151
[24] Hartvigsen, D.; Li, Y., Polyhedron of triangle-free simple 2-matchings in subcubic graphs, Math. Program., 138, 43-82 (2013) · Zbl 1273.05175
[25] Kobayashi, Y., A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs, Discrete Optim., 7, 197-202 (2010) · Zbl 1241.90162
[26] G.S. Lueker, Two NP-complete problems in nonnegative integer programming. Report No. 178, Department of Computer Science, Princeton University, Princeton N.J., 1975.; G.S. Lueker, Two NP-complete problems in nonnegative integer programming. Report No. 178, Department of Computer Science, Princeton University, Princeton N.J., 1975.
[27] Mahajan, A.; Ralphs, T., On the complexity of selecting disjunctions in integer programming, SIAM J. Optim., 20, 2181-2198 (2010) · Zbl 1211.90136
[28] Meyer, R. R., On the existence of optimal solutions to integer and mixed integer programming problems, Math. Program., 7, 223-235 (1974) · Zbl 0292.90036
[29] Padberg, M. W.; Rao, M. R., Odd minimum cut-sets and \(b\)-matchings, Math. Oper. Res., 7, 67-80 (1982) · Zbl 0499.90056
[30] Pulleyblank, W. R.; Edmonds, J., Facets of 1-matching polyhedra, (Berge, C.; Ray-Chaudhuri, D., Hypergraph Seminar (1974), Springer: Springer Berlin), 214-242 · Zbl 0317.05119
[31] Schrijver, A., On cutting planes, Ann. Discrete Math., 9, 291-296 (1980) · Zbl 0441.90070
[32] Schrijver, A., Theory of Linear and Integer Programming (1986), Wiley: Wiley Chichester · Zbl 0665.90063
[33] Schrijver, A., Combinatorial Optimization: Polyhedra and Efficiency (2003), Springer: Springer Berlin · Zbl 1041.90001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.