论文标题
理性在整数编程放松中的作用
The role of rationality in integer-programming relaxations
论文作者
论文摘要
For a finite set $X \subset \mathbb{Z}^d$ that can be represented as $X = Q \cap \mathbb{Z}^d$ for some polyhedron $Q$, we call $Q$ a relaxation of $X$ and define the relaxation complexity $rc(X)$ of $X$ as the least number of facets among all possible relaxations $Q$ of $X$.理性放松复杂性$ rc_ \ mathbb {q}（x）$将$ rc（x）$的定义限制为理性polyhedra $ q $。在本文中，我们专注于$ x =δ_d$，标准单纯胶的顶点集，由null vector和标准单位向量组成，$ \ mathbb {r}^d $。我们证明每$ d \ geq 5 $ $ rc（Δ_d）\ leq d $。也就是说，由于$ rc _ {\ mathbb {q}}}}（Δ_d）= d+1 $，因此非理性可以减少放松的最小尺寸。这回答了Kaibel和Weltge提出的一个空旷的问题（在没有其他变量的整数程序的大小上，数学编程，154（1）：407-425，2015）。此外，我们证明了o（\ frac {d} {\ sqrt {\ sqrt {\ log（d）}）$的渐近语句$ rc（δ_d）\ in o（\ frac {d} {\ sqrt {\ sqrt {\ sqrt {\ log（d）}）$，这表明比率$ $ rc（Δ_d）/rc _ {rc _ {\ nathbb {q} {q}}} $ d $ d $ do $ doves $ goves $ goves $ gond $ goves und tes $，
For a finite set $X \subset \mathbb{Z}^d$ that can be represented as $X = Q \cap \mathbb{Z}^d$ for some polyhedron $Q$, we call $Q$ a relaxation of $X$ and define the relaxation complexity $rc(X)$ of $X$ as the least number of facets among all possible relaxations $Q$ of $X$. The rational relaxation complexity $rc_\mathbb{Q}(X)$ restricts the definition of $rc(X)$ to rational polyhedra $Q$. In this article, we focus on $X = Δ_d$, the vertex set of the standard simplex, which consists of the null vector and the standard unit vectors in $\mathbb{R}^d$. We show that $rc(Δ_d) \leq d$ for every $d \geq 5$. That is, since $rc_{\mathbb{Q}}(Δ_d)=d+1$, irrationality can reduce the minimal size of relaxations. This answers an open question posed by Kaibel and Weltge (Lower bounds on the size of integer programs without additional variables, Mathematical Programming, 154(1):407-425, 2015). Moreover, we prove the asymptotic statement $rc(Δ_d) \in O(\frac{d}{\sqrt{\log(d)}})$, which shows that the ratio $rc(Δ_d)/rc_{\mathbb{Q}}(Δ_d)$ goes to $0$, as $d\to \infty$.
