Gomory, Ralph E.; Johnson, Ellis L.; Evans, Lisa Corner polyhedra and their connection with cutting planes. (English) Zbl 1082.90145 Math. Program. 96, No. 2 (B), 321-339 (2003). Corner polyhedra [R.E. Gomory, Some polyhedra related to combinatorial problems. Combinat. Struct. Appl., Proc. Calgary internat. Conf. combinat. Struct. Appl., Calgary 1969), 117 (1970; Zbl 0245.90019)] are polyhedra associated to certain relaxations of an integer programming problem. This relaxation forgets the nonnegativity constraints for all basic variables in a basic feasible solution of the linear programming relaxation. After providing background on corner polyhedra and reviewing a method for generating cutting planes from this theory for small instances, the authors present a shooting theorem that allows for an evaluation of the expected size of facets induced by the generated cuts. Experimental results are presented. Finally, it is indicated how the method can be used to generate cutting planes also for general (i.e., also large scale) integer programming problems. Reviewer: Jörg Rambau (Berlin) Cited in 1 ReviewCited in 35 Documents MSC: 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut 90C10 Integer programming 90C11 Mixed integer programming 90C27 Combinatorial optimization 52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) Keywords:corner polyhedra; integer programming; group relaxation; cutting planes; facets Citations:Zbl 0245.90019 PDFBibTeX XMLCite \textit{R. E. Gomory} et al., Math. Program. 96, No. 2 (B), 321--339 (2003; Zbl 1082.90145) Full Text: DOI