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.

Vorschau

Logo BII

BII

Rechte

Nutzung und Vervielfältigung:

Keine Lizenz. Es gelten die Bestimmungen des deutschen Urheberrechts (UrhG).

Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.