{0, 1/2}-Chvátal-Gomory cuts
Tóm tắt
Given the integer polyhedronP
t
:= conv{x ∈ℤ
n
:Ax⩽b}, whereA ∈ℤ
m × n
andb ∈ℤ
m
, aChvátal-Gomory (CG)cut is a valid inequality forP
1 of the type λτAx⩽⌊λτb⌋ for some λ∈ℝ
+
such that λτA∈ℤ
n
. In this paper we study {0, 1/2}-CG cuts, arising for λ∈{0, 1/2}
m
. We show that the associated separation problem, {0, 1/2}-SEP, is equivalent to finding a minimum-weight member of a binary clutter. This implies that {0, 1/2}-SEP is NP-complete in the general case, but polynomially solvable whenA is related to the edge-path incidence matrix of a tree. We show that {0, 1/2}-SEP can be solved in polynomial time for a convenient relaxation of the systemAx<-b. This leads to an efficient separation algorithm for a subclass of {0, 1/2}-CG cuts, which often contains wide families of strong inequalities forP
1. Applications to the clique partitioning, asymmetric traveling salesman, plant location, acyclic subgraph and linear ordering polytopes are briefly discussed.
Tài liệu tham khảo
E. Balas, “The asymmetric assignment problem and some new facets of the traveling salesman polytope on a directed graph”,SIAM Journal on Discrete Mathematics 2 (4) (1989) 425–451.
P. Camion, “Characterizations of totally unimodular matrices,”Proceedings of the American Mathematical Society 16 (1965) 1068–1073.
S. Chopra and M.R. Rao, “The partition problem”,Mathematical Programming 59 (1993) 87–115.
G. Cornuéjols, G.L., Nemhauser and L.A. Wolsey, “The uncapacitated facility location problem”, in: P.B. Mirchandani and R.L. Francis, eds.,Discrete Location Theory (Wiley, New York, 1990) pp. 119–171.
M. Deza, M. Grötschel and M. Laurent “Clique-web facets for multicut polytopes,”Mathematics of Operations Research 17 (4) (1992) 981–1000.
J. Edmonds, “Maximum matching and a polyhedron with 0.1-vertices,”Journal of Research of the National Bureau of Standards B. Mathematics and Mathematical Physics 69 (1965) 125–130.
J. Edmonds and H.L. Johnson, “Matching: a well-solved class of integer linear programs,” in: R.K. Guy et al., eds.Combinatorial Structures and their Applications (Gordon and Breach, New York, 1970) pp. 89–92.
M. Fischetti and P. Toth, “A polyhedral approach for solving hard ATSP instances,” Working paper, University of Bologna (1994).
M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-completeness (Freeman, San Francisco, 1979).
A.M.H. Gerards and A. Schrijver, “Matrices with the Edmonds-Johnson property,”Combinatorica 6(4) (1986) 365–379.
M. Grötschel, M. Jünger and G. Reinelt, “A cutting plane algorithm for the linear ordering problem”,Operations Research 32 (1984) 1195–1220.
M. Grötschel, M. Jünger and G. Reinelt, “On the acyclic subgraph polytope,”Mathematical Programming 33 (1985) 28–42.
M. Grötschel, M. Jünger and G. Reinelt, “Facets of the linear ordering polytope,”Mathematical Programming 33, (1985) 43–60.
M. Grötschel, L. Lovász and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization,”Combinatorica 1 (1981) 169–197.
M. Grötschel and W.R. Pulleyblank, “Weakly bipartite graphs and the max-cut problem,”Operations Research Letters 1 (1981) 23–27.
M. Grötschel and Y. Wakabayashi, “Facets of the clique partitioning polytope,”Mathematical Programming 47 (1990) 367–387.
R. Müller, “On the transitive acyclic subdigraph polytope,” in: G. Rinaldi and L.A. Wolsey, eds.,Proceedings of Third IPCO Conference (1993) pp. 463–477.
G.L. Nemhauser and L.A. Wolsey,Integer and Combinatorial Optimization, Wiley, New York, (1988).
M.W. Padberg and M.R. Rao “Odd minimum cut-sets andb-matchings,”Mathematics of Operations Research 7 (1) (1982) 67–80.
A. Schrijver,Theory of Linear and Integer Programming (Wiley, New York, 1986).
P.D. Seymour, “Decomposition of regular matroids,”Journal of Combinatorial Theory B 28 (1980) 305–359.