Mod-2 Cuts Generation Yields the Convex Hull of Bounded Integer Feasible Sets

This paper focuses on the outer description of the convex hull of all integer solutions to a given system of linear inequalities. It is shown that if the given system contains lower and upper bounds for the variables, then the convex hull can be produced by iteratively generating so-called mod-2 cuts only. This fact is surprising and might even be counterintuitive, since many integer rounding cuts exist that are not mod-2, i.e., representable as the zero- one-half combination of the given constraint system. The key, however, is that in general many more rounds of mod-2 cut generation are necessary to produce the final description compared to the traditional integer rounding procedure.