BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-72-284
       ENTRY:: October 16, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Edmonds polyhedra and a hierarchy of combinatorial problems.
        TYPE:: Technical Report
      AUTHOR:: Chvatal, Vaclav
        DATE:: May 1972
       PAGES:: 52
    ABSTRACT:: Let S be a set of linear inequalities that determine a
               bounded polyhedron P. The closure of S is the smallest set of
               inequalities that contains S and is closed under two
               operations: (i) taking linear combinations of inequalities,
               (ii) replacing an inequality $\sum\ a_j x_j \leq\ a_0$, where
               $a_1, a_2, ... , a_n$ are integers, by the inequality $\sum\
               a_j x_j \leq\ a$ with $a \geq\ [a_0]$. Obviously, if integers
               $x_1, x_2, ... , x_n$ satisfy all the inequalities in S then
               they satisfy also all the inequalities in the closure of S.
               Conversely, let $\sum\ c_j x_j \leq\ c_0$ hold for all
               choices of integers $x_1, x_2, ... , x_n$, that satisfy all
               the inequalities in S. Then we prove that $\sum\ c_j x_j
               \leq\ c_0$ belongs to the closure of S. To each integer
               linear programming problem, we assign a nonnegative integer,
               called its rank. (The rank is the minimum number of
               iterations of the operation (ii) that are required in order
               to eliminate the integrality constraint.) We prove that there
               is no upper bound on the rank of problems arising from the
               search for largest independent sets in graphs.
       NOTES:: [Adminitrivia V1/Prg/19951016]
         END:: STAN//CS-TR-72-284