On integer polytopes with few nonzero vertices

We provide a simple description in terms of linear inequalities of the convex hull of the nonnegative integer vectors $x$ that satisfy a given linear knapsack covering constraint $\Sigma a_i{x}_i\ge b$ and have sum of the components that does not exceed 2. This description allows the replacement of ‘weak’ knapsack‐type constraints by stronger ones in several ILP formulations for practical problems, including railway rolling stock scheduling. In addition, we provide a simple description of the packing counterpart of the considered polytope, i.e. for the case in which the knapsack inequality is $\Sigma a_i{x}_i\le b$ (and again the sum of the components of the nonnegative integer vectors that does not exceed 2).