A deep reinforcement learning framework for solving two-stage stochastic programs

Dogacan Yilmaz, I. Esra Büyüktahtakın

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

In this study, we present a deep reinforcement learning framework for solving scenario-based two-stage stochastic programming problems. Stochastic programs have numerous real-time applications, such as scheduling, disaster management, and route planning, yet they are computationally challenging to solve and require specially designed solution strategies such as hand-crafted heuristics. To the extent of our knowledge, this is the first study that decomposes two-stage stochastic programs with a multi-agent structure in a deep reinforcement learning algorithmic framework to solve them faster. Specifically, we propose a general two-stage deep reinforcement learning framework that can generate high-quality solutions within a fraction of a second, in which two different learning agents sequentially learn to solve each stage of the problem. The first-stage agent is trained with the feedback of the second-stage agent using a new policy gradient formulation since the decisions are interconnected through the stages. We demonstrate our framework through a general multi-dimensional stochastic knapsack problem. The results show that solution time can be reduced up to five orders of magnitude with sufficiently good optimality gaps of around 7%. Also, a decision-making agent can be trained with a few scenarios and can solve problems with many scenarios and achieve a significant reduction in solution times. Considering the vast state and action space of the problem of interest, the results show a promising direction for generating fast solutions for stochastic online optimization problems without expert knowledge.

Original languageEnglish (US)
JournalOptimization Letters
DOIs
StateAccepted/In press - 2023
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Business, Management and Accounting (miscellaneous)
  • Control and Optimization

Keywords

  • Deep learning
  • Discrete optimization
  • Online optimization
  • Real-time problems
  • Reinforcement learning
  • Two-stage stochastic programming

Fingerprint

Dive into the research topics of 'A deep reinforcement learning framework for solving two-stage stochastic programs'. Together they form a unique fingerprint.

Cite this