A generalization of Robacker's theorem (Q1118612)

Let \({\mathcal P}\) be the polyhedron given by \({\mathcal P}=\{x\in R^ n:\) \(Nx=0\), \(a\leq x\leq b\}\), where N is a totally unimodular matrix and a and b are any integral vectors. For \(x\in R^ n\) \(let(x)^+\) denote the vector obtained from x by changing all its negative components to zeros. Let \(x^ 1,...,x^ p\) be the integral points in \({\mathcal P}\) and let \({\mathcal P}^+\) be the convex hull of \((x^ 1)^+,...,(x^ p)^+\). In this paper we derive the blocking polyhedron for \(\{x\in R^ n_+:\) Mx\(\geq 1\}\) where the rows of M are integral points in \({\mathcal P}^+\). We also show that the optimum objective function values of the integer programming problem max\(\{\) \(1\cdot y:yM\leq w\), \(y\geq 0\) and integral\(\}\) and its linear programming relaxation differ by less than one for any nonnegative, integral vector w. As a special case of this result we derive Robacker's theorem which states that for a directed graph with two distinguished nodes a and t, the maximum value of an integral packing of forward edges in (s,t)-cuts into a nonnegative, integral weighting w of the edges is equal to the minimum w-weight of an (s,t)-path.