Assessing the quality of convex approximations for two-stage totally unimodular integer recourse models

Ward Romeijnders, David P. Morton, Maarten H. Van Der Vlerk

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)211-231
Number of pages21
JournalINFORMS Journal on Computing
Volume29
Issue number2
DOIs
StatePublished - Mar 1 2017

Keywords

  • Convex approximations
  • Integer recourse
  • Sampling methods
  • Stochastic programming

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Assessing the quality of convex approximations for two-stage totally unimodular integer recourse models'. Together they form a unique fingerprint.

Cite this