About the complexity of two-stage stochastic IPs

DOI10.1007/S10107-021-01698-ZMaRDI QIDQ2118129zbMATH OpenOpenAlexFDO

Authors Kim-Manuel Klein

Publication date 22 March 2022

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10107-021-01698-z

zbMATH Keywords

integer programmingparameterized compexitystochastic programmingtwo-stage stochastic

Mathematics Subject Classification ID

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

Recommendations

• About the Complexity of Two-Stage Stochastic IPs
• The double exponential runtime is tight for 2-stage stochastic ILPs
• The double exponential runtime is tight for 2-stage stochastic ILPs
• Two-stage quadratic integer programs with stochastic right-hand sides
• scientific article; zbMATH DE number 1688600

Cites work

• A finite branch-and-bound algorithm for two-stage stochastic integer programs
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• 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
• 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 1688599 (Why is no real title available?)
• 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?)
• scientific article; zbMATH DE number 7651172 (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
• Optimizing electricity distribution using two-stage integer recourse models
• Scheduling meets n-fold integer programming
• Two‐stage stochastic integer programming: a survey
• Value of the Steinitz constant
• Voting and bribing in single-exponential time

Cited in

(13)

• About the Complexity of Two-Stage Stochastic IPs
• The double exponential runtime is tight for 2-stage stochastic ILPs
• Optimizing low dimensional functions over the integers
• An approximated dynamic programming model for the supply vessel fleet sizing problem
• Collapsing the tower -- on the complexity of multistage stochastic IPs
• FPT algorithms for a special block-structured integer program with applications in scheduling
• Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
• (Near)-optimal algorithms for sparse separable convex integer programs
• Parameterized algorithms for block-structured integer programs with large entries
• Tight lower bounds for block-structured integer programs
• Tight lower bounds for block-structured integer programs
• Decomposition algorithms for computational stochastic mixed-integer programming: a survey
• Solving 4-block integer linear programs faster using affine decompositions of the right-hand sides

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 Q2118129)