An Analysis of Mixed Integer Linear Sets Based on Lattice Point Free Convex Sets

• 成果类型: Article
• 署名作者: Andersen, Kent; Louveaux, Quentin; Weismantel, Robert
• 署名单位: Otto von Guericke University; University of Liege
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1090.0439
• 发表日期: 2010
• 页码: 233-256
• 关键词: intersection cuts

摘要

A maximal lattice free polyhedron L has max-facet-width equal to w if max(x is an element of L) pi(T) x-min(x is an element of L) pi(T) x <= w for all facets pi(T) x <= pi(0) of L, and max(x is an element of L) pi(T) x-min(x is an element of L) pi(T) x = w for some facet pi(T) x <= pi(0) of L. 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 wth split closure. We show the wth 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.