The benefit of adaptivity in stochastic packing problems with probing

We consider stochastic variants of a wide class of NP-hard packing integer problems. In these variants the problem consists of two stages, the first stage is the probing phase, and the second is the optimization phase. The problem has items, each of which is associated with stochastic information which we can probe. We assume that every probed value corresponds to a distribution, that is, the probing does not fix the exact value of the stochastic information associated with the probed item, but fixes another distribution for that information, that is perhaps different for different outcomes of the probing. All these distributions are known to the optimizer a priori. In the optimization phase, the solution is constructed sequentially, and the act of choosing an item instantiates its stochastic information. The goal is to compute a policy that maximizes the expected value of the given objective function of the resulting solution such that the packing constraints are satisfied, where the output solution is the last feasible solution in the series of solutions which the optimizer creates during the optimization phase. We consider both non-adaptive policies (that designate a priori a fixed permutation of variables in the solution) and adaptive policies (that can make dynamic decisions based on the history of the instantiated values of the stochastic information).Our work characterizes the benefit of adaptivity. For this purpose we use a measure called the adaptivity gap: the supremum over instances of the ratio between the expected value obtained by an optimal adaptive policy and the expected value obtained by an optimal non-adaptive policy. In such problems the benefit of adaptivity is due to two phases: probing and optimization. Assuming that for the optimization phase (without the probing) the benefit of adaptivity is at most ρ, we show an upper bound on the adaptivity gap of 2ρ for the corresponding class with probing. We demonstrate our results for different problems and for each of these classes we provide examples that show that there is indeed a benefit of adaptivity in probing.