Stochastic Mixed-Integer Programming — Optimization Under Uncertainty with Discrete and Continuous Decisions
Stochastic Mixed-Integer Programming (SMIP) · Also known as: SMIP, Stochastic MIP, Mixed-Integer Stochastic Programming, SMILP
Stochastic Mixed-Integer Programming (SMIP) is an optimization framework that finds the best mix of binary, integer, and continuous decisions when key parameters — costs, demands, capacities — are uncertain and modeled as probability distributions over a set of scenarios. It extends classical MIP by embedding scenario trees or expected-value objectives that hedge against uncertainty while respecting combinatorial constraints.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use SMIP when decisions involve discrete or binary choices (invest/not invest, number of units to open) and key input parameters are genuinely uncertain with quantifiable probability distributions. Ideal for supply chain network design under demand uncertainty, energy capacity expansion, healthcare facility planning, and disaster response pre-positioning. Do not use when all decisions are continuous (use stochastic LP instead), when uncertainty cannot be meaningfully quantified as distributions, when the number of scenarios required to represent uncertainty leads to intractable model sizes and decomposition is unavailable, or when a simulation-based heuristic suffices for the decision quality required.
Strengths & limitations
- Handles combinatorial discrete decisions under uncertainty in a single coherent optimization model.
- Produces hedged first-stage plans that balance expected performance across all scenarios.
- VSS and EVPI metrics provide transparent justification for the value of stochastic modeling.
- Decomposition algorithms (L-shaped, progressive hedging) scale to large scenario sets.
- Widely supported in commercial solvers (CPLEX, Gurobi) and modeling languages (AMPL, Pyomo).
- Computational complexity grows combinatorially with number of scenarios and integer variables; large instances may be intractable without effective decomposition.
- Requires explicit probability distributions or scenario sets — misspecified uncertainty models lead to solutions that perform poorly out-of-sample.
- Two-stage formulations may oversimplify multi-period decisions; multi-stage SMIP is significantly harder.
- Integer second-stage recourse destroys the convexity exploited by standard Benders cuts, requiring specialized integer L-shaped cuts.
Frequently asked
How is SMIP different from regular Mixed-Integer Programming?
Regular MIP optimizes under fixed, known parameters. SMIP explicitly models uncertain parameters as a set of scenarios with probabilities, optimizing expected performance across all scenarios while ensuring first-stage decisions are made before uncertainty is revealed.
How many scenarios do I need?
There is no universal rule. As few as 10–50 scenarios may suffice for stable first-stage decisions in some problems; others require thousands. Scenario reduction techniques and stability tests (checking that the optimal solution does not change as you add more scenarios) help determine adequacy.
What is the L-shaped method?
The L-shaped method is a Benders decomposition adapted for stochastic programs. It iteratively solves a master MIP over first-stage variables and scenario subproblems, adding optimality and feasibility cuts to the master until convergence. For integer recourse, integer L-shaped cuts replace standard Benders cuts.
When should I use progressive hedging instead of L-shaped?
Progressive hedging decomposes by scenario rather than by subproblem structure, making it well-suited for parallel computing. It is preferred when scenarios are many and subproblems are large, and when the algorithm can be run on a cluster. L-shaped is generally preferred for fewer, well-structured scenarios.
Can SMIP handle more than two stages?
Yes, but multi-stage SMIP requires a scenario tree that grows exponentially in the number of stages, and decomposition becomes substantially more complex. In practice, most applied SMIP models use two stages, approximating multi-period dynamics via rolling horizon or aggregation.
Sources
- Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer. ISBN: 9780387982175
- Sen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20. DOI: 10.1007/s10107-004-0566-z ↗
How to cite this page
ScholarGate. (2026, June 3). Stochastic Mixed-Integer Programming (SMIP). ScholarGate. https://scholargate.app/en/simulation/stochastic-mixed-integer-programming
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Mixed-Integer ProgrammingSimulation↔ compare
- MONTE-CARLO-SIMULATIONDecision-making↔ compare
- Stochastic Dynamic ProgrammingSimulation↔ compare
- Stochastic Linear ProgrammingSimulation↔ compare
- Stochastic Multi-Objective OptimizationSimulation↔ compare