Complexity of linear relaxations in integer programming
成果类型：
Article
署名作者：
Averkov, Gennadiy; Schymura, Matthias
署名单位：
Brandenburg University of Technology Cottbus
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-021-01623-4
发表日期：
2022
页码：
191-227
关键词：
摘要：
For a set X of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with X is called the relaxation complexity rc(X). This parameter, introduced by Kaibel & Weltge (2015), captures the complexity of linear descriptions of X without using auxiliary variables. Using tools from combinatorics, geometry of numbers, and quantifier elimination, we make progress on several open questions regarding rc(X) and its variant rcQ(X), restricting the descriptions of X to rational polyhedra. As our main results we show that rc(X) = rc(Q)(X) when: (a) X is at most four-dimensional, (b) X represents every residue class in (Z/2Z)(d), (c) the convex hull of X contains an interior integer point, or (d) the lattice-width of X is above a certain threshold. Additionally, rc(X) can be algorithmically computed when X is at most three-dimensional, or X satisfies one of the conditions (b), (c), or (d) above. Moreover, we obtain an improved lower bound on rc(X) in terms of the dimension of X.
来源URL：