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 journalArticlepeer-review

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)
Pages (from-to)381-404
Number of pages24
JournalMathematical Programming
Volume191
Issue number1
DOIs
StatePublished - Jan 2022
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