Linear-Programming-Based Lifting and Its Application to Primal Cutting-Plane Algorithms

References

• Aardal K., Weismantel R., Wolsey L. A. Non-standard approaches to integer programming. Discrete Appl. Math. (2002) 123:5–74Crossref, Google Scholar
• Agra A., Constantino M. F. Lifting two-integer knapsack inequalities. Math. Programming (2007) 109:115–154Crossref, Google Scholar
• Arnold L. R., Bellmore M. A bounding minimization problem for primal integer programming. Oper. Res. (1974a) 22:383–392Link, Google Scholar
• Arnold L. R., Bellmore M. A generated cut for primal integer programming. Oper. Res. (1974b) 22:137–143Link, Google Scholar
• Arnold L. R., Bellmore M. Iteration skipping in primal integer programming. Oper. Res. (1974c) 22:129–136Link, Google Scholar
• Atamtürk A. On the facets of the mixed-integer knapsack polyhedron. Math. Programming (2003) 98:145–175Crossref, Google Scholar
• Atamtürk A. Sequence independent lifting for mixed-integer programming. Oper. Res. (2004) 52:487–490Link, Google Scholar
• Atamtürk A., Nemhauser G. L., Savelsbergh M. W. P. Conflict graphs in solving integer programming problems. Eur. J. Oper. Res. (2000) 121:40–55Crossref, Google Scholar
• Balas E. Facets of the knapsack polytope. Math. Programming (1975) 8:146–164Crossref, Google Scholar
• Balas E., Zemel E. Facets of knapsack polytope from minimal covers. SIAM J. Appl. Math. (1984) 34:119–148Crossref, Google Scholar
• Ben-Israel A., Charnes A. On some problems of diophantine programming. Cahiers du Centre d'Etudes de Recherche Operationelle (1962) 4:215–280Google Scholar
• Bixby R. E., Boyd E. A., Indovina R. R. MIPLIB: A test set of mixed integer programming problems. SIAM News (1992) 25:16Google Scholar
• Ceria S., Cordier C., Marchand H., Wolsey L. A. Cutting planes for integer programs with general integer variables. Math. Programming (1998) 81:201–214Crossref, Google Scholar
• Chvátal V.Linear Programming (1983) (W. H. Freeman and Company, New York) Google Scholar
• Dietrich B. L., Escudero L. F. Coefficient reduction for knapsack-like constraints in 0–1 program with variable upper bounds. Oper. Res. Lett. (1990) 2:9–14Crossref, Google Scholar
• Garfinkel R. S., Nemhauser G. L.Integer Programming (1972) (Wiley-Interscience, New York) Google Scholar
• Glover F. A new foundation for a simplified primal integer programming algorithm. Oper. Res. (1968) 16:724–740Link, Google Scholar
• Gomory R. E. An algorithm for the mixed-integer problem. (1960) . Report P-1885, The Rand Corporation, Santa Monica, CAGoogle Scholar
• Gu Z., Nemhauser G. L., Savelsbergh M. W. P. Lifted flow covers for mixed 0–1 integer programs. Math. Programming (1999) 85:439–467Crossref, Google Scholar
• Gu Z., Nemhauser G. L., Savelsbergh M. W. P. Sequence independent lifting in mixed integer programming. J. Combin. Optim. (2000) 4:109–129Crossref, Google Scholar
• Guignard M., Spielberg K. Logical reduction methods in 0–1 programming. Oper. Res. (1981) 29:49–74Link, Google Scholar
• Hammer P. L., Johnson E. L., Peled U. N. Facets of regular 0–1 polytopes. Math. Programming (1975) 8:179–206Crossref, Google Scholar
• Haus U., Köppe M., Weismantel R. A primal all-integer algorithm based on irreducible solutions. Math. Programming (2003) 96:205–246Crossref, Google Scholar
• Henk M., Köppe M., Weismantel R. Integral decomposition of polyhedra and some applications in mixed integer programming. Math. Programming (2003) 94:193–206Crossref, Google Scholar
• Hoffman K. L., Padberg M. Improving LP-representation of zero-one linear programs for branch-and-cut. ORSA J. Comput. (1991) 3:121–134Link, Google Scholar
• Johnson E. L., Kostreva M., Suhl U. H. Solving 0–1 integer programming problems arising from large-scale planning models. Oper. Res. (1981) 33:803–819Link, Google Scholar
• Johnson E. L., Nemhauser G. L., Savelsbergh M. W. P. Progress in linear programming-based algorithms for integer programming: An exposition. INFORMS J. Comput. (2000) 12:2–23Link, Google Scholar
• Kaparis K., Letchford A. N. Local and global lifted cover inequalities for the multidimensional knapsack problem. Eur. J. Oper. Res. (2008) 186:91–103Crossref, Google Scholar
• Köppe M., Weismantel R. An algorithm for mixed integer optimization. Math. Programming (2003) 98:281–308Crossref, Google Scholar
• Letchford A. N., Lodi A. Primal cutting plane algorithm revisited. Math. Methods Oper. Res. (2002) 56(1):67–81Crossref, Google Scholar
• Letchford A. N., Lodi A. Primal separation algorithms. Quart. J. Belgian, French Italian Oper. Res. Soc. (2003) 1:209–224Google Scholar
• Marchand H., Martin A., Weismantel R., Wolsey L. A. Cutting planes in integer and mixed integer programming. Discrete Appl. Math. (2002) 23:397–446Crossref, Google Scholar
• Martin A., Weismantel R., Bixby R. E., Boyd E. A., Ríos-Mercado R. Z. The intersection of knapsack polyhedron and extensions. Proc. 6th IPCO Conf. (1998) (Springer-Verlag, Copenhagen) 243–256Google Scholar
• Nemhauser G. L., Wolsey L. A.Integer and Combinatorial Optimization (1988) (Wiley-Interscience, New York) Crossref, Google Scholar
• Padberg M. W. On the facial structure of set packing polyhedra. Math. Programming (1973) 5:199–215Crossref, Google Scholar
• Padberg M. W. A note on zero-one programming. Oper. Res. (1975) 23:833–837Link, Google Scholar
• Padberg M. W., Hong S. On the symmetric travelling salesman problem: A computational study. Math. Programming (1980) 12:78–107Crossref, Google Scholar
• Rajan D. Designing capacitated survivable networks: Polyhedral analysis and algorithms. (2004) . Ph.D. thesis, University of California, Berkeley, BerkeleyGoogle Scholar
• Richard J.-P. P., de Farias I. R., Nemhauser G. L. Lifted inequalities for 0–1 mixed integer programming: Basic theory and algorithms. Math. Programming (2003a) 98:89–113Crossref, Google Scholar
• Richard J.-P. P., de Farias I. R., Nemhauser G. L. Lifted inequalities for 0–1 mixed integer programming: Superlinear lifting. Math. Programming (2003b) 98:115–143Crossref, Google Scholar
• Savelsbergh M. W. P. Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. (1994) 6:445–454Link, Google Scholar
• Sharma S., Sharma B. New technique for solving primal all-integer linear programming. Opsearch (1997) 34:62–68Crossref, Google Scholar
• Wolsey L. A. Facets and strong inequalities for integer programs. Oper. Res. (1976) 24:367–372Link, Google Scholar
• Wolsey L. A. Valid inequalities and superadditivity for 0–1 integer programs. Math. Oper. Res. (1977) 2:66–77Link, Google Scholar
• Young R. D. A primal (all-integer) integer programming algorithm. J. Res. National Bureau Standards (1965) 69B:213–250Crossref, Google Scholar
• Young R. D. A simplified primal (all-integer) integer programming algorithm. Oper. Res. (1968) 16:750–782Link, Google Scholar
• Young R. D. The eclectic primal algorithm: Cutting-plane method that accommodates hybrid subproblem solution techniques. Math. Programming (1975) 9:294–312Crossref, Google Scholar
• Zeng B., Richard J.-P. P. Sequence independent lifting for 0–1 knapsack problems with disjoint cardinality constraints. Optimization Online (2006) September 20). http://www.optimization-online.org/DB_HTML/2006/09/1468.htmlGoogle Scholar