N&O seminar: Kim-Manuel Klein (Kiel University)

Everyone is welcome to attend the N&O seminar by Kim-Manuel Klein with the title 'About the Complexity of 2-Stage Stochastic IPs'.
  • What Networks & Optimization English Seminars
  • When 24-09-2019 from 11:00 to 12:00 (Europe/Amsterdam / UTC200)
  • Where Room L016 at CWI, Science Park 123 in Amsterdam
  • Contact Name Daniel Dadush
  • Web Visit external website
  • Add event to calendar iCal

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.