Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142785 | Operations Research Letters | 2013 | 4 Pages |
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).
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Valentina Cacchiani, Alberto Caprara, Gábor Maróti, Paolo Toth,