Amsaa: A Multistep Anticipatory Algorithm for Online Stochastic Combinatorial Optimization
作者： Luc Mercier , Pascal Van Hentenryck
DOI: 10.1007/978-3-540-68155-7_15
关键词:
摘要: The one-step anticipatory algorithm (1s-AA) is an online making decisions under uncertainty by ignoring future non-anticipativity constraints. It makes near-optimal on a variety of stochastic combinatorial problems in dynamic fleet management, reservation systems, and more. Here we consider applications which 1s-AA not as close to the optimum propose Amsaa, anytime multi-step algorithm. Amsaa combines techniques from three different fields make online. uses sampling average approximation method programming approximate problem; solves resulting problem using search for Markov decision processes artificial intelligence; discrete optimization guiding search. Amsaa was evaluated project scheduling application pharmaceutical industry featuring endogenous observations uncertainty. experimental results show that significantly outperforms state-of-theart algorithms this various time
springer.com
brown.edu
harvard.edu 
sci-hub.st 参考文章(17)
Pascal Van Hentenryck, Luc Mercier, Performance analysis of online anticipatory algorithms for large multistage stochastic integer programs international joint conference on artificial intelligence. pp. 1979- 1984 ,(2007)
Pascal Van Hentenryck, Russell Bent, Waiting and relocation strategies in online stochastic vehicle routing international joint conference on artificial intelligence. pp. 1816- 1821 ,(2007)
Blai Bonet, Hector Geffner, Learning depth-first search: a unified approach to heuristic search in deterministic and non-deterministic settings, and its application to MDPs international conference on automated planning and scheduling. pp. 142- 151 ,(2006)
Jitka Dupačová, Giorgio Consigli, Stein W. Wallace, Scenarios for Multistage Stochastic Programs Annals of Operations Research. ,vol. 100, pp. 25- 53 ,(2000) , 10.1023/A:1019206915174
Michael Kearns, Yishay Mansour, Andrew Y. Ng, A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes Machine Learning. ,vol. 49, pp. 193- 208 ,(2002) , 10.1023/A:1017932429737
Pascal Van Hentenryck, Russell Bent, Online Stochastic Combinatorial Optimization ,(2006)
Andrew G. Barto, Steven J. Bradtke, Satinder P. Singh, Learning to act using real-time dynamic programming Artificial Intelligence. ,vol. 72, pp. 81- 138 ,(1995) , 10.1016/0004-3702(94)00011-O
Jaein Choi, Matthew J Realff, Jay H Lee, None, Dynamic programming in a heuristically confined state space: a stochastic resource-constrained project scheduling application Computers & Chemical Engineering. ,vol. 28, pp. 1039- 1058 ,(2004) , 10.1016/J.COMPCHEMENG.2003.09.024
M. A. H. Dempster, Sequential Importance Sampling Algorithms for Dynamic Stochastic Programming Journal of Mathematical Sciences. ,vol. 133, pp. 1422- 1444 ,(2006) , 10.1007/S10958-006-0058-1
Eric A. Hansen, Shlomo Zilberstein, LAO: a heuristic search algorithm that finds solutions with loops Artificial Intelligence. ,vol. 129, pp. 35- 62 ,(2001) , 10.1016/S0004-3702(01)00106-0