Complexity Bounds for Block-IPs

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.


Logo BII


Use and reproduction:

No license. The provisions of the German Copyright Act (UrhG) apply.

Please note that individual components of the publication may be subject to other licensing or copyright conditions.


Citation style:
Could not load citation form.