TY - GEN A1 - Weismantel, Robert T1 - On the 0/1 Knapsack Polytope. N2 - {\def\N{{\mbox{{\rm I\kern-0.22emN}}}} Given a set $N$ of items and a capacity $b \in \N$, and let $N_j$ be the set of items with weight $j$, $1 \leq j \leq b$. The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy the inequality $$\sum_{j=1}^b \sum_{i \in N_j} jx_i \leq b.$$ In this paper we first present a complete linear description of the 0/1 knapsack polytope for two special cases: (a) $N_j = \emptyset$ for all $1 < j \leq \lfloor {b \over 2} \rfloor$ and (b) $N_j = \emptyset$ for all $1 < j \leq \lfloor {b \over 3} \rfloor$ and $N_j = \emptyset$ for all $j \geq \lfloor {b \over 2} \rfloor + 1$. It turns out that the inequalities that are needed for the complete description of these special polytopes are derived by means of some ``reduction principle''. This principle is then generalized to yield valid and in many cases facet defining inequalities for the general 0/1 knapsack polytope. The separation problem for this class of inequalities can be solved in pseudo polynomial time via dynamic programming techniques.} T3 - ZIB-Report - SC-94-01 Y1 - 1994 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/131 UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-1312 ER -