Leveraging decision diagrams to solve two-stage stochastic programs with binary recourse and logical linking constraints

Moira MacNeil and Merve Bodur

European Journal of Operational Research, 2024, vol. 315, issue 1, 228-241

Abstract: We generalize an existing binary decision diagram-based (BDD-based) approach of Lozano and Smith (MP, 2022) to solve a special class of two-stage stochastic programs (2SPs) with binary recourse, where the first-stage decisions impact the second-stage constraints. First, we extend the second-stage problem to a more general setting where logical expressions of the first-stage solutions enforce constraints in the second stage. Then, as our primary contribution, we introduce a complementary problem, that appears more naturally for many of the same applications of the former approach, and a distinct BDD-based solution method, that is more efficient than the existing BDD-based approach on commonly applicable problem classes. In the novel problem, second-stage costs, rather than constraints, are impacted by expressions of the first-stage decisions. In both settings, we convexify the second-stage problems using BDDs and parameterize either the BDD arc costs or capacities with first-stage solutions. We extend this work by incorporating conditional value-at-risk and propose the first decomposition method for 2SP with binary recourse and a risk measure. We apply these methods to a novel stochastic problem, namely stochastic minimum dominating set problem, and present numerical results to support their effectiveness.

Keywords: Stochastic programming; Binary decision diagrams; Benders decomposition (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723009542
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:315:y:2024:i:1:p:228-241

DOI: 10.1016/j.ejor.2023.12.021

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().