Lifted Cover Inequalities for 0-1 Integer Programs: Complexity

References

• Balas E. Facets of the knapsack polytope. Math. Programming (1975) 8:146–164Crossref, Google Scholar
• Balas E., Zemel E., Cottle R. W., Kennington H. L., Korte B. Lifting and complementing yields all the facets of positive zero-one programming polytopes. Mathematical Programming (1984) (North-Holland, Amsterdam)13–24Google Scholar
• Chung C. S., Hung M. S., Rom W. O. A hard Knapsack problem. Naval Res. Logist. Quart. (1988) 35:85–98Crossref, Google Scholar
• Chvatal V. Hard Knapsack problems. Oper. Res. (1980) 28:1402–1411Link, Google Scholar
• Crowder H., Johnson E., Padberg M. Solving large-scale zero-one linear programming problems. Oper. Res. (1983) 31:803–834Link, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman and Company, San Francisco) Google Scholar
• Gu Z., Nemhauser G. L., Savelsbergh M. W. P. Lifted cover inequalities for 0-1 integer programs: Computation. INFORMS J. Comput. (1998) 10:427–437Link, Google Scholar
• Gu Z., Nemhauser G. L., Savelsbergh M. W. P. Lifted cover inequalities for 0-1 integer programs: Algorithms. (1999) . Technical report, Georgia Institute of Technology, in PreparationGoogle Scholar
• Hartvigsen D., Zemel E. The complexity of lifted inequalities for the Knapsack problem. Discrete Appl. Math. (1992) 39:113–123Crossref, Google Scholar
• Hoffman K., Padberg M. Improving LP-representations of zero-one linear programs for branch-and-cut. ORSA J. Comput. (1991) 3:121–134Link, Google Scholar
• Jereslow R. G. Trivial integer programs unsolved by branch and bound. Math. Programming (1974) 6:105–109Crossref, Google Scholar
• Klabjan D., Nemhauser G. L., Tovey C. The complexity of cover inequality separation. Oper. Res. Lett. (1998) 23:35–40Crossref, Google Scholar
• Laurent M., Sassano A. A characterization of Knapsacks with the max-flow-min-cut property. Oper. Res. Lett. (1992) 11:105–110Crossref, Google Scholar
• Martello S., Toth P.Knapsack Problems: Algorithms and Computer Implementations (1990) (John Wiley and Sons, New York) Google Scholar
• Nemhauser G. L., Vance P. H. Lifted cover facets of the 0-1 Knapsack polytope with GUB constraints. Oper. Res. Lett. (1994) 16:255–263Crossref, Google Scholar
• Nemhauser G. L., Wolsey L. A.Integer and Combinatorial Optimization (1988) (John Wiley and Sons, New York) Crossref, Google Scholar
• Padberg M. W. A note on zero-one programming. Oper. Res. (1975) 23:833–837Link, Google Scholar
• Padberg M. W. (1 k)-configurations and facets for packing problems. Math. Programming (1980) 18:94–99Crossref, Google Scholar
• Weismantel R. On the 0/1 Knapsack polytope. (1994) . Technical report SC 91-1, Konrad-Zuse-Zentrum fur Informationstechnik Berlin, Berlin, GermanyGoogle Scholar
• Wolsey L. A. Faces for a linear inequality in 0-1 variables. Math. Programming (1975) 8:165–178Crossref, Google Scholar
• Zemel E. Easily computable facets of the knapsack polytope. Math. Oper. Res. (1989) 14:760–765Link, Google Scholar