Optimization Online


A Branch-and-Cut Decomposition Algorithm for Solving Chance-Constrained Mathematical Programs with Finite Support

James Luedtke (jrluedt1***at***wisc.edu)

Abstract: We present a new approach for exactly solving chance-constrained mathematical programs having discrete distributions with nite support and random polyhedral constraints. Such problems have been notoriously difficult to solve due to nonconvexity of the feasible region, and most available methods are only able to nd provably good solutions in certain very special cases. Our approach uses both decomposition, to enable processing subproblems corresponding to one possible outcome at a time, and integer programming techniques, to combine the results of these subproblems to yield strong valid inequalities. Computational results on a chance-constrained formulation of a resource planning problem inspired by a call center stang application indicate the approach works signi cantly better than both an existing mixed integer programming formulation and a simple decomposition approach that does not use strong valid inequalities. We also demonstrate how the approach can be used to efficiently solve for a sequence of risk levels, as would be done when solving for the ecient frontier of risk and cost.

Keywords: Stochastic programming, integer programming, chance constraints, probabilistic constraints, decomposition

Category 1: Stochastic Programming

Citation: Mathematical Programming (2013). DOI 10.1007/s10107-013-0684-6. Available at link.springer.com


Entry Submitted: 05/14/2011
Entry Accepted: 05/14/2011
Entry Last Modified: 05/22/2013

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