An anytime multistep anticipatory algorithm for online stochastic combinatorial optimization

作者：Mercier Luc; Van Hentenryck Pascal^*

来源：Annals of Operations Research, 2011, 184(1): 233-271.

DOI：10.1007/s10479-010-0798-7

• Stochastic optimization
• Scheduling
• Endogenous uncertainty

The one-step anticipatory algorithms (1s-AA) is an online algorithm making decisions under uncertainty by ignoring the non-anticipativity constraints in the future. It was shown to make near-optimal decisions on a variety of online stochastic combinatorial problems in dynamic fleet management and reservation systems.
Here we consider applications in which 1s-AA is not as close to the optimum and propose Amsaa, an anytime multi-step anticipatory algorithm. Amsaa combines techniques from three different fields to make decisions online. It uses the sampling average approximation method from stochastic programming, search algorithms for Markov decision processes from artificial intelligence, and discrete optimization algorithms.
Amsaa was evaluated on a stochastic project scheduling application from the pharmaceutical industry featuring endogenous observations of the uncertainty. The experimental results show that Amsaa significantly outperforms state-of-the-art algorithms on this application under various time constraints.

• 出版日期2011-4