Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of -optimization
The scenario approach developed by Calafiore and Campi to attack chance-constrained convex programs utilizes random sampling on the uncertainty parameter to substitute the original problem with a representative continuous convex optimization with convex constraints which is a relaxation of the original. Calafiore and Campi provided an explicit estimate on the size of the sampling relaxation to yield high-likelihood feasible solutions of the chance-constrained problem. They measured the probability of the original constraints to be violated by the random optimal solution from the relaxation of size . This paper has two main contributions. First, we present a generalization of the Calafiore-Campi results to both integer and mixed-integer variables. In fact, we demonstrate that their sampling estimates work naturally for variables restricted to some subset of . The key elements are generalizations of Helly's theorem where the convex sets are required to intersect . The size of samples in both algorithms will be directly determined by the -Helly numbers. Motivated by the first half of the paper, for any subset , we introduce the notion of an -optimization problem, where the variables take on values over . It generalizes continuous, integer, and mixed-integer optimization. We illustrate with examples the expressive power of -optimization to capture sophisticated combinatorial optimization problems with difficult modular constraints. We reinforce the evidence that -optimization is "the right concept" by showing that the well-known randomized sampling algorithm of K. Clarkson for low-dimensional convex optimization problems can be extended to work with variables taking values over .