Fully Polynomial Time Approximation Schemes for Robust Multistage Decision Making

Nir Halman () and Giacomo Nannicini ()
Additional contact information
Nir Halman: Faculty of Engineering, Bar-Ilan University, Ramat Gan 5290002, Israel
Giacomo Nannicini: Department of Industrial & Systems Engineering, University of Southern California, Los Angeles, California 90089

INFORMS Journal on Computing, 2025, vol. 37, issue 5, 1306-1327

Abstract: We design a framework to obtain Fully Polynomial Time Approximation Schemes (FPTASes) for adjustable robust multistage decision making under the budgeted uncertainty sets introduced by Bertsimas and Sim. We apply this framework to the robust counterpart of three problems coming from operations research: (i) ordered knapsack, (ii) single-item inventory control, and (iii) single-item batch dispatch. Our work gives the first FPTAS for these problems, and for adjustable robust multistage decision making in general. The proposed approximation schemes are constructed with the technique of K -approximation sets and functions, relying on careful robust dynamic programming formulations for a master problem (corresponding to the decision maker) and for an adversary problem (corresponding to nature, which chooses bad realizations of uncertainty for the decision maker). The resulting algorithms are short and simple, requiring just a few concise subroutines.

Keywords: robust optimization; adjustable robust optimization; dynamic programming; robust dynamic programming; inventory control; knapsack problem; FPTAS; K -approximation sets and functions (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0126 (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:orijoc:v:37:y:2025:i:5:p:1306-1327

Access Statistics for this article

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