A new lifting procedure for 0,1 integer programming problems is introduced in which variables are appended to correspond to each logical statement that can be made about the vectors in the feasible region. It is shown that this lifting generalizes the liftings of Sherali and Adams [?] and Lovasz and Schrijver [?], and that its features generalize the features of those liftings. The new larger lifting provides a broader conceptual framework for 0, 1 integer programming that is only incompletely exploited by the techniques based on the older liftings. We suggest several polynomial time algorithms in particular that take advantage of the larger lifting by tailoring their choice of new variables to the structure of the feasible set itself. One notable feature of these algorithms is that for large classes of problems, including the "Set Covering Problem", they produce in polynomial time a linear system of polynomial size each of whose solutions is guaranteed to satisfy all linear constraints on the feasible set whose coefficients are in {lcub}0,1,..., k{rcub}.
展开▼
