B&B Solution Technique for Multicriteria Stochastic Optimization Problems

The paper extends stochastic branch and bound (SB&B) method, primarily developed for solving stochastic global and integer stochastic programming problems, to stochastic multicriteria problems. The specific feature and difficulty of the stochastic optimization problems consists in that they contain random parameters and thus mathematical expectations and other probabilistic integral operators. The scalar stochastic branch and bound method has found various applications for optimization of stochastic workflow models, stochastic schedules, project management, water quality, pollution control, service allocation, reliability optimization, financial portfolio selection, and others. Multicriteria versions of such problems allow more explicit investigation of a trade-off between utility, risk, and other criteria in the problem. In the new SB&B method, upper and lower bounds become vectorial. For example, for a maximization problem, as an upper bound, the value of the vector objective function at the ideal point can be used; as a lower bound, the value of the vector objective function at any feasible point is usually taken. For stochastic optimization problems, such bounds can be calculated exactly only in special cases, for example, when the distribution of random parameters is known and discrete. In the latter case, the estimation problems are reduced to mixed-integer programming. In a general case to get upper bounds, the so-called interchange relaxation is applied, i.e., interchange of optimization and integration operators. Another bounding technique involves the use of multiple independent observations of random parameters and stochastic tangent majorants. Since the bounds are vectorial and may be inexact, the convergence results state finite step convergence to a set of approximate solutions.