When the Gomory–Chvátal closure coincides with the integer hull

Operations Research Letters - Tập 46 - Trang 251-256 - 2018
Gérard Cornuéjols1, Yanjun Li2
1Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA 15213, USA
2Krannert School of Management, Purdue University, West Lafayette, IN 47906, USA

Tài liệu tham khảo

Borosh, 1976, Bounds on positive integral solutions to linear Diophantine equations, Proc. Amer. Math. Soc., 55, 299, 10.1090/S0002-9939-1976-0396605-3 Boyd, 2009, Facet generating techniques, 33 Bunch, 1997 Campelo, 2009, Stable sets, corner polyhedra and the Chvátal closure, Oper. Res. Lett., 37, 375, 10.1016/j.orl.2009.06.006 Caprara, 1996, {0,1∕2}-Chvátal-Gomory cuts, Math. Program., 74, 221, 10.1007/BF02592196 Chandrasekaran, 2016, The cutting plane method is polynomial for perfect matchings, Math. Oper. Res., 41, 23, 10.1287/moor.2015.0714 Chvátal, 1973, Edmonds polytope and a hierarchy of combinatorial problems, Discrete Math., 4, 305, 10.1016/0012-365X(73)90167-2 Conforti, 2007, Mixed-integer vertex covers on bipartite graphs, vol. 4513, 324 Cook, 1990, Chvátal closures for mixed integer programs, Math. Program., 47, 155, 10.1007/BF01580858 Cornuéjols, 2016, Deciding emptiness of the Gomory-Chvátal closure is NP-complete, even for a rational polyhedron containing no integer point, vol. 9682, 387 Del Pia, 2017, On matrices with the Edmonds-Johnson property arising from bidirected graphs, J. Combin. Theory, Ser. B Del Pia, 2009, Half-integral vertex covers on bipartite bidirected graphs: total dual integrality and cut-rank, SIAM J. Discrete Math., 23, 1281, 10.1137/070703399 Edmonds, 1965, Maximum matching and a polyhedron with 0,1-vertices, J. Res. Nat. Bureau Stand. B, 69, 125, 10.6028/jres.069B.013 Edmonds, 1973, Matching, Euler tours and the Chinese postman, Math. Program., 5, 88, 10.1007/BF01580113 Eisenbrand, 1999, On the membership problem for the elementary closure of a polyhedron, Combinatorica, 19, 297, 10.1007/s004930050057 Fischetti, 2007, Optimizing over the first Chvátal closure, Math. Program., 110, 3, 10.1007/s10107-006-0054-8 Garey, 1979 Gerards, 1986, Matrices with the Edmonds-Johnson property, Combinatorica, 6, 365, 10.1007/BF02579262 Goldreich, 2010 Gomory, 1958, Outline of an algorithm for integer solutions to linear programs, Bull. Amer. Math. Soc., 64, 275, 10.1090/S0002-9904-1958-10224-4 Gomory, 1969, Some polyhedra related to combinatorial problems, Linear Algebra Appl., 2, 451, 10.1016/0024-3795(69)90017-2 Grötschel, 1981, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169, 10.1007/BF02579273 Hartmann, 1999, On the Chvátal rank of certain inequalities, vol. 1610, 218 Hartvigsen, 2013, Polyhedron of triangle-free simple 2-matchings in subcubic graphs, Math. Program., 138, 43, 10.1007/s10107-012-0516-0 Kobayashi, 2010, A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs, Discrete Optim., 7, 197, 10.1016/j.disopt.2010.04.001 G.S. Lueker, Two NP-complete problems in nonnegative integer programming. Report No. 178, Department of Computer Science, Princeton University, Princeton N.J., 1975. Mahajan, 2010, On the complexity of selecting disjunctions in integer programming, SIAM J. Optim., 20, 2181, 10.1137/080737587 Meyer, 1974, On the existence of optimal solutions to integer and mixed integer programming problems, Math. Program., 7, 223, 10.1007/BF01585518 Padberg, 1982, Odd minimum cut-sets and b-matchings, Math. Oper. Res., 7, 67, 10.1287/moor.7.1.67 Pulleyblank, 1974, Facets of 1-matching polyhedra, 214 Schrijver, 1980, On cutting planes, Ann. Discrete Math., 9, 291, 10.1016/S0167-5060(08)70085-2 Schrijver, 1986 Schrijver, 2003