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

• 成果类型: Article
• 署名作者: Ntaimo, Lewis
• 署名单位: Texas A&M University System; Texas A&M University College Station
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1090.0693
• 发表日期: 2010
• 页码: 229-243
• 关键词: lift-and-project; algorithms

摘要

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, we derive valid inequalities that allow for scenario subproblems for SIP with random recourse but deterministic technology matrix and right-hand side vector to share cut coefficients. 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.