Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse

Z. L. Chen; Warren Buckler Powell

doi:10.1023/A:1022641805263

Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse

Z. L. Chen, Warren Buckler Powell

Research output: Contribution to journal › Article › peer-review

72 Scopus citations

Abstract

We propose an algorithm for multistage stochastic linear programs with recourse where random quantities in different stages are independent. The algorithm approximates successively expected recourse functions by building up valid cutting planes to support these functions from below. In each iteration, for the expected recourse function in each stage, one cutting plane is generated using the dual extreme points of the next-stage problem that have been found so far. We prove that the algorithm is convergent with probability one.

Original language	English (US)
Pages (from-to)	497-524
Number of pages	28
Journal	Journal of Optimization Theory and Applications
Volume	102
Issue number	3
DOIs	https://doi.org/10.1023/A:1022641805263
State	Published - Sep 1999

All Science Journal Classification (ASJC) codes

Control and Optimization
Applied Mathematics
Management Science and Operations Research

Keywords

Convergence with probability one
Cutting planes
Multistage stochastic programming
Sampling

Access to Document

10.1023/A:1022641805263

Cite this

@article{0648ad8a59324a868ec15501c3fa6475,

title = "Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse",

abstract = "We propose an algorithm for multistage stochastic linear programs with recourse where random quantities in different stages are independent. The algorithm approximates successively expected recourse functions by building up valid cutting planes to support these functions from below. In each iteration, for the expected recourse function in each stage, one cutting plane is generated using the dual extreme points of the next-stage problem that have been found so far. We prove that the algorithm is convergent with probability one.",

keywords = "Convergence with probability one, Cutting planes, Multistage stochastic programming, Sampling",

author = "Chen, {Z. L.} and Powell, {Warren Buckler}",

note = "Funding Information: 1This work was supported in part by Grant AFOSR-F49620-93-1-0098 from the Air Force Office of Scientific Research. 2Assistant Professor, Department of Systems Engineering, University of Pennsylvania, Philadelphia, Pennsylvania. 3Professor, Department of Civil Engineering and Operations Research, Princeton University, Princeton, New Jersey.",

year = "1999",

month = sep,

doi = "10.1023/A:1022641805263",

language = "English (US)",

volume = "102",

pages = "497--524",

journal = "Journal of Optimization Theory and Applications",

issn = "0022-3239",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse

AU - Chen, Z. L.

AU - Powell, Warren Buckler

N1 - Funding Information: 1This work was supported in part by Grant AFOSR-F49620-93-1-0098 from the Air Force Office of Scientific Research. 2Assistant Professor, Department of Systems Engineering, University of Pennsylvania, Philadelphia, Pennsylvania. 3Professor, Department of Civil Engineering and Operations Research, Princeton University, Princeton, New Jersey.

PY - 1999/9

Y1 - 1999/9

N2 - We propose an algorithm for multistage stochastic linear programs with recourse where random quantities in different stages are independent. The algorithm approximates successively expected recourse functions by building up valid cutting planes to support these functions from below. In each iteration, for the expected recourse function in each stage, one cutting plane is generated using the dual extreme points of the next-stage problem that have been found so far. We prove that the algorithm is convergent with probability one.

AB - We propose an algorithm for multistage stochastic linear programs with recourse where random quantities in different stages are independent. The algorithm approximates successively expected recourse functions by building up valid cutting planes to support these functions from below. In each iteration, for the expected recourse function in each stage, one cutting plane is generated using the dual extreme points of the next-stage problem that have been found so far. We prove that the algorithm is convergent with probability one.

KW - Convergence with probability one

KW - Cutting planes

KW - Multistage stochastic programming

KW - Sampling

UR - http://www.scopus.com/inward/record.url?scp=0033245908&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033245908&partnerID=8YFLogxK

U2 - 10.1023/A:1022641805263

DO - 10.1023/A:1022641805263

M3 - Article

AN - SCOPUS:0033245908

SN - 0022-3239

VL - 102

SP - 497

EP - 524

JO - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

IS - 3

ER -

Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this