Deterministic Solutions for a Class of Chance-Constrained Programming Problems

It is desired to select a deterministic decision vector x to maximize a function Z ( x ) subject to one or more independent probability constraints of the form Pr [ y ( x ) ≦ 0] ≧ α, where y ( x ) is a random vector for each given vector x , and α is a given probability. For this purpose we develop a certainty equivalent model without random variables for our chance-constrained model such that feasible and optimal solutions of a chance-constrained problem and of its associated certainty equivalent problem coincide. Problems with any number of single chance-constraints of the form Pr [ y ( x ) ≦ 0] ≧ α, i ϵ I , where the y ı ( x ) are independent single random variables for given vector x , can be solved directly after converting them to the certainty equivalent form. Problems with joint chance-constraints of the form Pr [ y ( x ) ≦ 0] ≧ α, where y ( x ) is a random vector for given vector x , require selection from a set of certainty equivalent values in order to optimize the objective function. For the case of linear chance-constrained problems with joint constraints, and where only the b bector contains random variables, we develop a method for transforming any linear programming problem of the form max cx , Ax = b , x ≧ 0 into a cost unitized linear programming problem of the form max 1 y , AT −1 y = b , y ≧ 0. We then determine how to solve the chance-constrained problem max cx , Pr [ A ( x ) ≦ b ] ≧ α, where b is a random vector.