Modeling and Solving Robust Chance-Constrained Binary Programs Using Sample Average Approximations

This chapter describes the modeling and solution approaches for binary programs involving chance constraints with ambiguously described probability distributions followed by the parameters. Here the chance constraints are satisfied over all possible probability distributions that belong to an ambiguity set. We use a stochastic bin packing model as an illustrative example. A bin packing problem allocates items of a certain size to a bin of a fixed capacity while minimizing the total allocation cost. The study of distributional robustness in chance-constrained is a topic of recent development. In a chance-constrained packing problem, we allocate items to a bin so that the bin capacity exceeds only with the desired probability. This chapter also describes a probability cut-based algorithm for solving such problems and presents computational results for their effectiveness. The computational results are presented using an ambiguity set of distributions described using the Wasserstein metric. The value of using an ambiguity set in improving the out-of-sample performance for satisfying the chance constraint is also illustrated.