When the Gomory–Chvátal closure coincides with the integer hull
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