Complexity of linear relaxations in integer programming

Area of Science:

• Discrete Geometry
• Integer Programming
• Computational Geometry

Background:

• The relaxation complexity, introduced by Kaibel & Weltge (2015), quantifies the minimum facets needed for a polyhedron to represent a specific set of integer points.
• This parameter is crucial for understanding the complexity of linear descriptions of integer point sets without auxiliary variables.

Purpose of the Study:

• To address open questions concerning the relaxation complexity and its variant for rational polyhedra.
• To establish new bounds and computational methods for determining the relaxation complexity.

Main Methods:

• Utilizing tools from combinatorics and the geometry of numbers.
• Applying techniques from quantifier elimination.
• Analyzing properties of integer point sets within polyhedra, including dimension, residue class representation, convex hull properties, and lattice-width.

Main Results:

• Established that the relaxation complexity is bounded for integer point sets in at most four dimensions.
• Proved bounds for sets representing all residue classes or containing an interior integer point.
• Demonstrated that relaxation complexity is algorithmically computable under specific dimensional and property-based conditions.
• Derived an improved lower bound for relaxation complexity based on the dimension of the integer point set.

Conclusions:

• Significant progress has been made in characterizing and computing the relaxation complexity of integer point sets.
• The findings provide a deeper understanding of the complexity of integer descriptions in polyhedra.
• New conditions and computational approaches enhance the practical applicability of relaxation complexity in related fields.