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).
On integer polytopes with few nonzero vertices / Valentina Cacchiani; Alberto Caprara; Gábor Maróti; Paolo Toth. - In: OPERATIONS RESEARCH LETTERS. - ISSN 0167-6377. - STAMPA. - 41:1(2013), pp. 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.
