Convex hull approximation of TU integer recourse models:Counterexamples, sufficient conditions, and special cases

Abstract

We consider a convex approximation for integer recourse models. In particular, we showthat the claim of Van der Vlerk (2004) that this approximation yields the convex hull of totallyunimodular (TU) integer recourse models is incorrect. We discuss counterexamples, indicate which step of its proof does not hold in general, and identify a class of random variables for which the claim in Van der Vlerk (2004) is not true. At the same time, we derive additional assumptions under which the claim does hold. In particular, if the random variables in the model are independently and uniformly distributed, then these assumptions are satisfied.