We present a general metaheuristic for joint chance-constrained stochastic programs with discretely distributed parameters. We give a reformulation of the problem that allows us to define a finite solution space. We then formulate a novel neighborhood for the problem and give methods for efficiently searching this neighborhood for solutions that are likely to be improving. We formulate a reduced linear program that is all that needs to be solved each iteration of the algorithm, reducing the computational effort required for the search. Finally, we give a random tabu search heuristic to search our solution space. The algorithm differs from other work on joint chance-constrained problems in that it is valid for problems with randomness both in the constraint matrix and in the righthand side. We finish with computational experiments on two sets of test instances that show that our algorithm is highly effective at finding good feasible solutions to these problems.
Department of Industrial and Systems Engineering Texas A&M University, Submitted to Computational Optimization and Applications