Stronger cuts for Benders’ decomposition for stochastic Unit Commitment Problems based on interval variables
Published in Accepted/in press in Mathematical Programming Computation., 2026
The Stochastic Unit Commitment (SUC) problem addresses the scheduling of power generation units under uncertainty, typically using a two-stage stochastic program with integer first-stage and continuous second-stage variables. We present a novel Benders decomposition strategy employing an extended formulation with interval variables that enables decomposition across both units and time intervals. This approach yields provably stronger Benders cuts than those derived from the standard 3-bin representation.
To enhance computational performance, we introduce a heuristic leveraging weak duality to expeditiously approximate cut coefficients for units with ramping and capacity constraints. Computational testing on large-scale instances — including the IEEE 118-bus system and SMS++ benchmarks — demonstrates superior performance, achieving up to five times faster results than competing approaches on difficult cases and solving previously intractable instances.
Recommended citation:
Download Paper