Complexity of Bilevel Coherent Risk Programming

This paper considers a bilevel programming approach to applying coherent risk measures to extended two-stage stochastic programming problems. This formulation technique avoids the time-inconsistency issues plaguing naive models and the incomposability issues which cause time-consistent formulations to have complicated, hard-to-explain objective functions. Unfortunately, the analysis here shows that such bilevel formulations, when using the standard mean-semideviation and average-value-at-risk measures, are NP-hard. While not necessarily indicating that solution of such models is impractical, these results suggest that it may prove dicult and will likely require some kind of implicit enumeration method.


RUTCOR Research Report 17-2012, Rutgers University, April 2012



View Complexity of Bilevel Coherent Risk Programming