论文标题
整数编程中线性放松的复杂性
Complexity of linear relaxations in integer programming
论文作者
论文摘要
对于多面体中的整数$ x $，这是任何多面体的最小数量的整数点与$ x $重合的零色调，称为放松复杂度$ \ mathrm {rc}（x）$。该参数由Kaibel＆Weltge（2015）引入，并捕获了$ x $的线性描述的复杂性，而无需使用辅助变量。 使用Combinatorics，数字的几何形状和消除量词的工具，我们在几个关于$ \ Mathrm {rc}（X）$及其变体$ \ Mathrm {rc} _ {\ Mathbb {Q}}}（x）（x）$的开放式问题上取得了进展。 作为我们的主要结果，我们表明$ \ mathrm {rc}（x）= \ mathrm {rc} _ {\ mathbb {q}}}（x）$何时：（a）$ x $最多是四维的，（b）$ x $代表$ x $ in $ x $ in $（MATHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB） $ x $的凸壳包含一个内部整数点，或（d）$ x $的晶格宽度高于一定阈值。此外，当$ x $最多是三维时，可以通过算法计算$ \ mathrm {rc}（x）$，或者$ x $满足上面的条件（b），（c）或（d）。此外，我们在$ x $的尺寸上获得了$ \ mathrm {rc}（x）$的改进的下限。
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 $\mathrm{rc}(X)$. This parameter was introduced by Kaibel & Weltge (2015) and 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 $\mathrm{rc}(X)$ and its variant $\mathrm{rc}_{\mathbb{Q}}(X)$, restricting the descriptions of $X$ to rational polyhedra. As our main results we show that $\mathrm{rc}(X) = \mathrm{rc}_{\mathbb{Q}}(X)$ when: (a) $X$ is at most four-dimensional, (b) $X$ represents every residue class in $(\mathbb{Z}/2\mathbb{Z})^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, $\mathrm{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 $\mathrm{rc}(X)$ in terms of the dimension of $X$.
