The \(C^3\) theorem and a \(D^2\) algorithm for large scale stochastic mixed-integer programming: set convexification

DOI10.1007/S10107-004-0566-ZzbMath1159.90464OpenAlexW1964974282MaRDI QIDQ2570997

Suvrajeet Sen, Julia L. Higle

Publication date: 31 October 2005

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

Full work available at URL: https://doi.org/10.1007/s10107-004-0566-z

zbMATH Keywords

Cutting Plane AlgorithmsDisjunctive ProgrammingStochastic Mixed-Integer Programming

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Stochastic programming (90C15)

Related Items (67)

Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs ⋮ Cutting planes for the multistage stochastic unit commitment problem ⋮ On a mixture of the fix-and-relax coordination and Lagrangian substitution schemes for multistage stochastic mixed integer programming ⋮ An approximation framework for two-stage ambiguous stochastic integer programs under mean-MAD information ⋮ 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 ⋮ K-Adaptability in Two-Stage Robust Binary Programming ⋮ Theoretical challenges towards cutting-plane selection ⋮ An extended formulation for two-stage stochastic unit commitment with reserves ⋮ Two-stage stochastic programming supply chain model for biodiesel production via wastewater treatment ⋮ Stochastic multi-site capacity planning of TFT-LCD manufacturing using expected shadow-price based decomposition ⋮ An exact algorithm for solving large-scale two-stage stochastic mixed-integer problems: some theoretical and experimental aspects ⋮ Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables ⋮ Mathematical programming formulations for approximate simulation of multistage production systems ⋮ Stochastic and risk management models and solution algorithm for natural gas transmission network expansion and LNG terminal location planning ⋮ Decomposition Algorithms for Two-Stage Distributionally Robust Mixed Binary Programs ⋮ A stochastic programming approach for chemotherapy appointment scheduling ⋮ Convex approximations for two-stage mixed-integer mean-risk recourse models with conditional value-at-risk ⋮ On Generating Lagrangian Cuts for Two-Stage Stochastic Integer Programs ⋮ Fenchel decomposition for stochastic mixed-integer programming ⋮ Strong Formulations for Multistage Stochastic Self-Scheduling Unit Commitment ⋮ 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 ⋮ Lagrangian decomposition for large-scale two-stage stochastic mixed 0-1 problems ⋮ A solution algorithm for chance-constrained problems with integer second-stage recourse decisions ⋮ Stochastic last mile relief network design with resource reallocation ⋮ Totally unimodular stochastic programs ⋮ Tight Second Stage Formulations in Two-Stage Stochastic Mixed Integer Programs ⋮ Integer set reduction for stochastic mixed-integer programming ⋮ A decomposition approach for solving a broadcast domination network design problem ⋮ A decomposition approach to the two-stage stochastic unit commitment problem ⋮ Convex approximations for a class of mixed-integer recourse models ⋮ Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function ⋮ Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs ⋮ Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic Programs ⋮ Computations with disjunctive cuts for two-stage stochastic mixed 0-1 integer programs ⋮ A Stochastic Integer Programming Approach to Air Traffic Scheduling and Operations ⋮ 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 ⋮ 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 ⋮ Two-Stage Stochastic Mixed-Integer Programs: Algorithms and Insights ⋮ The Benders decomposition algorithm: a literature review ⋮ A finite \(\epsilon\)-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and second-stage variables ⋮ A Convex Approximation for Two-Stage Mixed-Integer Recourse Models with a Uniform Error Bound ⋮ Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming ⋮ Stochastic set packing problem ⋮ 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 ⋮ Decomposition methods for global solution of mixed-integer linear programs ⋮ A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management ⋮ A comparative study of decomposition algorithms for stochastic combinatorial optimization ⋮ A general algorithm for solving two-stage stochastic mixed \(0-1\) first-stage problems ⋮ Effects of feasibility cuts in Lagrangian relaxation for a two-stage stochastic facility location and network flow problem ⋮ Disjunctive Decomposition for Two-Stage Stochastic Mixed-Binary Programs with Generalized Upper Bound Constraints ⋮ Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs ⋮ 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 ⋮ Cutting plane algorithms for solving a stochastic edge-partition problem ⋮ Multistage Stochastic Power Generation Scheduling Co-Optimizing Energy and Ancillary Services ⋮ Parametric error bounds for convex approximations of two-stage mixed-integer recourse models with a random second-stage cost vector ⋮ 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

Uses Software

• Tabu search
• Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The integer \(L\)-shaped method for stochastic integer programs with complete recourse
• A branch and bound algorithm for extreme point mathematical programming problems
• Partitioning procedures for solving mixed-variables programming problems
• Optimization with disjunctive constraints
• Facial disjunctive programs and sequences of cutting-planes
• Relaxations for probabilistically constrained programs with discrete random variables
• A cutting-plane approach to mixed 0-1 stochastic integer programs
• Stochastic integer programming: general models and algorithms
• Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis reductions
• Progressive hedging and tabu search applied to mixed integer (0,1) multistage stochastic programming
• A modified lift-and-project procedure
• Epigraphical nesting: A unifying theory for the convergence of algorithms
• On the convex hull of the simple integer recourse objective function
• A closed-form representation of mixed-integer program value functions
• An algorithm for the construction of convex hulls in simple integer recourse programming
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• On Optimal Allocation of Indivisibles Under Uncertainty
• Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization
• Continuity Properties of Expectation Functions in Stochastic Integer Programming
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• The Cutting-Plane Method for Solving Convex Programs
• Scenarios and Policy Aggregation in Optimization Under Uncertainty
• On the convergence of cutting plane algorithms for a class of nonconvex mathematical programs
• Facet inequalities from simple disjunctions in cutting plane theory
• A Cutting-Plane Game for Facial Disjunctive Programs
• Two stage linear programming under uncertainty with 0–1 integer first stage variables
• The value function of an integer program
• On the Convergence of Algorithms with Implications for Stochastic and Nondifferentiable Optimization
• Stochastic Programs with Fixed Recourse: The Equivalent Deterministic Program
• A Modified Benders' Partitioning Algorithm for Mixed Integer Programming
• Disjunctive Programming
• Introduction to Stochastic Programming
• Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework
• Variational Analysis
• A Geometric Buchberger Algorithm for Integer Programming
• L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
• Stochastic Lagrangian relaxation applied to power scheduling in a hydro-thermal system under uncertainty

This page was built for publication: The \(C^3\) theorem and a \(D^2\) algorithm for large scale stochastic mixed-integer programming: set convexification