Collapsing the Tower - On the Complexity of Multistage Stochastic IPs

In this paper we study the computational complexity of solving a class of block structured integer programs (IPs) -so called multistage stochastic IPs. A multistage stochastic IP is an IP of the form maxc T x | Ax = b, l ≤ x ≤ u, x integral where the constraint matrix A consists of small block matrices ordered on the diagonal line and for each stage there are larger blocks with few columns connecting the blocks in a tree like fashion. Over the last years there was enormous progress in the area of block structured IPs. For many of the known block IP classes -such as n-fold, tree-fold, and two-stage stochastic IPs, nearly matching upper and lower bounds are known concerning their computational complexity. One of the major gaps that remained however was the parameter dependency in the running time for an algorithm solving multistage stochastic IPs. Previous algorithms require a tower of t exponentials, where t is the number of stages, while only a double exponential lower bound was known. In this paper we show that the tower of t exponentials is actually not necessary. We can show an improved running time for the algorithm solving multistage stochastic IPs with a running time of 2

• poly(d, n), where d is the sum of columns in the connecting blocks and n is the number of blocks on the lowest stage. Hence, we obtain the first bound by an elementary function for the running time of an algorithm solving multistage stochastic IPs. In contrast to previous works, our algorithm has only a triple exponential dependency on the parameters and only doubly exponential for every constant t. By this we come very close the known double exponential bound (based on the exponential time hypothesis) that holds already for two-stage stochastic IPs, i.e. multistage stochastic IPs with only two stages.

The improved running time of the algorithm is based on new bounds for the proximity of multistage stochastic IPs. The idea behind the bound is based on generalization for a structural lemma originally used for two-stage stochastic IPs. While the structural lemma requires iteration to be applied to multistage stochastic IPs, our generalization directly applies to inherent combinatorial properties of multiple stages. Already a special case of our lemma yields an improved bound for the Graver Complexity of multistage stochastic IPs.