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

Leonardo Lozano, J. Cole Smith

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
JournalMathematical Programming
DOIs
StateAccepted/In press - Jan 1 2018
Externally publishedYes

Keywords

  • Benders’ decomposition
  • Binary decision diagrams
  • Integer programming
  • Two-stage stochastic programming

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A binary decision diagram based algorithm for solving a class of binary two-stage stochastic programs'. Together they form a unique fingerprint.

  • Cite this