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

Alfredo Garcia (), Stephen D. Patek () and Kaushik Sinha ()
Additional contact information
Alfredo Garcia: Department of Systems and Information Engineering, University of Virginia, Charlottesville, Virginia 22904
Stephen D. Patek: Department of Systems and Information Engineering, University of Virginia, Charlottesville, Virginia 22904
Kaushik Sinha: Department of Systems and Information Engineering, University of Virginia, Charlottesville, Virginia 22904

Operations Research, 2007, vol. 55, issue 4, 717-732

Abstract: 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.

Keywords: simulation; games/group decisions; networks (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1060.0379 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:55:y:2007:i:4:p:717-732

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().