About the Complexity of Two-Stage Stochastic IPs

DOI10.1007/978-3-030-45771-6_20MaRDI QIDQ5041750zbMATH OpenOpenAlexFDO

Authors Kim-Manuel Klein

Publication date 14 October 2022

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.01135

zbMATH Keywords

2-stage stochastic programmingGraver complexityinteger programming

Mathematics Subject Classification ID

Integer programming (90C10) Stochastic programming (90C15)

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}xmidAx=b,lleqxlequ,xinmathbb{Z}^{nt+s}$ where the constraint matrix $Ainmathbb{Z}^{rimess}$ consists roughly of $n$ repetition of a block matrix $A$ on the vertical line and $n$ repetitions of a matrix $Binmathbb{Z}^{rimest}$ on the diagonal. In this paper we improve upon an algorithmic result by Hemmecke and Schultz form 2003 to solve $2$-stage stochastic IPs. 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. Our new improved bound however is obtained by a novel theorem which argues about the intersection of paths in a vector space. As a result of our new bound we obtain an algorithm to solve $2$-stage stochastic IPs in time $poly(n,t)cdotf(r,s,Delta)$, where $f$ is a doubly exponential function. To complement our result, we also prove a doubly exponential lower bound for the size of the augmenting steps.

Recommendations

• About the complexity of two-stage stochastic IPs
• On complexity of multistage stochastic programs
• A note on sample complexity of multistage stochastic programs
• On complexity of multistage stochastic programs under heavy tailed distributions
• On complexity of stochastic programming problems
• A Probabilistic Lower Bound for Two-Stage Stochastic Programs
• Complexity of stochastic dual dynamic programming
• Approximation Algorithms for 2-Stage Stochastic Optimization Problems
• Two‐stage stochastic integer programming: a survey

Cites work

• A finite branch-and-bound algorithm for two-stage stochastic integer programs
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• Algebraic and geometric ideas in the theory of discrete optimization
• An integer analogue of Carathéodory's theorem
• Analytical Evaluation of Hierarchical Planning Systems
• Combinatorial \(n\)-fold integer programming and applications
• Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs
• Decomposition of test sets in stochastic integer programming
• Empowering the configuration-IP -- new PTAS results for scheduling with setups times
• Faster Algorithms for Integer Programs with Block Structure
• Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs
• Finiteness theorems in stochastic integer programming
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 663895 (Why is no real title available?)
• scientific article; zbMATH DE number 6850361 (Why is no real title available?)
• Introduction to stochastic programming.
• L-shaped decomposition of two-stage stochastic programs with integer recourse
• Minkowski's Convex Body Theorem and Integer Programming
• Near-linear time algorithm for \(n\)-fold ILPs via color coding
• On the foundations of linear and integer linear programming I
• On the lengths of bad sequences of monomial ideals over polynomial rings
• Optimizing electricity distribution using two-stage integer recourse models
• Scheduling meets n-fold integer programming
• Tight complexity lower bounds for integer linear programming with few constraints
• Two‐stage stochastic integer programming: a survey
• Value of the Steinitz constant
• Voting and bribing in single-exponential time

Cited in

(10)

• About the complexity of two-stage stochastic IPs
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• Finiteness theorems in stochastic integer programming
• Integer programming in parameterized complexity: five miniatures
• Block-structured integer programming: can we parameterize without the largest coefficient?
• scientific article; zbMATH DE number 7651172 (Why is no real title available?)
• The double exponential runtime is tight for 2-stage stochastic ILPs
• The double exponential runtime is tight for 2-stage stochastic ILPs
• Collapsing the tower -- on the complexity of multistage stochastic IPs
• Collapsing the tower -- on the complexity of multistage stochastic IPs

This page was built for publication: About the Complexity of Two-Stage Stochastic IPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041750)