On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming
| العنوان: | On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming |
|---|---|
| المؤلفون: | Daniela Pucci de Farias, Benjamin Van Roy |
| المصدر: | Mathematics of Operations Research. 29:462-478 |
| بيانات النشر: | Institute for Operations Research and the Management Sciences (INFORMS), 2004. |
| سنة النشر: | 2004 |
| مصطلحات موضوعية: | Mathematical optimization, Linear programming, General Mathematics, Management Science and Operations Research, Constraint satisfaction, Computer Science Applications, Linear-fractional programming, Dynamic programming, Goal programming, Bellman equation, Constraint programming, Computer Science::Programming Languages, Markov decision process, Mathematics |
| الوصف: | In the linear programming approach to approximate dynamic programming, one tries to solve a certain linear program—the ALP—that has a relatively small number K of variables but an intractable number M of constraints. In this paper, we study a scheme that samples and imposes a subset of m≪M constraints. A natural question that arises in this context is: How must m scale with respect to K and M in order to ensure that the resulting approximation is almost as good as one given by exact solution of the ALP? We show that, given an idealized sampling distribution and appropriate constraints on the K variables, m can be chosen independently of M and need grow only as a polynomial in K. We interpret this result in a context involving controlled queueing networks. |
| تدمد: | 1526-5471 0364-765X |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::ee26d6fe4d0c35a56848d567d40755b1 https://doi.org/10.1287/moor.1040.0094 |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi...........ee26d6fe4d0c35a56848d567d40755b1 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 15265471 0364765X |
|---|