Linear programs with joint probabilistic constraints (PCLP) are known to be highly intractable due to the non-convexity of the feasible region. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We present a mixed integer programming formulation and study the relaxation corresponding to a single row of the probabilistic constraint, yielding two strengthened formulations. As a byproduct of this analysis, we obtain new results for the previously studied mixing set, subject to an additional knapsack inequality. We present computational results that indicate that by using our strengthened formulations, large scale instances can be solved to optimality.
展开▼