Given the integer polyhedron PI ≔ conv{x ∈ ℤn: Ax ⩽ b}, where A ∈ ℤm×n and b ∈ ℤm, a Chvátal–Gomory (CG) cut is a valid inequality for PI of the type λTAx ⩽ ⌊λTb⌋ for some λ ∈ ℝm+ such that λTA ∈ ℤn. In this paper we study {0, ½}-CG cuts, arising for λ ∈ {0, ½}m. We show that the associated separation problem, {0, ½}-SEP, is equivalent to finding a minimum-weight member of a binary cluster. This implies that {0, ½}-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, ½}-SEP can be solved in polynomial time for a convenient relaxation of the system Ax ⩽ b. This leads to an efficient separation algorithm for a subclass of {0, ½}-CG cuts, which often contains wide families of strong inequalities for PI. Applications to the clique partitioning, asymmetric traveling salesman, plant location, acyclic subgraph and linear ordering polytopes are briefly discussed.
