Optimization Online


Complexity of Bilevel Coherent Risk Programming

Jonathan Eckstein(jeckstei***at***rci.rutgers.edu)

Abstract: 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.

Keywords: Stochastic programming, bilevel programming, computational complexity

Category 1: Stochastic Programming

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

Download: [PDF]

Entry Submitted: 04/10/2012
Entry Accepted: 04/10/2012
Entry Last Modified: 04/10/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society