Everyone is welcome to attend the N&O seminar by Kim-Manuel Klein with the title 'About the Complexity of 2-Stage Stochastic IPs'.
Abstract:
We consider so called 2-stage stochastic integer programs (IPs) and their generalized form of multi-stage stochastic IPs. A 2-stage
stochastic IP is an integer program of the form max \{ c^T x \mid A x = b, l \leq x \leq u, x \in Z^{s + nt} \} where the constraint matrix A\in \ZZ^{r n \times s +nt} consists roughly of n repetitions of a block matrix A \in Z^{r \times s} on the vertical line and n repetitions of a matrix B \in \ZZ^{r \times t} on the diagonal. Hence it is roughly the transposed of the constraint matrix of an n-fold IP.
In this talk we present new algorithmic results on how to solve this type of IP. The algorithm is based on the Graver augmentation framework where our main contribution is to give an explicit doubly exponential bound on the size of the augmenting steps. The previous bound for the size of the augmenting steps relied on non-constructive finiteness arguments from commutative algebra and therefore only an implicit bound was known that depends on parameters r,s,t and \Delta, where \Delta is the largest entry of the constraint matrix. The new improved bound however is obtained by a novel theorem which argues about the intersection of paths in a vector space.
