License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-638
URL: http://drops.dagstuhl.de/opus/volltexte/2005/63/

Morton, David P. ; Bayraksan, Guzin

Assessing Solution Quality in Stochastic Programs

pdf-format:
Dokument 1.pdf (172 KB)


Abstract

Assessing whether a solution is of high quality (optimal or near optimal) is a fundamental question in optimization. We develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure and then present a result that justifies a computationally simplified single-replication procedure. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval may have low coverage for small sample sizes on some problems. We provide variants of this procedure and provide preliminary guidelines for selecting a candidate solution. Both are designed to improve the basic procedure's performance.

BibTeX - Entry

@InProceedings{morton_et_al:DSP:2005:63,
  author =	{David P. Morton and Guzin Bayraksan},
  title =	{Assessing Solution Quality in Stochastic Programs},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  year =	{2005},
  editor =	{Susanne Albers and Rolf H. M{\"o}hring and Georg Ch. Pflug and R{\"u}diger Schultz},
  number =	{05031},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2005/63},
  annote =	{Keywords: stochastic programming , Monte Carlo simulation}
}

Keywords: stochastic programming , Monte Carlo simulation
Seminar: 05031 - Algorithms for Optimization with Incomplete Information
Issue date: 2005
Date of publication: 30.05.2005


DROPS-Home | Fulltext Search | Imprint Published by LZI