Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms

DOI10.1002/NET.21922MaRDI QIDQ6087397zbMATH OpenFDO

Authors

Publication date 15 November 2023

Published in Networks (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1002/NET.21922

zbMATH Keywords

Benders decompositioncombinatorial optimizationcomplexityminimum \(s - t\) cut problemtotal unimodularitytwo-stage stochastic programming

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Recommendations

• Solving two-stage stochastic Steiner tree problems by two-stage branch-and-cut
• Stochastic survivable network design problems: theory and practice
• On the two-stage stochastic graph partitioning problem
• Decomposition methods for the two-stage stochastic Steiner tree problem
• Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse

Cites work

• L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
• A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
• A new approach to the minimum cut problem
• A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
• Algebraic methods for stochastic minimum cut and maximum flow problems
• Applications of Stochastic Programming
• Bounds on expected performance of networks with links subject to failure
• Combining sampling-based and scenario-based nested Benders decomposition methods: application to stochastic dual dynamic programming
• Convexity and decomposition of mean-risk stochastic programs
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 53949 (Why is no real title available?)
• scientific article; zbMATH DE number 1312984 (Why is no real title available?)
• scientific article; zbMATH DE number 2121076 (Why is no real title available?)
• Improved approximations for two-stage MIN-cut and shortest path problems under uncertainty
• Introduction to Stochastic Programming
• LP Rounding Approximation Algorithms for Stochastic Network Design
• Maximal Flow Through a Network
• Network flows. Theory, algorithms, and applications.
• On structure and stability in stochastic programs with random technology matrix and complete integer recourse
• On the history of the transportation and maximum flow problems
• On the random 2-stage minimum spanning tree
• On Two-Stage Stochastic Minimum Spanning Trees
• Partitioning procedures for solving mixed-variables programming problems
• Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems
• Practical minimum cut algorithms
• Selected Applications of Minimum Cuts in Networks
• Single Commodity Representation of Multicommodity Networks
• The Benders decomposition algorithm: a literature review
• The Complexity of Multiterminal Cuts
• The value of information in stochastic maximum flow problems
• Two-stage robust network design with exponential scenarios
• Unimodular matrices of flow problems with additional constraints

Cited in

(2)

• Risk‐averse optimization and resilient network flows
• An exact algorithm for maximum electric vehicle flow coverage problem with heterogeneous chargers, nonlinear charging time and route deviations

This page was built for publication: Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms

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