Application of Coordinate Transformation with Close-Form Exact Algorithm for Minimizing Maximum Processing Time in the Unbounded Knapsack Problem

Main Article Content

Chanin Srisuwannapa*
Peerayuth Chansethikul

Abstract

We address a variant of the unbounded knapsack problem (UKP) into which the processing time of each item is also put and considered, referred as MMPTUKP problem. The problem is a decision of allocating amount of n items such that the maximum processing time of the selected items is minimized and the total profit is gained as at least as determined without exceeding capacity of knapsack (budget). In this paper, we proposed the new modified exact algorithm for this problem, CTCFMMPTUKP algorithms. It applied the coordinate transformation with CFMMPTUKP algorithm, close-form exact algorithm. We present computational experiments with 4 different type of problems for which data were generated to validate our ideas and demonstrate the efficiency of the proposed algorithms. It can be concluded that, for most types of problems, the proposed CTCFMMPTUKP algorithms performs in term of solution time faster than the 5 other algorithms.


Keywords:  Linear programming, Simplex method, Integer linear programming, Branch and bound algorithm, Unbounded and bounded knapsack problem, Processing time.


Corresponding author: E-mail: chanin_sri@yahoo.com

Article Details

Section
Original Research Articles

References

[1] P.toth (2000), Optimization engineering techniques for the exact solution of NP-hard combination optimization problem, European Journal of Operation Research, vol 125, pp. 222-238.
[2] S. Martello, D. Psinger, P. Toth (1999), Dynamic programming and strong bounds for the 0-1 knapsack problem, Management Science, vol. 45, pp 414-424.
[3] A. Freville, G. Plateau (1986), Heuristics and reduction methods for multiple constrains Linear Programming, European Journal of Operations Research, vol 24, pp. 206-215.
[4] D. Psinger (1999), An exact algorithm for large multiple knapsack problem, European Journal of Operations Research, vol 114, pp. 528-541.
[5] S. Martello, P. Toth (1981), A branch-and- bound algorithm for the zero-one knapsack problem, Discrete Applied Mathematics, vol 3, pp.275-288.
[6] D. Psinger (1995), A minimal algorithm for the multiple-choice Knapsack Problem, European Journal of Operations Research, vol 83, pp. 394-410
[7] D. Psinger (2001), Budgeting with bound multiple-choice constraints, European Journal of Operations Research, vol 129, pp.471-480.
[8] R. Andonow, V. Poirriez, S. Rajopadhye (2000), Unbounded knapsack problem: Dynamic programming revised, European Journal of Operations Research, vol 123, pp. 394-407.
[9] Srisuwannapa, C., Charnsettikul, P. (2001), A exact algorithm for solving the Unbounded Knapsack Problem with Minimizing Maximum Processing Time, Proceedings of Seminar in Applied Optimization, A Publication of Industrial Engineering Department, Faculty of Engineering, Kasetsart University, Bangkhen, Thailand, pp.83-89.
[10] Srisuwannapa, C., Charnsettikul, P. (2004), Application of Coordinate Transformation with MMPTUKP for Minimzing Maximum Processing Time in Unbounded Knapsack Problem, Proceedings of The 1 st KMITL International Conferences on Integration of Science and Technology for Sustrainable Development, KMITL, Ladkrabang, Bangkok, Thailand, vol: 1, p 25-28.
[11] Srisuwannapa, C., Charnsettikul, P. (2004), Modified exact algorithms for Minimizing Maximum Processing Time in the Unbounded knapsack Problem, Proceedings of Meeting in Operation Researches in 2004, Industrial Engineering Department, Faculty of Engineering, Kasetsart University, Bangkhen, Thailand, pp.207-221.
[12] Srisuwannapa, C., Charnsettikul, P. (2004), Close-form exact algorithm for Minimizing Maximum Processing Time in the Unbounded knapsack Problem. KMITL SCIENCE JOURNAL, KMITL, Thailand, Vol 4, 2004, pp.310-321.