Disjunctive decomposition for two-stage stochastic mixed-binary programs with random recourse

Abstract

This paper introduces disjunctive decomposition for two-stage mixed 0-1 stochastic integer programs (SIPs) with random recourse. Disjunctive decomposition allows for cutting planes based on disjunctive programming to be generated for each scenario subproblem under a temporal decomposition setting of the SIP problem.A new class of valid inequalities for mixed 0-1 SIP with random recourse is presented. In particular, valid inequalities that allow for sharing cut coefficients among scenario subproblems for SIP with random recourse but deterministic technology matrix and righthand side vector are obtained. The valid inequalities are used to derive a disjunctive decomposition method whose derivation has been motivatedby real-life stochastic server location problems with random recourse, which find many applications in operations research. Computational results with large-scaleinstances to demonstrate the potential of the method are reported.