Show simple item record

2005-02-25Buch DOI: 10.18452/8333
Assessing Solution Quality in Stochastic Programs
dc.contributor.authorBayraksan, Güzin
dc.contributor.authorMorton, David P.
dc.contributor.editorHigle, Julie L.
dc.contributor.editorRömisch, Werner
dc.contributor.editorSen, Surrajeet
dc.date.accessioned2017-06-16T20:03:10Z
dc.date.available2017-06-16T20:03:10Z
dc.date.created2005-09-08
dc.date.issued2005-02-25
dc.date.submitted2005-01-27
dc.identifier.urihttp://edoc.hu-berlin.de/18452/8985
dc.description.abstractDetermining whether a solution is of high quality (optimal or near optimal) is a fundamental question in optimization theory and algorithms. In this paper, 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 that requires solution of, say, 30 optimization problems and then, we present a result that justifies a computationally simplified single-replication procedure that only requires solving one optimization problem. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval might have low coverage probability for small sample sizes for some problems. We provide variants of this procedure that require two replications instead of one and that perform better empirically. We present computational results for a newsvendor problem and for two-stage stochastic linear programs from the literature. We also discuss when the procedures perform well an when they fail and provide preliminary guidelines for selecting a candidate solution.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Mathematik
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subject.ddc510 Mathematik
dc.titleAssessing Solution Quality in Stochastic Programs
dc.typebook
dc.identifier.urnurn:nbn:de:kobv:11-10046379
dc.identifier.doihttp://dx.doi.org/10.18452/8333
local.edoc.pages22
local.edoc.type-nameBuch
local.edoc.container-typeseries
local.edoc.container-type-nameSchriftenreihe
local.edoc.container-year2005
dc.identifier.zdb2936317-2
bua.series.nameStochastic Programming E-Print Series
bua.series.issuenumber2005,4

Show simple item record