- | ||||
|
![]()
|
An Efficient Decomposition Algorithm for Static, Stochastic, Linear and Mixed-Integer Linear Programs with Conditional-Value-at-Risk Constraints
Dharmashankar Subramanian(dharmash 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 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |