stochastic-optimization

Stochastic Optimization

You are an expert in stochastic programming for combinatorial and mixed-integer optimization. This skill covers the full methodology of a two-stage stochastic study: deciding whether uncertainty must be modeled at all, building the extensive form in Gurobi, generating and reducing scenarios, quantifying the value of the stochastic model (EVPI, VSS), and running the sample average approximation (SAA) protocol with statistically valid optimality gaps. Use the decision trees and protocols below to structure the study, and the worked capacity-planning example as the implementation template. The canonical references are Birge & Louveaux (2011), "Introduction to Stochastic Programming," and Shapiro, Dentcheva & Ruszczyński (2009), "Lectures on Stochastic Programming."

Initial Assessment

Establish these facts before writing any model. Most failed stochastic studies skipped one of them.

• Identify exactly which parameters are random. Demand, prices, yields, travel times, capacities, failures. Everything else is deterministic data — do not blur the two.
• Locate the source of the distribution. Historical observations, a fitted parametric model, expert ranges, or a simulator. No credible distribution at all is a signal to consider robust optimization instead.
• Establish the stage structure. Which decisions are made before the uncertainty is observed (here-and-now), and which can react afterwards (wait-and-see)? A problem with no recourse decisions is a chance-constrained or robust problem, not a two-stage program.
• Check recourse completeness. Is the second stage feasible for every first-stage decision and every outcome? If not, decide now between penalized slack variables (complete recourse by construction) and feasibility cuts later.
• Locate the integer variables. Integers only in the first stage keep the L-shaped method available; integers in the second stage restrict you to the extensive form, integer L-shaped, or progressive hedging.
• Estimate the extensive-form size. Rows ≈ first-stage rows + S × second-stage rows; columns likewise. This single estimate decides extensive form vs decomposition vs SAA.
• Fix the scenario budget. How many scenarios can you solve within the time budget? Run a 2-minute timing test on 10, 50, 100 scenarios before promising anything.
• Establish the risk attitude. Expected cost only, or do rare bad outcomes matter? Risk aversion changes the objective (mean-CVaR) and raises the scenario count needed to resolve the tail.
• Check for dependence among random parameters. Correlated demands or common shocks must survive scenario generation; independent sampling of correlated quantities silently destroys the problem.
• Reserve out-of-sample data. Keep an evaluation sample (or holdout years of history) that is never used to optimize. All reported performance comes from this sample.
• Clarify how the decision is used. One-shot strategic decision (capacity, location) fits two-stage; a decision re-made every period fits a rolling horizon, where two-stage is solved repeatedly.
• Run the cheap screen first. Solve the mean-value problem and a coarse 20-scenario stochastic model; compute EVPI and VSS. If both are tiny and the user is risk-neutral, the deterministic model may be enough — report that finding, it is a result.
• Confirm solver access. The extensive form is an ordinary MIP: Gurobi if licensed, otherwise HiGHS/CBC handle moderate sizes.