Computational aspects of relaxation complexity (Q2061898)

This article considers the relaxation complexity of a set of integer points that are contained inside the facets of a linear polyhedron. This is of importance for integer programming as good relaxation methods result in more efficient solution algorithms. The authors begin with an introduction to the problem and a number of definitions and background theorems. They then derive estimations of the relaxation complexity, that is the smallest number of facets which coincide with the integer points of the polyhedron, including a variant where the relaxation complexity is calculated using rational polyhedra. Several interesting theorems are presented with proof and detailed examples help to understand the propositions. Some numerical experiments on the calculation of the number of facets are presented at the end of the article. For the entire collection see [Zbl 1476.90004].