Performance analysis of online anticipatory algorithms for large multistage stochastic integer programs

Despite significant algorithmic advances in recent years, finding optimal policies for large-scale, mul-tistage stochastic combinatorial optimization prob-lems remains far beyond the reach of existing meth-ods. This paper studies a complementary approach, online anticipatory algorithms, that make decisions at each step by solving the anticipatory relaxation for a polynomial number of scenarios. Online an-ticipatory algorithms have exhibited surprisingly good results on a variety of applications and this paper aims at understanding their success. In par-ticular, the paper derives sufficient conditions under which online anticipatory algorithms achieve good expected utility and studies the various types of er-rors arising in the algorithms including the antic-ipativity and sampling errors. The sampling error is shown to be negligible with a logarithmic num-ber of scenarios. The anticipativity error is harder to bound and is shown to be low, both theoretically and experimentally, for the existing applications.