A binary decision diagram based algorithm for solving a class of binary two-stage stochastic programs

• 成果类型: Article
• 署名作者: Lozano, Leonardo; Smith, J. Cole
• 署名单位: Clemson University; Clemson University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1315-z
• 发表日期: 2022
• 页码: 381-404
• 关键词: traveling salesman problem; integer recourse; time windows; branch; DECOMPOSITION; models; FRAMEWORK

摘要

We consider a special class of two-stage stochastic integer programming problems with binary variables appearing in both stages. The class of problems we consider constrains the second-stage variables to belong to the intersection of sets corresponding to first-stage binary variables that equal one. Our approach seeks to uncover strong dual formulations to the second-stage problems by transforming them into dynamic programming (DP) problems parameterized by first-stage variables. We demonstrate how these DPs can be formed by use of binary decision diagrams, which then yield traditional Benders inequalities that can be strengthened based on observations regarding the structure of the underlying DPs. We demonstrate the efficacy of our approach on a set of stochastic traveling salesman problems.