Two-stage stochastic hierarchical multiple risk problems: models and algorithms

In this paper, we consider a class of two-stage stochastic risk management problems, which may be stated as follows. A decision-maker determines a set of binary first-stage decisions, after which a random event from a finite set of possible outcomes is realized. Depending on the realization of this outcome, a set of continuous second-stage decisions must then be made that attempt to minimize some risk function. We consider a hierarchy of multiple risk levels along with associated penalties for each possible scenario. The overall objective function thus depends on the cost of the first-stage decisions, plus the expected second-stage risk penalties. We develop a mixed-integer 0–1 programming model and adopt an automatic convexification procedure using the reformulation–linearization technique to recast the problem into a form that is amenable to applying Benders’ partitioning approach. As a principal computational expedient, we show how the reformulated higher-dimensional Benders’ subproblems can be efficiently solved via certain reduced-sized linear programs in the original variable space. In addition, we explore several key ingredients in our proposed procedure to enhance the tightness of the prescribed Benders’ cuts and the efficiency with which they are generated. Finally, we demonstrate the computational efficacy of our approaches on a set of realistic test problems. Dr. H. D. Sherali acknowledges the support of the National Science Foundation under Grant No. DMI-0552676. Dr. J. C. Smith acknowledges the support of the Air Force Office of Scientific Research under Grant No. AFOSR/MURI F49620-03-1-0477.