Corner polyhedra and their connection with cutting planes (Q1424273): Difference between revisions

Corner polyhedra [\textit{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.