×

Corner polyhedra and their connection with cutting planes. (English) Zbl 1082.90145

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.

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)

Citations:

Zbl 0245.90019
PDFBibTeX XMLCite
Full Text: DOI