A chernoff bound approximation for risk-averse integer programming

In this paper we consider optimization problems with a stochastic performance measure, where the goal of the problem is to find a solution that minimizes the probability that this performance measure exceeds a given threshold. It is known that this and related problems are computationally intractable, so we consider an approach that seeks to minimize an upper bound on the probability of exceeding the given threshold. From this approach, we obtain a suboptimal solution, together with a guaranteed upper bound on the achieved exceedance probability. First, we present an algorithm that minimizes a Chernoff bound by solving a binary integer program. For problems with totally unimodular constraint sets, this Chernoff bound can be minimized by solving a linear program. This formulation is shown to recover several known results for the cases of Gaussian and stochastically dominant costs. We then briefly consider these problems in a closed loop setting, where solutions can be refined as the values of uncertain quantities in the model are revealed. We propose an open-loop feedback control algorithm where a binary integer program (or possibly linear program) is solved in each time step given the current state of the system.