Lower bounds on the sizes of integer programs without additional variables (Q896270)

This article studies the smallest number of facets that a polyhedron can have and which contains a given set of integer points. The authors begin with the necessary background to this problem and the existing research on relaxation complexity in linear programs. This is followed in the second section by the preliminary propositions on polyhedra and facet defining inequalities. The third and fourth section consider the notion of relaxation complexity and the derivation with proof of the lower bounds on this quantity, which is the core contribution of the paper. The article concludes with a section on the importance of having rational coordinates in the description of the relaxation and a list of relevant references.