<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>131</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1994-01-20</completedDate>
    <publishedDate>1994-01-20</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the 0/1 Knapsack Polytope.</title>
    <abstract language="eng">{\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 &lt; j \leq \lfloor {b \over 2} \rfloor$ and (b) $N_j = \emptyset$ for all $1 &lt; 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.}</abstract>
    <identifier type="serial">SC-94-01</identifier>
    <identifier type="opus3-id">131</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-1312</identifier>
    <enrichment key="SourceTitle">A revised version appeared in: Mathematical Programming 77 (1997) 49-68</enrichment>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-94-01</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/131/SC-94-01.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/131/SC-94-01.pdf</file>
  </doc>
</export-example>
