Article ID Journal Published Year Pages File Type
1142785 Operations Research Letters 2013 4 Pages PDF
Abstract

We provide a simple description in terms of linear inequalities of the convex hull of the nonnegative integer vectors xx that satisfy a given linear knapsack covering constraint ∑aixi≥b∑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∑aixi≤b (and again the sum of the components of the nonnegative integer vectors that does not exceed 2).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,