An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions

Hao Hsiang Wu, Simge Küçükyavuz*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

We consider a class of risk-averse submodular maximization problems (RASM) where the objective is the conditional value-at-risk (CVaR) of a random nondecreasing submodular function at a given risk level. We propose valid inequalities and an exact general method for solving RASM under the assumption that we have an efficient oracle that computes the CVaR of the random function. We demonstrate the proposed method on a stochastic set covering problem that admits an efficient CVaR oracle for the random coverage function.

Original languageEnglish (US)
Pages (from-to)356-361
Number of pages6
JournalOperations Research Letters
Volume48
Issue number3
DOIs
StatePublished - May 2020

Keywords

  • Conditional value-at-risk
  • Lifting
  • Oracle
  • Stochastic programming
  • Stochastic set covering
  • Submodular maximization

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions'. Together they form a unique fingerprint.

Cite this