We consider a chance-constrained optimization problem (CCOP), where the random variables follow finite discrete distributions. The problem is in general nonconvex and can be reformulated as a mixed-integer program. By exploiting the special structure of the probabilistic constraint, we propose an alternating direction method for finding suboptimal solutions of CCOP. At each iteration, this method solves a convex programming subproblem and a 0-1 knapsack subproblem, which can be computed in quasi-linear time in the case of equal probabilities. We establish the convergence of the method to a first-order stationary point under certain mild conditions. Preliminary computational results are reported for VaR-constrained portfolio selection problems and chance-constrained transportation problems. Numerical results show that the proposed method is promising for finding solutions of good quality and compares favorably with CPLEX and other existing approximation methods, especially for large-size problems.
View An Alternating Direction Method for Chance-Constrained Optimization Problems with Discrete Distributions