On Multi-Disjunctive Valid Inequalities for Chance-Constrained Stochastic Problems with Finite Support

We consider mixed-integer linear chance-constrained problems for which the random vector that parameterizes the feasible region has finite support. Our key objective is to improve branch-and-bound or -cut approaches by introducing new types of valid inequalities that improve the dual bound and, by this, the overall performance of such methods. We introduce so-called multi-disjunctive valid inequalities, a generalization of a family of inequalities from the literature. We show properties on the closure of such inequalities to assert their theoretical strength. Moreover, we show that the mathematical programming formulation of the separation problem is unbounded. To resolve the latter challenge, we introduce the rescaled-ℓ1 valid inequalities, a special case of the multi-disjunctive valid inequalities, and propose heuristic separation procedures. Finally, we present extensive numerical results showing the effectiveness of the novel inequalities in comparison to state-of-the-art inequalities from the literature.

Article

Download

View PDF