Stage- and scenario-wise Fenchel decomposition for stochastic mixed 0-1 programs with special structure

摘要

Solving stochastic integer programs (SIN) is generally difficult. This paper considers a comparative study of stage- and scenario-wise Fenchel decomposition (FD) for two-stage SIPs with special structure. The standard FD approach is based on stage-wise or Benders' decomposition. This work derives a scenario FD method based on decomposing the SIP problem by scenario and performs a computational study of the two approaches. In particular, two algorithms are studied, stage-wise FD (ST-FD) and scenario-wise FD (SC-FD) algorithms. The algorithms use FD cuts generated based on the scenario subproblem under each decomposition setting to iteratively recover (partially) the convex hull of integer points in the neighborhood of the optimal solution. The L-shaped method is used to solve the LP relaxation of the SIP problem in the ST-FD algorithm, while the progressive hedging algorithm (PHA) is used in the SC-FD algorithm. Computational results on knapsack test instances demonstrate the viability of both approaches towards solving large instances in reasonable amount of time and outperforming a direct solver in most cases. Overall, the ST-FD algorithm provides the best performance in our experiments. (C) 2015 Elsevier Ltd. All rights reserved.