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).
Valentina Cacchiani, Alberto Caprara, Gábor Maróti, Paolo Toth (2013). On integer polytopes with few nonzero vertices. OPERATIONS RESEARCH LETTERS, 41(1), 74-77 [10.1016/j.orl.2012.11.007].
On integer polytopes with few nonzero vertices
CACCHIANI, VALENTINA;CAPRARA, ALBERTO;TOTH, PAOLO
2013
Abstract
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).I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
