Odd cutsets, odd cycles and 0–1/2 Chvátal–Gomory cuts

We address 0–1/2 Chvátal–Gomory (C-G) cuts, a subclass of the well-known Chvátal–Gomory cuts arising when each coefficient in the Chvátal–Gomory derivation is either 0 or 1/2. We show that the associated separation problem, 0–1/2 SEP, is NP-complete in the general case, but polynomially solvable in two relevant special cases. We also describe reduction procedures for 0–1/2 SEP and outline two heuristic algorithms based on the computation of minimum-weight odd cut-sets and odd cycles in a suitable graph. One of the two heuristics turns out to be exact for a subclass of 0–1/2 C–G cuts, which often contains wide families of strong inequalities. Applications to the Node Packing, Clique Partitioning, Asymmetric Traveling Salesman, Plant Location, Acyclic Subgraph and Linear Ordering polytopes are briefly discussed, leading to new efficient separation algorithms. Finally, we present in the appendix a dynamic programming algorithm for finding a minimum-weight odd cycle in a digraph.