Complexity Bounds for Block-IPs

zum Volltext (421 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • Juni 2021
Seitenbereich31 Seiten

We consider integer programs (IPs) with a certain block structure, called two-stage stochastic. A two-stage stochastic IP is an integer program of the form $\min\{c^Tx \mid Ax=b,\, \ell\leq x\leq u,\, x\in \mathbb{Z}^{s + nt}\}$ where the constraint matrix $A\in \mathbb{Z}^{rn \times s+tn}$ consists of blocks $A^{(i)} \in \mathbb{Z}^{r\times s}$ on a vertical line and blocks $B^{(i)}\in \mathbb{Z}^{r\times t}$ on the diagonal line aside. We improve the bound for the Graver complexity of two-stage stochastic IPs.
Our bound of $3^{O(s^s(2r||A||_\infty+1)^{rs})}$ reduces the dependency from $rs^2$ to $rs$ and is asymptotically tight under the exponential time hypothesis in the case that $r=1$. The improved Graver complexity bound stems from improved bounds on the intersection for a class of structurally rich integer cones. Our bound of $3^{O(d\Delta)^d}$ for dimension $d$ and absolute entries bounded by $\Delta$ is independent of the number of intersected integer cones. We investigate special properties of this class, which is complemented by the fact that these properties do not hold for general integer cones. Moreover, we give structural characterizations of this class that admit their use for two-stage stochastic IPs.
Statische URL
IDNummer des Berichts :
  • TR_2101