This Article Full Text (PDF) e-companion References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Garcia, A. Articles by Sinha, K. Search for Related Content

A Decentralized Approach to Discrete Optimization via Simulation: Application to Network Flow

Department of Systems and Information Engineering, University of Virginia, Charlottesville, Virginia 22904
Department of Systems and Information Engineering, University of Virginia, Charlottesville, Virginia 22904
Department of Systems and Information Engineering, University of Virginia, Charlottesville, Virginia 22904
agarcia{at}virginia.edu
patek{at}virginia.edu
ksinha{at}alumni.virginia.edu

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.

Subject classifications: simulation; games/group decisions; networks.
History: Received May 2005; revision received July 2006; accepted August 2006.