The Sample Average Approximation Method for Stochastic Discrete Optimization
From MaRDI portal
Publication:2784421
DOI10.1137/S1052623499363220zbMath0991.90090OpenAlexW1983916623WikidataQ100355948 ScholiaQ100355948MaRDI QIDQ2784421
Tito Homem-de-mello, Alexander Shapiro, Anton J. Kleywegt
Publication date: 23 April 2002
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s1052623499363220
computational complexityconvergence ratesstochastic programminglaw of large numbersMonte Carlo samplingdiscrete optimizationstopping ruleslarge deviations theorysample average approximationstochastic knapsack problem
Related Items
Fast scenario reduction by conditional scenarios in two-stage stochastic MILP problems, Periodic supply vessel planning under demand and weather uncertainty, A New Generalized Newsvendor Model with Random Demand and Cost Misspecification, Transport Map Accelerated Markov Chain Monte Carlo, Stochastic Cutting Planes for Data-Driven Optimization, Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds, A sample average approximation approach to the berth allocation problem with uncertain tides, Actor-Critic–Like Stochastic Adaptive Search for Continuous Simulation Optimization, Optimal Hour-Ahead Bidding in the Real-Time Electricity Market with Battery Storage Using Approximate Dynamic Programming, Optimization of Industrial-Scale Assemble-to-Order Systems, SAMPLE AVERAGE APPROXIMATION METHOD FOR SOLVING A DETERMINISTIC FORMULATION FOR BOX CONSTRAINED STOCHASTIC VARIATIONAL INEQUALITY PROBLEMS, Reformulation and sampling to solve a stochastic network interdiction problem, Sequential Bounding Methods for Two-Stage Stochastic Programs, Benders Decomposition for Production Routing Under Demand Uncertainty, The value and cost of more stages in stochastic programing: a statistical analysis on a set of portfolio choice problems, Chance-Constrained Programming Models and Approximations for General Stochastic Bottleneck Spanning Tree Problems, Stochastic Learning Approach for Binary Optimization: Application to Bayesian Optimal Design of Experiments, A Variable Sample-Size Stochastic Quasi-Newton Method for Smooth and Nonsmooth Stochastic Convex Optimization, Data-Driven Pricing for a New Product, Performance of a coordinate search ANN training algorithm, Integrated Multiresource Capacity Planning and Multitype Patient Scheduling, Predicting Tactical Solutions to Operational Planning Problems Under Imperfect Information, Multicomponent Maintenance Optimization: A Stochastic Programming Approach, The Risk-Averse Static Stochastic Knapsack Problem, Extreme Ray Feasibility Cuts for Unit Commitment with Uncertainty, Recourse in Kidney Exchange Programs, Risk-Averse Stochastic Programming vs. Adaptive Robust Optimization: A Virtual Power Plant Application, Block Stochastic Gradient Iteration for Convex and Nonconvex Optimization, Unnamed Item, Sample average approximation with heavier tails. I: Non-asymptotic bounds with weak assumptions and stochastic constraints, A Scalable Bounding Method for Multistage Stochastic Programs, Consistency of Monte Carlo estimators for risk-neutral PDE-constrained optimization, The role of optimization in some recent advances in data-driven decision-making, Data-Driven Approximation of Contextual Chance-Constrained Stochastic Programs, A smoothing projected HS method for solving stochastic tensor complementarity problem, Managing interruptions in appointment schedules via patient notification, Optimal subsidy design for shore power usage in ship berthing operations, Using stochastic programming to solve an outpatient appointment scheduling problem with random service and arrival times, Appointment scheduling at a multidisciplinary outpatient clinic using stochastic programming, The effect of few historical data on the performance of sample average approximation method for operating room scheduling, Mitigating Uncertainty via Compromise Decisions in Two-Stage Stochastic Linear Programming: Variance Reduction, Stochastic mathematical programs with equilibrium constraints, modelling and sample average approximation, Consistency of the Scenario Approach, Approximation Algorithms for Stochastic and Risk-Averse Optimization, On Feasibility of Sample Average Approximation Solutions, Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimization, Randomized QMC Methods for Mixed-Integer Two-Stage Stochastic Programs with Application to Electricity Optimization, Penalty methods with stochastic approximation for stochastic nonlinear programming, Coordinating Pricing and Inventory Replenishment with Nonparametric Demand Learning, Single Observation Adaptive Search for Continuous Simulation Optimization, Generic Consistency for Approximate Stochastic Programming and Statistical Problems, Gradient-Based Adaptive Stochastic Search for Simulation Optimization Over Continuous Space, Scenario Generation for Single-Period Portfolio Selection Problems with Tail Risk Measures: Coping with High Dimensions and Integer Variables, Risk Averse Shortest Paths: A Computational Study, An Asymptotically Optimal Set Approach for Simulation Optimization, Surrogate-Based Promising Area Search for Lipschitz Continuous Simulation Optimization, Chance-Constrained Surgery Planning Under Conditions of Limited and Ambiguous Data, Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic Programs, A Stochastic Integer Programming Approach to Air Traffic Scheduling and Operations, Simulation-Based Optimality Tests for Stochastic Programs, A Sequential Algorithm for Solving Nonlinear Optimization Problems with Chance Constraints, Combining Progressive Hedging with a Frank--Wolfe Method to Compute Lagrangian Dual Bounds in Stochastic Mixed-Integer Programming, A Bayesian Risk Approach to Data-driven Stochastic Optimization: Formulations and Asymptotics, Unnamed Item, Learning regularization parameters of inverse problems via deep neural networks, Train Like a (Var)Pro: Efficient Training of Neural Networks with Variable Projection, Smoothing projected cyclic Barzilai–Borwein method for stochastic linear complementarity problems, Technical Note—Nonparametric Data-Driven Algorithms for Multiproduct Inventory Systems with Censored Demand, An Empirical Interpolation and Model-Variance Reduction Method for Computing Statistical Outputs of Parametrized Stochastic Partial Differential Equations, Robust Actuarial Risk Analysis, Adaptive random search for continuous simulation optimization, Discrete stochastic optimization using variants of the stochastic ruler method, Least-squares Importance Sampling for Monte Carlo security pricing, An Approximate Dynamic Programming Algorithm for Monotone Value Functions, Estimation in discrete parameter models, Simulation Optimization Using Multi-Time-Scale Adaptive Random Search, The Newsvendor under Demand Ambiguity: Combining Data with Moment and Tail Information, Stochastic polynomial optimization, On modification of population-based search algorithms for convergence in stochastic combinatorial optimization, Risk-Averse Approximate Dynamic Programming with Quantile-Based Risk Measures, Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models, Approximation Algorithms for a Class of Stochastic Selection Problems with Reward and Cost Considerations, Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls, Technical Note—Perishable Inventory Systems: Convexity Results for Base-Stock Policies and Learning Algorithms Under Censored Demand, Risk-Averse Two-Stage Stochastic Program with Distributional Ambiguity, Robust Quadratic Programming with Mixed-Integer Uncertainty, Pseudo-Valid Cutting Planes for Two-Stage Mixed-Integer Stochastic Programs with Right-Hand-Side Uncertainty, Statistical Optimization in High Dimensions, An Uncertainty-Weighted Asynchronous ADMM Method for Parallel PDE Parameter Estimation, Stochastic Decomposition for Two-Stage Stochastic Linear Programs with Random Cost Coefficients, A Multistage Stochastic Programming Approach to the Optimal Surveillance and Control of the Emerald Ash Borer in Cities, Nonparametric Learning Algorithms for Joint Pricing and Inventory Control with Lost Sales and Censored Demand, A Note on Appointment Scheduling with Piecewise Linear Cost Functions, Optimal FCFS allocation rules for periodic‐review assemble‐to‐order systems, Quantitative Stability and Empirical Approximation of Risk-Averse Models Induced by Two-Stage Stochastic Programs with Full Random Recourse, Unnamed Item, Overlapping Batches for the Assessment of Solution Quality in Stochastic Programs, Bias Reduction in Sample-Based Optimization, Data-Driven Optimization: A Reproducing Kernel Hilbert Space Approach, A sampling-based stochastic winner determination model for truckload service procurement, Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs, Measuring and optimizing system reliability: a stochastic programming approach, When it is worthwhile to work with the stochastic RCPSP?, A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem, Comments on: On a mixture of the fix-and-relax coordination and Lagrangean substitution schemes for multistage stochastic mixed integer programming, A stochastic program to evaluate disruption mitigation investments in the supply chain, Supply chain design for unlocking the value of remanufacturing under uncertainty, Tactical berth allocation under uncertainty, A generic stochastic model for supply-and-return network design, SAA method based on modified Newton method for stochastic variational inequality with second-order cone constraints and application in portfolio optimization, Capacitated dynamic production and remanufacturing planning under demand and return uncertainty, A two-stage approach to the orienteering problem with stochastic weights, A sample average approximation method for disassembly line balancing problem under uncertainty, Network design in scarce data environment using moment-based distributionally robust optimization, Flexible solutions to maritime inventory routing problems with delivery time windows, A long-term capacity expansion planning model for an electric power system integrating large-size renewable energy technologies, A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs, Applying ranking and selection procedures to long-term mitigation for improved network restoration, Stochastic programming analysis and solutions to schedule overcrowded operating rooms in China, Multi-leader multi-follower model with aggregative uncertainty, On component commonality for periodic review assemble-to-order systems, Smoothing nonmonotone Barzilai-Borwein gradient method and its application to stochastic linear complementarity problems, Stochastic models for budget optimization in search-based advertising, The sample average approximation method for empty container repositioning with uncertainties, Short-term liner ship fleet planning with container transshipment and uncertain container shipment demand, Dynamic fleet scheduling with uncertain demand and customer flexibility, Confidence-based reasoning in stochastic constraint programming, Study of M-stationarity and strong stationarity for a class of SMPCC problems via SAA method, A note on sample complexity of multistage stochastic programs, Robust combinatorial optimization with variable budgeted uncertainty, Sleeping experts and bandits approach to constrained Markov decision processes, Stochastic uncapacitated hub location, Integrated demand and procurement portfolio management with spot market volatility and option contracts, Solving multistage quantified linear optimization problems with the alpha-beta nested Benders decomposition, Adaptive and nonadaptive approaches to statistically based methods for solving stochastic linear programs: a computational investigation, An optimal method for stochastic composite optimization, Sample average approximation of stochastic dominance constrained programs, Minimizing worst-case and average-case makespan over scenarios, Integrated supply chain planning under uncertainty using an improved stochastic approach, Stochastic binary problems with simple penalties for capacity constraints violations, Retrospective optimization of mixed-integer stochastic systems using dynamic simplex linear interpolation, On two-stage stochastic knapsack problems, An approximation scheme for uncertain minimax optimal control problems, Carbon-efficient deployment of electric rubber-tyred gantry cranes in container terminals with workload uncertainty, A dynamic programming strategy to balance exploration and exploitation in the bandit problem, A unified framework for stochastic optimization, Surgery sequencing to minimize the expected maximum waiting time of emergent patients, An implementable SAA nonlinear Lagrange algorithm for constrained minimax stochastic optimization problems, The empirical likelihood approach to quantifying uncertainty in sample average approximation, Managing congestion in a multi-modal transportation network under biomass supply uncertainty, A primal-dual aggregation algorithm for minimizing conditional value-at-risk in linear programs, A two-level optimization model for elective surgery scheduling with downstream capacity constraints, Maximizing performance with an eye on the finances: a chance-constrained model for football transfer market decisions, Efficient solution selection for two-stage stochastic programs, A stochastic programming model for service scheduling with uncertain demand: an application in open-access clinic scheduling, Robust optimization in the presence of uncertainty: a generic approach, ADMM-softmax: an ADMM approach for multinomial logistic regression, Stochastic global optimization using tangent minorants for Lipschitz functions, Dynamic job assignment: a column generation approach with an application to surgery allocation, A capacitated lot sizing problem with stochastic setup times and overtime, Sample average approximation of expected value constrained stochastic programs, A survey on robustness in railway planning, Whole blood or apheresis donations? A multi-objective stochastic optimization approach, Robust solution of monotone stochastic linear complementarity problems, Variable-number sample-path optimization, Multistep stochastic mirror descent for risk-averse convex stochastic programs based on extended polyhedral risk measures, A data-driven newsvendor problem: from data to decision, The stratified \(p\)-center problem, Feasible smooth method based on Barzilai-Borwein method for stochastic linear complementarity problem, Climate change and optimal energy technology R\&D policy, A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity, Stochastic task networks -- trading performance for stability, Estimation-based metaheuristics for the probabilistic traveling salesman problem, Pre-disaster investment decisions for strengthening a highway network, Sales and operations planning in systems with order configuration uncertainty, Scheduling elective surgery under uncertainty and downstream capacity constraints, Sample average approximation under non-i.i.d. sampling for stochastic empty container repositioning problem, Validation analysis of mirror descent stochastic approximation method, The static stochastic knapsack problem with normally distributed item sizes, Divide to conquer: decomposition methods for energy optimization, Sample size selection in optimization methods for machine learning, Solution quality of random search methods for discrete stochastic optimization, An integrated flight scheduling and fleet assignment problem under uncertainty, A multiobjective metaheuristic for a mean-risk static stochastic knapsack problem, Robust sample average approximation, Optimization of stochastic virus detection in contact networks, Topological optimization of reliable networks under dependent failures, Corrigendum to: ``A scenario decomposition algorithm for 0--1 stochastic programs, Home service routing and appointment scheduling with stochastic service times, Introducing statistical consistency for infinite chance constraints, Optimization of R\&D project portfolios under endogenous uncertainty, Robust allocation of operating rooms: a cutting plane approach to handle lognormal case durations, Upper bounds for the 0-1 stochastic knapsack problem and a B\&B algorithm, Solution sensitivity-based scenario reduction for stochastic unit commitment, Stochastic programming approach to optimization under uncertainty, An improved L-shaped method for solving process flexibility design problems, A single-resource allocation problem with Poisson resource requirements, Supply chain design under uncertainty using sample average approximation and dual decomposition, A practical approach for robust and flexible vehicle routing using metaheuristics and Monte Carlo sampling, Natural gas production network infrastructure development under uncertainty, Predictive stochastic programming, Sample average approximation for stochastic nonconvex mixed integer nonlinear programming via outer-approximation, Scheduling deferrable electric appliances in smart homes: a bi-objective stochastic optimization approach, A solution method for a two-dispatch delivery problem with stochastic customers, A framework for adaptive open-pit mining planning under geological uncertainty, Smoothing projected Barzilai-Borwein method for constrained non-Lipschitz optimization, Robust approximation of chance constrained DC optimal power flow under decision-dependent uncertainty, Exact solutions to a carsharing pricing and relocation problem under uncertainty, Model and solution method for mean-risk cost-based post-disruption restoration of interdependent critical infrastructure networks, Multi-commodity distribution under uncertainty in disaster response phase: model, solution method, and an empirical study, Computational strategies for non-convex multistage MINLP models with decision-dependent uncertainty and~gradual uncertainty resolution, Stochastic program for disassembly lot-sizing under uncertain component refurbishing lead times, Operating room management under uncertainty, An elective surgery scheduling problem considering patient priority, Supplier selection and order allocation in CLSC configuration with various supply strategies under disruption risk, Decision-based scenario clustering for decision-making under uncertainty, Single observation adaptive search for discrete and continuous stochastic optimization, Logarithmic sample bounds for sample average approximation with capacity- or budget-constraints, On complexity of multistage stochastic programs under heavy tailed distributions, Approximation of probabilistic constraints in stochastic programming problems with a probability measure kernel, Multi-period stochastic programming models for two-tiered emergency medical service system, An index-based deterministic convergent optimal algorithm for constrained multi-armed bandit problems, Hybrid stochastic and robust optimization model for lot-sizing and scheduling problems under uncertainties, An ADMM algorithm for two-stage stochastic programming problems, Enhancing Benders decomposition algorithm to solve a combat logistics problem, Railway disruption management: designing bus bridging services under uncertainty, Minimum penalty perturbation heuristics for curriculum-based timetables subject to multiple disruptions, Distributionally robust facility location with bimodal random demand, Stochastic optimization approaches for elective surgery scheduling with downstream capacity constraints: models, challenges, and opportunities, Product-line planning under uncertainty, Algorithms for stochastic optimization with function or expectation constraints, A sample average approximation approach for the stochastic dial-a-ride problem on a multigraph with user satisfaction, Inventory availability commitment under uncertainty in a dropshipping supply chain, An online stochastic algorithm for a dynamic nurse scheduling problem, Convex approximations for two-stage mixed-integer mean-risk recourse models with conditional value-at-risk, Augmented simulation methods for discrete stochastic optimization with recourse, Influence maximization with deactivation in social networks, An incremental bundle method for portfolio selection problem under second-order stochastic dominance, Community-based rumor blocking maximization in social networks: algorithms and analysis, The workload balancing problem at air cargo terminals, Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes, Approximability of the two-stage stochastic knapsack problem with discretely distributed weights, A scenario decomposition algorithm for 0-1 stochastic programs, An efficient linear programming based method for the influence maximization problem in social networks, Fast robust optimization using bias correction applied to the mean model, Construction of confidence absorbing sets using statistical methods, On a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling, Quasi-Monte Carlo methods for two-stage stochastic mixed-integer programs, Optimal insurance contract specification in the upstream sector of the oil and gas industry, Risk and resilience-based optimal post-disruption restoration for critical infrastructures under uncertainty, Spare parts inventory routing problem with transshipment and substitutions under stochastic demands, Variance reduction for sequential sampling in stochastic programming, Multi-echelon supply chains with lead times and uncertain demands. A lot-sizing formulation and solutions, A study on the optimal inventory allocation for clinical trial supply chains, A two-stage stochastic integer programming approach as a mixture of branch-and-fix coordination and Benders decomposition schemes, A stochastic programming approach for supply chain network design under uncertainty, Performance of derivative free search ANN training algorithm with time series and classification problems, Solving the vehicle routing problem with stochastic demands using the cross-entropy method, Event tree based sampling, Multiplier stabilization applied to two-stage stochastic programs, Component rationing for available-to-promise scheduling in configure-to-order systems, Some large deviations results for Latin hypercube sampling, Solving a class of stochastic mixed-integer programs with branch and price, Assessing solution quality in stochastic programs, A general framework on the simulation-based optimization under fixed computing budget, Multistage stochastic programming approach for joint optimization of job scheduling and material ordering under endogenous uncertainties, A distributionally robust optimization approach for stochastic elective surgery scheduling with limited intensive care unit capacity, The empirical behavior of sampling methods for stochastic programming, Warehousing platform's revenue management: a dynamic model of coordinating space allocation for self-use and rent, Applications of stochastic modeling in air traffic management: methods, challenges and opportunities for solving air traffic problems under uncertainty, Distributionally robust facility location problem under decision-dependent stochastic demand, Underground mine scheduling under uncertainty, Accelerated sample average approximation method for two-stage stochastic programming with binary first-stage variables, The Data-Driven Newsvendor Problem: New Bounds and Insights, A new convergent hybrid learning algorithm for two-stage stochastic programs, Robust university course timetabling problem subject to single and multiple disruptions, Time-consistent risk-constrained dynamic portfolio optimization with transactional costs and time-dependent returns, Decision dependent stochastic processes, Community-based rumor blocking maximization in social networks, Design of a reliable logistics network with hub disruption under uncertainty, Penalty variable sample size method for solving optimization problems with equality constraints in a form of mathematical expectation, On inventory allocation for periodic review assemble-to-order systems, Stochastic structured tensors to stochastic complementarity problems, Stochastic sampling for deterministic structural topology optimization with many load cases: density-based and ground structure approaches, Integrating location and network restoration decisions in relief networks under uncertainty, Analysis of models for the stochastic outpatient procedure scheduling problem, On Monte-Carlo methods in convex stochastic optimization, Order assignment and scheduling under processing and distribution time uncertainty, Asymptotic behaviors of semidefinite programming with a covariance perturbation, Appointment scheduling for multi-stage sequential service systems with stochastic service durations, Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming, On sample average approximation for two-stage stochastic programs without relatively complete recourse, Generalized adaptive partition-based method for two-stage stochastic linear programs with fixed recourse, Adaptive sampling line search for local stochastic optimization with integer variables, A study of data-driven distributionally robust optimization with incomplete joint data under finite support, On complexity of multistage stochastic programs, Stochastic radiotherapy appointment scheduling, Resource distribution under spatiotemporal uncertainty of disease spread: stochastic versus robust approaches, Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested L-shaped method, Appraising the convenience of a call-based dynamical hedging strategy for an oil-company, Simultaneous location and vehicle fleet sizing of relief goods distribution centers and vehicle routing for post-disaster logistics, Robust optimization for spread quality and shortfall in guaranteed targeted display advertising planning, Exact reliability optimization for series‐parallel graphs using convex envelopes, Network revenue management game in the railway industry: Stackelberg equilibrium, global optimality, and mechanism design, From scenarios to conditional scenarios in two‐stage stochastic MILP problems, A guarantee rate optimization model for wastewater treatment system design under uncertainty, Evaluating appointment postponement in scheduling patients at a diagnostic clinic, Estimating the marginal cost to deliver to individual customers, Using Lagrangian relaxation to locate hydrogen production facilities under uncertain demand: a case study from Norway, Problem-driven scenario clustering in stochastic optimization, A survey on bilevel optimization under uncertainty, Non-parametric generalised newsvendor model, Stochastic optimization models for a home service routing and appointment scheduling problem with random travel and service times, Approximation schemes for districting problems with probabilistic constraints, Joint tank container demurrage policy and flow optimisation using a progressive hedging algorithm with expanded time-space network, Single machine scheduling with release dates: a distributionally robust approach, Integrated strategic energy mix and energy generation planning with multiple sustainability criteria and hierarchical stakeholders, Cardinality-constrained distributionally robust portfolio optimization, Day-ahead aircraft routing with data-driven primary delay predictions, Conditional scenario-based model predictive control, Sample average approximation for risk-averse problems: a virtual power plant scheduling application, A hybrid genetic algorithm for scheduling jobs sharing multiple resources under uncertainty, Efficient presolving methods for the influence maximization problem, A stochastic optimization approach for staff scheduling decisions at inpatient units, Winner determination with sustainable-flexible considerations under demand uncertainty in transportation service procurement auctions, Solving linear Bayesian inverse problems using a fractional total variation-Gaussian (FTG) prior and transport map, Distribution-free algorithms for predictive stochastic programming in the presence of streaming data, A limited-memory BFGS-based differential evolution algorithm for optimal control of nonlinear systems with mixed control variables and probability constraints, An accelerated benders decomposition algorithm for stochastic power system expansion planning using sample average approximation, Hesitant adaptive search with estimation and quantile adaptive search for global optimization with noise, Solving multistage stochastic linear programming via regularized linear decision rules: an application to hydrothermal dispatch planning, A robust multi-objective Bayesian optimization framework considering input uncertainty, Two-stage stochastic nonlinear winner determination for logistics service procurement auctions under quantity discounts, An alternative approach to address uncertainty in hub location, Optimal control of nonlinear systems with integer‐valued control inputs and stochastic constraints, Finding groups with maximum betweenness centrality via integer programming with random path sampling, Reliable Error Estimates for Optimal Control of Linear Elliptic PDEs with Random Inputs, Sample Size Estimates for Risk-Neutral Semilinear PDE-Constrained Optimization
