Adaptive Scenario Partitioning for Stochastic Bilevel Linear Programs

This paper develops an adaptive scenario partitioning approach for stochastic bilevel linear programs. The method extends the Adaptive Partitioning Method, originally designed for two-stage stochastic programs, to settings in which a leader makes a first-stage decision while anticipating scenario dependent optimal responses from a follower. The proposed approach solves a sequence of aggregated master problems and refines scenario groups using information from the follower’s optimal bases and primal–dual signatures. We also study computational variants based on basis-aware refinement, scenario bundling, and non-trivial initial partitions obtained from K-means clustering and central initialization. The approach is evaluated on stochastic continuous bilevel knapsack instances with up to 3,200 scenarios and compared with an extended reference formulation. The results show that basis aware refinement and informative initial partitions substantially reduce solution times while keeping objective gaps small relative to the reference model. These findings indicate that adaptive partitioning is a promising computational strategy for large-scale stochastic bilevel optimization.

Article

Download

View PDF