consider the integer set where A is total unimdular Consider

consider the integer set where A is total unimdular

Consider the integer set S = {x epsilon Z^n_+ | Ax lessthanorequalto b}, where A is totally unimodular. but b may have fractional components. Show that conv(S) - {x epsilon R^n_+ | Ax lessthanorequalto [b]}. You may assume that S notequalto theta.

Solution

Since S is the set of n dimensional integer entried points. All the basis vectors of Rⁿ₊ are in Zⁿ_+.

i.e. {(1,0,0,...,0),(0,1,...,0),...,(0,0,...,1)}.

Convex set made by the points of set S will be the whole space Rⁿ₊.

Since, b is the vector that may have fractional components, in Conv(S), Ax <= [b].