{0,1/2}-Chvatal-Gomory cuts

Given the integer polyhedron P-I = conv{x is an element of Z(n): Ax less than or equal to b}, where A is an element of Z(mxn) and b is an element of Z(m), a Chvatal-Gomory (CG) cut is a valid inequality for P-I of the type lambda(T)Ax less than or equal to [lambda(T)b] for some lambda is an element of R(+)(m) such that lambda(T)A is an element of Z(n). In this paper we study {0, 1/2}-CG cuts, arising for lambda is an element of {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 when A 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 system Ax less than or equal to 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 for P-I. Applications to the clique partitioning, asymmetric traveling salesman, plant location, acyclic subgraph and linear ordering polytopes are briefly discussed.