An Efficient Decomposition Algorithm for Static, Stochastic, Linear and Mixed-Integer Linear Programs with Conditional-Value-at-Risk Constraints

Dharmashankar Subramanian(dharmashus.ibm.com)
Pu Huang(puhuangus.ibm.com)

Abstract: We present an efficient decomposition algorithm for single-stage, stochastic linear programs, where conditional value at risk (CVaR) appears as a risk measure in multiple constraints. It starts with a well-known nonlinear, convex reformulation of conditional value at risk constraints, and establishes the connection to a combinatorially large polyhedral representation of the convex feasible set induced by the above reformulation. The algorithm is developed as a column-generation procedure in the dual space of the resulting polyhedral representation. In the special case, where CVaR appears in the objective function alone, it offers an alternative view into CVarMin, a breakthrough algorithm in the literature, which specialized the L-shaped algorithm of two-stage stochastic programs with recourse for CVaR minimization. CVarMin concentrated on CVaR in the objective function, which led naturally to a two-stage interpretation. The optimization problem with multiple CVaR constraints does not have a natural two-stage interpretation, nevertheless we explicitly extend the polyhedral ideas of CVaR minimization and integrated chance constraints to the case of multiple CVaR constraints. We also present an algorithm that engineers the decomposition scheme to address mixed-integer linear programming problems with multiple CVaR constraints.

Keywords: Conditional value at risk; CVaR constraints; CVaR Objective; Column generation; Discrete sampling approximation; Risk-constrained Optimization

Category 1: Robust Optimization

Category 2: Applications -- OR and Management Sciences

Citation: IBM T.J. Watson Research Report, 1101 Kitchawan Rd, Rte 134, Yorktown Heights, NY 10598, Report RC24752, February 2009

Download: [PDF]

Entry Submitted: 01/27/2010
Entry Accepted: 01/27/2010
Entry Last Modified: 01/27/2010

Modify/Update this entry