Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs

DOI10.1007/s10107-012-0615-yzbMath1291.90143OpenAlexW2135791976MaRDI QIDQ2452371

Simge Küçükyavuz, Dinakar Gade, Suvrajeet Sen

Publication date: 2 June 2014

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

Full work available at URL: https://doi.org/10.1007/s10107-012-0615-y

zbMATH Keywords

finite convergenceBenders' decompositionGomory cutslexicographic dual simplex\(L\)-shaped methodtwo-stage stochastic integer programs

Mathematics Subject Classification ID

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

Related Items

Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs, About the Complexity of Two-Stage Stochastic IPs, Cutting planes for the multistage stochastic unit commitment problem, An approximation framework for two-stage ambiguous stochastic integer programs under mean-MAD information, Towards a sustainable power grid: stochastic hierarchical planning for high renewable integration, Stochastic Planning and Scheduling with Logic-Based Benders Decomposition, Integrated Backup Rolling Stock Allocation and Timetable Rescheduling with Uncertain Time-Variant Passenger Demand Under Disruptive Events, Optimal crashing of an activity network with disruptions, Stochastic programming analysis and solutions to schedule overcrowded operating rooms in China, Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables, Logic-Based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling, Decomposition Algorithms for Two-Stage Distributionally Robust Mixed Binary Programs, Convex approximations for two-stage mixed-integer mean-risk recourse models with conditional value-at-risk, A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation, On Generating Lagrangian Cuts for Two-Stage Stochastic Integer Programs, Benders-type branch-and-cut algorithms for capacitated facility location with single-sourcing, Chance-constrained optimization under limited distributional information: a review of reformulations based on sampling and distributional robustness, A solution algorithm for chance-constrained problems with integer second-stage recourse decisions, Tight Second Stage Formulations in Two-Stage Stochastic Mixed Integer Programs, Integer set reduction for stochastic mixed-integer programming, Algorithm for the N-2 Security-Constrained Unit Commitment Problem with Transmission Switching, Scenario-based cuts for structured two-stage stochastic and distributionally robust \(p\)-order conic mixed integer programs, A loose Benders decomposition algorithm for approximating two-stage mixed-integer recourse models, A two-stage stochastic programming approach for influence maximization in social networks, The ancestral Benders' cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming, Higher-order total variation bounds for expectations of periodic functions and simple integer recourse approximations, A progressive hedging based branch-and-bound algorithm for mixed-integer stochastic programs, A finite \(\epsilon\)-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and second-stage variables, A generalized Benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary first and second stage variables, A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management, Pseudo-Valid Cutting Planes for Two-Stage Mixed-Integer Stochastic Programs with Right-Hand-Side Uncertainty, On solving two-stage distributionally robust disjunctive programs with a general ambiguity set, Improving the Integer L-Shaped Method, A decomposition method for distributionally-robust two-stage stochastic mixed-integer conic programs, A Unified Framework for Multistage Mixed Integer Linear Optimization, An L-shaped method with strengthened lift-and-project cuts, A binary decision diagram based algorithm for solving a class of binary two-stage stochastic programs, Nonlinear chance-constrained problems with applications to hydro scheduling, About the complexity of two-stage stochastic IPs

Uses Software

• SCIP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Progress in computational mixed integer programming -- a look back from the other side of the tipping point
• A modification of Benders' decomposition algorithm for discrete subproblems: An approach for stochastic programs with integer recourse
• Lexicography and degeneracy: Can a pure cutting plane algorithm work?
• The integer \(L\)-shaped method for stochastic integer programs with complete recourse
• SCIP: solving constraint integer programs
• A comparative study of decomposition algorithms for stochastic combinatorial optimization
• A multicut algorithm for two-stage stochastic linear programs
• Partitioning procedures for solving mixed-variables programming problems
• An upper bound on the number of cuts needed in Gomory's method of integer forms
• A cutting-plane approach to mixed 0-1 stochastic integer programs
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis reductions
• L-shaped decomposition of two-stage stochastic programs with integer recourse
• Some complexity results for polynomial ideals
• A finite branch-and-bound algorithm for two-stage stochastic integer programs
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming
• The million-variable ``march for stochastic combinatorial optimization
• Two-stage integer programs with stochastic right-hand sides: A superadditive dual approach
• On solving discrete two-stage stochastic programs having mixed-integer first- and second-stage variables
• Some polyhedra related to combinatorial problems
• Edmonds polytopes and a hierarchy of combinatorial problems
• Gomory cuts revisited
• The \(C^3\) theorem and a \(D^2\) algorithm for large scale stochastic mixed-integer programming: set convexification
• Enhanced Cut Generation Methods for Decomposition-Based Branch and Cut for Two-Stage Stochastic Mixed-Integer Programs
• Introduction to Stochastic Programming
• Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs
• Disjunctive Decomposition for Two-Stage Stochastic Mixed-Binary Programs with Random Recourse
• Continuity Properties of Expectation Functions in Stochastic Integer Programming
• Minimal Valid Inequalities for Integer Constraints
• Outline of an algorithm for integer solutions to linear programs
• On the convergence of cutting plane algorithms for a class of nonconvex mathematical programs
• The value function of an integer program
• L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming