A finite branch-and-bound algorithm for two-stage stochastic integer programs

This paper addresses a general class of two-stage stochastic programs with integer recourse and discrete distributions. We exploit the structure of the value function of the second-stage integer problem to develop a novel global optimization algorithm. The proposed scheme departs from those in the c...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2004-06, Vol.100 (2), p.355-377
Main Authors: AHMED, Shabbir, TAWARMALANI, Mohit, SAHINIDIS, Nikolaos V
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Decomposition
Exact sciences and technology
Expected values
Integer programming
Linear programming
Mathematical programming
Operational research and scientific management
Operational research. Management science
Optimization
Random variables
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper addresses a general class of two-stage stochastic programs with integer recourse and discrete distributions. We exploit the structure of the value function of the second-stage integer problem to develop a novel global optimization algorithm. The proposed scheme departs from those in the current literature in that it avoids explicit enumeration of the search space while guaranteeing finite termination. Computational experiments on standard test problems indicate superior performance of the proposed algorithm in comparison to those in the existing literature.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-003-0475-6