Abstract
Rollout algorithms are heuristic algorithms that can be applied to solve deterministic and stochastic dynamic programming problems. The basic idea is to use the cost obtained by applying a well known heuristic, called the base policy, to approximate the value of the optimal cost-to-go. We develop a theoretical approach to prove, for the 0-1 knapsack problem, that the minimum performance ratio of the rollout algorithms tends to be significantly greater when the performance ratio of the corresponding base policy is poor and that the worst-case performance ratio is significantly better than the one of the corresponding base policies.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bertsekas, D.P., Tsitsiklis, J.N.: Neuro-Dynamic Programming. Athena Scientific, Belmont (1996)
Tesauro, G., Galperin, G.R.: On-line policy improvement using Monte Carlo search. Adv. Neural Inf. Process. Syst. 9, 1068–1074 (1997)
Bertsekas, D.P., Castanõn, D.A.: Rollout algorithms for stochastic scheduling problems. J. Heuristics 5, 89–108 (1998)
Secomandi, N.: Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands. Comput. Oper. Res. 27, 1201–1225 (2000)
Secomandi, N.: A rollout policy for the vehicle routing problem with stochastic demands. Oper. Res. 49, 796–802 (2001)
Secomandi, N.: Analysis of a rollout approach to sequencing problems with stochastic routing applications. J. Heuristics 9, 321–352 (2003)
Novoa, C., Storer, R.: An approximate dynamic programming approach for the vehicle routing problem with stochastic demands. Eur. J. Oper. Res. 196, 509–515 (2009)
Guerriero, F., Mancini, M.: A cooperative parallel rollout algorithm for the sequential ordering problem. Parallel Comput. 29, 663–677 (2003)
Guerriero, F., Mancini, M.: Parallelization strategies for rollout algorithms. Comput. Optim. Appl. 31, 221–244 (2005)
Bertsekas, D.P., Tsitsiklis, J.N., Wu, C.: Rollout algorithms for combinatorial optimization. J. Heuristics 3, 245–262 (1997)
Guerriero, F.: Hybrid rollout approaches for the job shop scheduling problem. J. Optim. Theory Appl. 139, 419–438 (2008)
Bertsimas, D.J., Demir, R.: An approximate dynamic programming approach to multidimensional Knapsack problems. Manag. Sci. 48, 550–565 (2002)
Bertsekas, D.P.: Dynamic Programming and Optimal Control, vol. I. Athena Scientific, Belmont (2005)
Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester (1990)
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)
Sahni, S.: Approximate algorithms for the 0-1 knapsack problem. J. ACM 22, 115–124 (1975)
Caprara, A., Kellerer, H., Pferschy, U., Pisinger, D.: Approximation algorithms for Knapsack problems with cardinality constraints. Eur. J. Oper. Res. 123, 333–345 (2000)
Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problem. J. ACM 22, 463–468 (1975)
Lawler, E.L.: Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4, 339–356 (1979)
Kellerer, H., Pferschy, U.: A new fully polynomial time approximation scheme for the knapsack problem. J. Comb. Optim. 3, 59–71 (1999)
Kellerer, H., Pferschy, U.: Improved dynamic programming in connection with an FPTAS for the Knapsack problem. J. Comb. Optim. 8, 5–11 (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Rainer Burkard.
The author wishes to thank the Associate Editor and two anonymous Referees for their useful comments and suggestions.
Rights and permissions
About this article
Cite this article
Bertazzi, L. Minimum and Worst-Case Performance Ratios of Rollout Algorithms. J Optim Theory Appl 152, 378–393 (2012). https://doi.org/10.1007/s10957-011-9902-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-011-9902-7