Assessing the Quality of Convex Approximations for Two-Stage Totally Unimodular Integer Recourse Models

Ward Romeijnders (), David P. Morton () and Maarten H. van der Vlerk
Additional contact information
Ward Romeijnders: Department of Operations, University of Groningen, 9700 AV, Groningen, Netherlands
David P. Morton: Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208
Maarten H. van der Vlerk: Department of Operations, University of Groningen, 9700 AV, Groningen, Netherlands

INFORMS Journal on Computing, 2017, vol. 29, issue 2, 211-231

Abstract: We consider two types of convex approximations of two-stage totally unimodular integer recourse models. Although worst-case error bounds are available for these approximations, their actual performance has not yet been investigated, mainly because this requires solving the original recourse model. In this paper we assess the quality of the approximating solutions using Monte Carlo sampling, or more specifically, using the so-called multiple replications procedure. Based on numerical experiments for an integer newsvendor problem, a fleet allocation and routing problem, and a stochastic activity network investment problem, we conclude that the error bounds are reasonably sharp if the variability of the random parameters in the model is either small or large; otherwise, the actual error of using the convex approximations is much smaller than the error bounds suggest. Moreover, we conclude that the solutions obtained using the convex approximations are good only if the variability of the random parameters is medium to large. In case this variability is small, however, typically sampling methods perform best, even with modest sample sizes. In this sense, the convex approximations and sampling methods can be considered as complementary solution methods. Moreover, as required for our applications, we extend our approach to derive new error bounds dealing with deterministic second-stage side constraints and relatively complete recourse, and perfect dependencies in the right-hand side vector.

Keywords: stochastic programming; integer recourse; convex approximations; sampling methods (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2016.0725 (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:29:y:2017:i:2:p:211-231

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 ().