Sign In
Register
eISSN:2278-5299

International Journal of Latest Research in Science and Technology

DOI:10.29111/ijlrst   ISRA Impact Factor:3.35

A News Letter Sign UP!
SOLVING THE (0 -1) KNAPSACK PROBLEM BY AN ADAPTED TRANSPORTATION ALGORITHM

Research Paper Open Access

International Journal of Latest Research in Science and Technology Vol.6 Issue 3, pp 20-24,Year 2017

SOLVING THE (0 -1) KNAPSACK PROBLEM BY AN ADAPTED TRANSPORTATION ALGORITHM

Boudjellaba H., Gningue Y. and Shamakhai H.

Correspondence should be addressed to :

Received : 05 May 2017; Accepted : 14 May 2017 ; Published : 30 June 2017

Share
Download 125
View 181
Article No. 10726
Abstract

In this paper we link the zero-one knapsack problem to the linear transportation problem then solve it by using an adaptation of the transportation algorithm. The Vogel Approximation Method is applied to find an initial solution. It consists in assigning to each row and column a penalty which is the difference between the two least costs. The largest penalty indicates the line to be allocated first. Then the variable with the least cost on that line is assigned. For the zero-one knapsack problem, the Vogel method is shown to be equivalent to the Greedy Algorithm. That initial solution is then improved by using the dual variable and resulting reduced cost. We detect conditions which indicate that the optimal solution is reached. We also prove that when no further cost’s reduction is possible, then an optimal solution is obtained. This approach opens a new field of research which treats the zero-one knapsack problem as a transportation problem.

Key Words   
Knapsack problem, Linear Transportation problem, Assignment problem, Vogel Approximation M

Copyright
References
  1. Bellman R. (1957), Dynamic programming (1st Edition), Princeton University Press, Princeton, NJ, USA.
  2. Caprara A., Kellerer H. and  Pferschy U.(2000), “The Multiple Subset Sum Problem”, SIAM Journal on  Optimization, Vol. 11, No. 2, pp. 308–319.
  3. Dantzig, George B. (1957). "Discrete-Variable Extremum Problems". Operations Research. 5 (2): 266–288. doi:1287/opre.5.2.266
  4. Hristakeva, M. and Dipti S. (2004) “Solving the 0/1 Knapsack Problem with Genetic Algorithms.” MICS 2004 Proceedings :www.micsymposium.org/mics_2004/Hristake.pdf
  5. Horowitz, Ellis; Sahni, Sartaj (1974), "Computing partitions with applications to the knapsack problem", Journal of the Association for Computing Machinery, 21: 277–292.
  6. Kellerer, H., Pferschy, U and Pisinger, D. Knapsack problems. 2004.
  7. Kolesar, P. J. (1967). A branch and bound algorithm for the knapsack problem. Management science, 13(9), 723-735.
  8. Loots, W. and Smith, T.H.C. “A parallel algorithm for the zero-one knapsack problem”, in J. Parallel Program.21, 5, 1992, pp.313–348.
  9. Martello, S., Pisinger, D., and Toth, P. (1999). Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science, 45(3), 414-424.
  10. Martello, S., and Toth, P. (1990). Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc.. ISBN:0-471-92420-2.
  11. Penn, M., Hasson, D. and Avriel, M.“Solving the 0–1 proportional Knapsack problem by sampling”, Int. Journal Optim. Theory Appl.80, 2,1994, pp. 261–272.
  12. Pisinger D (1999). "Linear Time Algorithms for Knapsack Problems with Bounded Weights". Journal of Algorithms, Volume 33, Number 1, October 1999, pp. 1–14.
  13. Sahni, S. (1975), "Approximate Algorithm for  knapsack problem", Journal of the Association for Computing Machinery, 22, 1, pp. 115–124.
  14. Teghem J. (2012), Recherche Opérationnelle, Méthodes d’optimisation, Ellipses, Tome 1, p. 247-253.
  15. Yadav and S. Singh (2016), “Genetic Algorithms Based Approach to Solve 0-1 Knapsack Optimization Problem”, International Journal of Innovative Research in Computer and Communication Engineering,  Vol. 4, Issue 5.  ISSN(Online): 2320-9801,  ISSN (Print) : 2320-9798.
To cite this article

Boudjellaba H., Gningue Y. and Shamakhai H. , " Solving The (0 -1) Knapsack Problem By An Adapted Transportation Algorithm ", International Journal of Latest Research in Science and Technology . Vol. 6, Issue 3, pp 20-24 , 2017

Responsive image

MNK Publication was founded in 2012 to upholder revolutionary ideas that would advance the research and practice of business and management. Today, we comply with to advance fresh thinking in latest scientific fields where we think we can make a real difference and growth now also including medical and social care, education,management and engineering.

Responsive image

We offers several opportunities for partnership and tie-up with individual, corporate and organizational level. We are working on the open access platform. Editors, authors, readers, librarians and conference organizer can work together. We are giving open opportunities to all. Our team is always willing to work and collaborate to promote open access publication.

Responsive image

Our Journals provide one of the strongest International open access platform for research communities. Our conference proceeding services provide conference organizers a privileged platform for publishing extended conference papers as journal publications. It is deliberated to disseminate scientific research and to establish long term International collaborations and partnerships with academic communities and conference organizers.