[en] The set obtained by adding all cuts whose validity follows from a maximal lattice free polyhedron with max-facet-width at most w is called the w th split closure. We show the w th split closure is a polyhedron. This generalizes a previous result showing this to be true when w = 1. We also consider the design of finite cutting plane proofs for the validity of an inequality. Given a measure of “size” of a maximal lattice free polyhedron, a natural question is how large a size s of a maximal lattice free polyhedron is required to design a finite cutting plane proof for the validity of an inequality. We characterize s based on the faces of the linear relaxation of the mixed integer linear set.
Disciplines :
Mathematics
Author, co-author :
Andersen, Kent; Otto-von-Guericke Universität Magdeburg > Institut für Mathematische Optimierung
Louveaux, Quentin ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Optimisation discrète
Weismantel, Robert; Otto-von-Guericke Universituat Magdeburg > Institut für Mathematische Optimierung
Language :
English
Title :
An analysis of mixed integer linear sets based on lattice point free convex sets
Andersen, K., G. Cornuéjols, Y. Li. 2005. Split closure and intersection cuts. Math. Programming Ser. A 102 457-493.
Andersen, K., Q. Louveaux, R. Weismantel. 2008. Certificates of linear mixed integer infeasibility. Oper. Res. Lett.
Balas, E. 1971 Intersection cuts-A new type of cutting plane for integer programming. Oper. Res. 19 19-39.
Balas, E. 1979. Disjunctive programming. Ann. Discrete Math. 5 517-546.
Cook, W. J., R. Kannan, A. Schrijver. 1990. Chvátal closures for mixed integer programming problems. Math. Programming 47 155-174.
Cornuéjols, G. 2008. Valid inequalities for mixed integer linear programs. Math. Programming Ser. B 112 3-44.
Lovász, L. 1989. Geometry of numbers and integer programming. M. Iri, K. Tanabe, eds. Math. Programming, Recent Developments and Applications. Kluwer, Dordrecht, The Netherlands, 177-210.
Rockafellar, R. T. 1970. Convex Analysis. Princeton University Press, Princeton, NJ.