Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/10230/935

Restless bandits, linear programming relaxations and a primal-dual index heuristic
Bertsimas, Dimitris; Niño-Mora, José
Universitat Pompeu Fabra. Departament d'Economia i Empresa
We develop a mathematical programming approach for the classicalPSPACE - hard restless bandit problem in stochastic optimization.We introduce a hierarchy of n (where n is the number of bandits)increasingly stronger linear programming relaxations, the lastof which is exact and corresponds to the (exponential size)formulation of the problem as a Markov decision chain, while theother relaxations provide bounds and are efficiently computed. Wealso propose a priority-index heuristic scheduling policy fromthe solution to the first-order relaxation, where the indices aredefined in terms of optimal dual variables. In this way wepropose a policy and a suboptimality guarantee. We report resultsof computational experiments that suggest that the proposedheuristic policy is nearly optimal. Moreover, the second-orderrelaxation is found to provide strong bounds on the optimalvalue.
15-09-2005
Microeconomics
stochastic scheduling
bandit problems
resource allocation
dynamic programming
L'accés als continguts d'aquest document queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Documento de trabajo
         

Mostrar el registro completo del ítem