A decentralized approach to discrete optimization via simulation: Application to network flow
成果类型：
Article
署名作者：
Garcia, Alfredo; Patek, Stephen D.; Sinha, Kaushik
署名单位：
University of Virginia
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1060.0379
发表日期：
2007
页码：
717-732
关键词：
摘要：
We study a new class of decentralized algorithms for discrete optimization via simulation, which is inspired by the fictitious play algorithm applied to games with identical interests. In this approach, each component of the solution vector of the optimization model is artificially assumed to have a corresponding player, and the interaction of these players in simulation allows for exploration of the solution space and, for some problems, ultimately results in the identification of the optimal solution. Our algorithms also allow for correlation in players' decision making, a key feature when simulation output is shared by multiple decision makers. We first establish convergence under finite sampling to equilibrium solutions. In addition, in the context of discrete network flow models, we prove that if the underlying link cost functions are convex, then our algorithms converge almost surely to an optimal solution.