  We introduce a novel approach to reduce the computational effort of solving
mixed-integer convex chance constrained programs through the scenario approach.
Instead of reducing the number of required scenarios, we directly minimize the
computational cost of the scenario program. We exploit the problem structure by
efficiently partitioning the constraint function and considering a multiple
chance constrained program that gives the same probabilistic guarantees as the
original single chance constrained problem. We formulate the problem of finding
the optimal partition, a partition achieving the lowest computational cost, as
an optimization problem with nonlinear objective and combinatorial constraints.
By using submodularity of the support rank of a set of constraints, we propose
a polynomial-time algorithm to find suboptimal solutions to this partitioning
problem and we give approximation guarantees for special classes of cost
metrics. We illustrate that the resulting computational cost savings can be
arbitrarily large and demonstrate our approach on two case studies from
production and multi-agent planning.
