International E-publication: Publish Projects, Dissertation, Theses, Books, Souvenir, Conference Proceeding with ISBN.  International E-Bulletin: Information/News regarding: Academics and Research

Optimal solutions to a stochastic knapsack problem with contagious distributional capacity

    ,

Author Affiliations

  • 1Department of Mathematics and statistics, University of Port Harcourt, Nigeria
  • 2Department of Mathematics and statistics, University of Port Harcourt, Nigeria

Res. J. Mathematical & Statistical Sci., Volume 6, Issue (5), Pages 1-10, May,12 (2018)

Abstract

The stochastic knapsack problem has continued to generate interest in many areas especially in the area of resource allocation. Of the two forms of the stochastic knapsack problem, the static knapsack problem has been studied over the years by considering the distribution of one of the parameters of a knapsack such as weight, capacity, profit, etc. however, optimal solutions for parameters having contagious distributions have not been considered. This study therefore seeks to obtain optimal solutions to a stochastic knapsack problem following a contagion capacity of Poisson and Gamma distribution. The simplex method of Witchakul et al. (2007) was adopted in developing an algorithm as well as a Monte Carlo and Heuristics algorithms. The result shows optimal solutions were gotten for up to 75,000 variables and the Heuristics algorithm performed much better than the main algorithm and Monte Carlo algorithms respectively.

References

  1. Stewart T.J. (1981)., The secretary problem with an unknown number of options., Operations Research, 29(1), 130-145.
  2. Mendelson H., Pliskin J.S. and Yechiali U. (1980)., A stochastic allocation problem., Operations Research, 28(3-part-ii), 687-693.
  3. Kleywegt A.J. and Papastavrou J.D. (2001)., The dynamic and stochastic knapsack problem with random sized items., Operations Research, 49(1), 26-41.
  4. Dean B.C., Goemans M.X. and Vondrdk J. (2004)., Approximating the stochastic knapsack problem: The benefit of adaptivity., Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, IEEE, 208-217.
  5. Levin A. and Vainer A. (2013)., The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature., Discrete Optimization, 10(2), 147-154.
  6. Steinberg E. and Parks M.S. (1979)., A preference order dynamic program for a knapsack problem with stochastic rewards., Journal of the Operational Research Society, 30(2), 141-147.
  7. Sniedovich M. (1980)., Preference order stochastic knapsack problems: methodological issues., Journal of the Operational Research Society, 31(11), 1025-1032.
  8. Cohn A.M. and Barnhart C. (1998)., The stochastic knapsack problem with random weights: A heuristic approach to robust transportation planning., In in Proceedings of the Triennial Symposium on Transportation Analysis.
  9. Witchakul S., Ayudhaya P.S. and Charnsethikul P. (2008)., A stochastic knapsack problem with continuous random capacity., Journal of Mathematics and Statistics, 4(4), 269.
  10. Ağralı S. and Geunes J. (2009)., A single-resource allocation problem with Poisson resource requirements., Optimization Letters, 3(4), 559-571.
  11. Merzifonluo˘glu Y., Geunes J. and Romeijn H.E. (2012)., The static stochastic knapsack problem with normally distributed item sizes., Mathematical Programming, 134(2), 459-489.
  12. Chen K. and Ross S.M. (2015)., Static stochastic knapsack problems., Probability in the Engineering and Informational Sciences, 29(04), 527-546.
  13. Henig M.I. (1990)., Risk criteria in a stochastic knapsack problem., Operations Research, 38(5), 820-825.
  14. Carraway R.L., Schmidt R.L. and Weatherford L.R. (1993)., An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns., Naval Research Logistics (NRL), 40(2), 161-173.
  15. Goel A. and Indyk P. (1999)., Stochastic load balancing and related problems., In1999, 40th Annual Symposium on Foundations of Computer Science, IEEE, 579-586.
  16. Kosuch S. and Lisser A. (2010)., Upper bounds for the 0-1 stochastic knapsack problem and a branch and-bound algorithm., Annals of Operations Research, 176, 77-93.
  17. Kosuch S. and Lisser A. (2011)., On two-stage stochastic knapsack problems., Discrete Applied Mathematics, 159(16), 1827-1841.
  18. Witchakul S., Sudasna-na-Ayudthya P. and Charnsethikul P. (2007)., A heuristic for solving a stochastic knapsack problem with discrete random capacity., Thammasat International Journal of Science and Technology, 12(1).
  19. Mood A., Graybill F. and Boes D. (1974)., Introduction to the Theory of Statistics., 3rd Edition, McGrawHill.
  20. Etuk E.H., Essi I.D. and Akpan N.P. (2010)., A Stochastic knapsack problem with mixed distributional capacity.,
  21. Akpan N.P. and Etuk E.H. (2012)., A Stochastic Knapsack Model with The Capacity Following an Additive form of Contagious Distribution., Journal of Basic and Applied Scientific Research, 2(6), 5431-5446.
  22. Akpan N.P., Etuk E.H. and Essi I.D. (2012)., A stochastic knapsack problem with additive model of contagious distribution for the weight., African Journal of Mathematics and Computer Science Research, 5(14), 253-273.