A Stochastic Branch-and-Bound Method

Title:

Author:

Andrzej Ruszczynski

Coauthor(s):

Vladimir I. Norkin
Georg Ch. Pflug

Session: TH3-G-IN11

Keywords: stochastic integer programming, stochastic global optimization

Abstract:

We present a novel methodology for solving stochastic integer or global optimization problems: a stochastic branch-and-bound method. At each step a certain partition of the feasible set is considered, and for each subset stochastic estimates of lower and upper bounds for the best objective value are calculated. They are used to construct a new partition, for which new estimates are generated, etc. The method is convergent with probability one. We discuss various ways of calculating stochastic bounds, using multiple observations, estimating the accuracy of the solution, and deleting non-prospective subsets. We present also an application of the new methodology to a problem of water quality management.