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 ~(aixi)≥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 ~(aixi)≤b (and again the sum of the components of the nonnegative integer vectors that does not exceed 2).