Lagrangian Dual Decision Rules for Multistage Stochastic Mixed-Integer Programming

Maryam Daryalal (), Merve Bodur () and James R. Luedtke ()
Additional contact information
Maryam Daryalal: Department of Decision Sciences, HEC Montréal, Montréal, Québec H3T 2A7, Canada
Merve Bodur: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
James R. Luedtke: Department of Industrial and Systems Engineering, University of Wisconsin, Madison, Wisconsin 53706

Operations Research, 2024, vol. 72, issue 2, 717-737

Abstract: Multistage stochastic programs can be approximated by restricting policies to follow decision rules. Directly applying this idea to problems with integer decisions is difficult because of the need for decision rules that lead to integral decisions. In this work, we introduce Lagrangian dual decision rules (LDDRs) for multistage stochastic mixed-integer programming (MSMIP), which overcome this difficulty by applying decision rules in a Lagrangian dual of the MSMIP. We propose two new bounding techniques based on stagewise (SW) and nonanticipative (NA) Lagrangian duals, where the Lagrangian multiplier policies are restricted by LDDRs. We demonstrate how the solutions from these duals can be used to drive primal policies. Our proposal requires fewer assumptions than most existing MSMIP methods. We compare the theoretical strength of the restricted duals and show that the restricted NA dual can provide relaxation bounds at least as good as the ones obtained by the restricted SW dual. In our numerical study on two problem classes, one traditional and one novel, we observe that the proposed LDDR approaches yield significant optimality-gap reductions compared with existing general-purpose bounding methods for MSMIP problems.

Keywords: Programming: stochastic; Optimization; multistage stochastic mixed integer programming; decision rules; Lagrangian dual; two-stage approximation; sampling (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2366 (application/pdf)

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:inm:oropre:v:72:y:2024:i:2:p:717-737

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().