Paper Info
Title
A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support
Abstract
We present a new approach for exactly solving chance-constrained mathematical programs having discrete distributions with finite 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 find 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 staffing application indicate the approach works significantly 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 efficient frontier of risk and cost.
Year
DOI
Venue
2014
10.1007/s10107-013-0684-6
Mathematical Programming: Series A and B
Keywords
Field
DocType
chance constraints,integer programming,probabilistic constraints,90c11,decomposition,90c15,stochastic programming
Resource planning,Mathematical optimization,Staffing,Branch and cut,Algorithm,Efficient frontier,Integer programming,Feasible region,Stochastic programming,Mathematics
Journal
Volume
Issue
ISSN
146
1-2
1436-4646
Citations 
PageRank 
References 
24
0.87
33
Authors
1
Name
Order
Citations
PageRank
James Luedtke143925.95