Hilbert Bases and the Facets of Special Knapsack Polytopes.
Please always quote using this URN: urn:nbn:de:0297-zib-1475
- {\def\N{{\mbox{{\rm I\kern-0.22emN}}}} Let a set $N$ of items, a capacity $F \in \N$ and weights $a_i \in \N$, $i \in N$ be given. The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy the inequality $$\sum_{i \in N} a_i x_i \leq F.$$ In this paper we present a linear description of the 0/1 knapsack polytope for the special case where $a_i \in \{\mu,\lambda\}$ for all items $i \in N$ and $1 \leq \mu < \lambda \leq b$ are two natural numbers. The inequalities needed for this description involve elements of the Hilbert basis of a certain cone. The principle of generating inequalities based on elements of a Hilbert basis suggests further extensions.}
Download full text files
Additional Services
| Author: | Robert Weismantel |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 1994/06/24 |
| Series (Serial Number): | ZIB-Report (SC-94-19) |
| ZIB-Reportnumber: | SC-94-19 |
| Published in: | Appeared in: Operations Research 21 (1996) pp. 886-904 |
