  Chance-constrained problems involve stochastic components in the constraints
which can be violated with a small probability. We investigate the impact of
different types of chance constraints on the performance of iterative search
algorithms and study the classical maximum coverage problem in graphs with
chance constraints. Our goal is to evolve reliable chance constraint settings
for a given graph where the performance of algorithms differs significantly not
just in expectation but with high confidence. This allows to better learn and
understand how different types of algorithms can deal with different types of
constraint settings and supports automatic algorithm selection. We develop an
evolutionary algorithm that provides sets of chance constraints that
differentiate the performance of two stochastic search algorithms with high
confidence. We initially use traditional approximation ratio as the fitness
function of (1+1)~EA to evolve instances, which shows inadequacy to generate
reliable instances. To address this issue, we introduce a new measure to
calculate the performance difference for two algorithms, which considers
variances of performance ratios. Our experiments show that our approach is
highly successful in solving the instability issue of the performance ratios
and leads to evolving reliable sets of chance constraints with significantly
different performance for various types of algorithms.
