Disjunctive Decomposition for Two-Stage Stochastic Mixed-Binary Programs with Random Recourse

Lewis Ntaimo(ntaimotamu.edu)

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 motivated by real-life stochastic server location problems with random recourse, which find many applications in operations research. Computational results with large-scale instances to demonstrate the potential of the method are reported.

Keywords: Set convexification, cutting plane, random recourse, disjunctive decomposition, stochastic programming

Category 1: Stochastic Programming

Category 2: Integer Programming (Cutting Plane Approaches )

Citation:

Download: [PDF]

Entry Submitted: 02/22/2008
Entry Accepted: 02/22/2008
Entry Last Modified: 02/22/2008

Modify/Update this entry