Using Surrogate Information to Solve Multidimensional Multi-choice Knapsack Problem

Abstract

The multidimensional multi-choice knapsack problem (MMKP) is one of the most complex members of the Knapsack Problem (KP) family. It has been used to model large problems such as telecommunications, quality of service (QoS), management problem in computer networks and admission control problem in the adaptive multimedia systems. In this paper, we propose a new approach based on strategic oscillation using surrogate constraint information. We introduce new rules to control oscillation process to solve the MMKP. The main idea is to explore both sides of the feasibility border that consists in alternating both constructive and destructive phases in a strategic oscillating manner. In order to strengthen the surrogate constraint information, we enhance the method with constraints normalization. This may improve the computational results. Numerical results show that the performance of this approach is competitive with previously published results. Performance analysis of the method shows the merits of its using in this problem class.

References

• Glover. F, Laguna M. Tabu search. Boston: Kluwer Academic Publishers; (1998).
• Glover. F, GA. Kochenberger, Critical event tabu search for multidimensional knapsack problems. In: Osman IH, Kelly JP, editors. Metaheuristics: theory and applications. p. 407-27. (1996)
• Hanafi. S, Freville. A, An efficient tabu search approach for the 0-1 multidimensional knapsack problem. European Journal of Operational Research ;106(23):659 75. (1998).
• Glover F. Surrogate constraints: tutorial notes. October (1998).
• Moser M, Declarative scheduling for optimally graceful QoS degradation, in Proc. IEEE Int. Conf. Multimedia Computing Systems (ICMCS), pp. 86 93(1996).
• L. Chen, The utility model applied to layer-coded sources, Dept. of Computer Science, University of Victoria, Victoria, BC, Canada, (1998).
• Khan. S, Quality adaptation in a multisession multimedia system : Model, algorithms and architecture, Ph. D. dissertation, Department of Electrical and Computer Engineering, University of Victoria, Canada (1998).
• Watson. R, The optimal admission and adaptation of service level agreements in packet networks: Applying the utility model, Masters thesis, Dept. of Electrical and Computer Engineering, University of Victoria, Victoria, BC, Canada, (2001).
• Khan. S, K. F. Li and E. G. Manning, The Utility Model for Adaptive Multimedia System. In International Workshop on Multimedia Modeling, pages 111-126 (1997).
• Garey. MR, Johnson. DS, Computers and intractability: a guide to the theory of NP completeness. San Francisco: Freeman; (1979).
• Martello. S, Toth. P, Knapsack problems. New York: Wiley; (1990).
• Healy Jr. WC, Multiple choice programming. Operations Research; 12:122 38. (1964)
• Lin EYH. Multiple choice programming: a state-ofthe- art review. International Transactions in Operational Research;1:409-421. (1994)
• Lin EYH. A bibliographical survey on some well-known nonstandard knapsack problems. ;36(4): 274 317 INFOR (1998)
• Dyer. ME, Walker. J. Dominance in multi-dimensional multiple-choice knapsack problems. Asia Pacific Journal of Operational Research;15(2):15968. (1998)
• Weingatner. HM, Capital budgeting of interrelated projects: survey and synthesis. Operations Research;12: 485-516. (1966)
• Peterson. CC, Computational experience with variants of the Balas algorithm applied to the selection of research and development projects. Management Science 13:736 50. (1967)
• Gilmore. PC, Gomory. RE. The theory and computation of knapsack functions. Operations Research;14: 1045 (1966)
• Shih. W, A branch and bound method for the multi constraint zero-one knapsack problem. Journal of Operations Research Society; 36978. (1979)
• Geo-rion. AM, Lagrangian relaxation for integer programming. Mathematical Programming Study 2:82114. (1974)
• Glover F. Surrogate constraints. Operations Research;16:741. (1968)
• Glover F. Heuristics for integer programming using surrogate constraints. Decision Sciences; 8:15666. (1977)
• Chu PC, Beasley JE. A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics;4: 6386. (1998)
• Bertsimas D, Demir R. An approximate dynamic programming approach to multidimensional knapsack problems. Management Science;48(4):550-565 (2002)
• Mhand Hifi, Slim Sadfi, Abdelkader Sbihi, An exact algorithm for the multiple-choice multidimensional knapsack problem. Cahiers de la MSE b04024, Maison des Sciences Economiques, University paris pantheon-Sorbonne. (2004)
• Khan. S, Li KF, Manning. EG, Akbar. MM, Solving the knapsack problem for adaptive multimedia system. Studia informatica 2:161-82. (2002)
• Mhand Hifi, Michrafy. M, Sbihi. A, Heuristic algorithms for the multiple-choice multidimensional knapsack problem. Journal of the Operational Research Society 55, 13231332 (2004)
• Parra-Hemendez R, N. Dimopoulos, A New Heuristic for Solving the Multi-choice Multidimensional knapsack problem. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions. Volume: 35 , Issue: 5 Page(s): 708- 717 (2005)
• Hifi M. M. Michrafy and A. Sbihi, A reactive local searchbased algorithm for the multiple-choice multi-dimensional knapsack problem, Computational Optimization and Applications, vol. 33, 271-285, (2006)
• Glover. F, Future paths for integer programming and links to artificial intelligence, Computers and Operations Research I9 (1986)
• Lee. C, Lehoczky. J, Rajkumar. R, Siewiorek. D. On quality of service optimization with discrete QoS options. In: RTAS'99: Proceedings of the fifth IEEE real-time technology and applications symposium. Washington, DC, USA: IEEE Computer Society; 1999. p. 276.
• Sadid MWH, Islam MR, Hasan SMK, A new strategy for solving multiple- choice multiple-dimension knapsack problem in pram model. In: Asian Applied Computing Conference. 2005.
• Kellerer H, Pferschy. U, Pisinger. D, Knapsack problems. Berlin: Springer; 2004.
• Chaitr S. Hire. M, Raymond. Hill2, New greedy heuristics for the Multiple-choice Multi-dimensional Knapsack Problem. International Journal of Operational Research Volume 2, 2007 Pages 495-512.
• Shahrear Iqbal, Md. Faizul Bari, M. Sohel Rahman, Solving the Multi-dimensional Multi-choice Knapsack Problem with the Help of Ants. ANTS Conference 2010: 312-323
• Beasley. J, OR-Library: Distributing test problems by electronic mail. The Journal of the Operational Research Society 41(11), 10691072 (1990)
• Alaya. I, C. Solnon et K. Ghedira, Des fourmis pour le sac a dos multidimensionnel. Dans : 4mes Journes Francophones de Recherche Oprationnelle (Francoro 2004), Fribourg, Suisse, pp. 159-160, 2004
• Han I, Jimmy Leblet, Gwendal Simon, Hard multidimensional multiple choice knapsack problems, an empirical study, Computers Operations Research, (2010), 37, 172-181.
• Cherfi. M, Hifi. M, A column generation method for the multiple-choice multi-dimensional knapsack problem, Comput. Optim. App. online first, Springer Netherlands (2008).
• Sbihi. A, A best first search exact algorithm for the multiplechoice multidimensional knapsack problem, Journal of Combinatorial Optimization 13 (4) (2007) 337-351.
• Rad Mansia, Cludio Alvesa, J. M. Valrio de Carvalhoa and Said Hanafi. A hybrid heuristic for the multiple choice multidimensional knapsack problem. Engineering Optimization. iFirst, 1-22 (2011)
• Romain Picot-Clmente, Florence Mendes, Christophe Cruz, Christophe Nicolle. TOURISM-KM, A variant of MMKP applied to the tourism domain. ICORES 2012, Portugal (2012)
• Ykman-Couvreur, Cliaiztal MEC, Leuven Nollet, Vincent, Fast Multi-Dimension Multi-Choice Knapsack Heuristic for MP-SoC Run-Time Management. International Symposium on. Henk System-on-Chip, 2006 pages 1-4.
• I. Crevits, S. Hanafi, R. Mansi, and C. Wilbaut, Iterative semicontinuous relaxation heuristics for the multiple-choice multidimensional knapsack problem. Computers and Operations Research, 2011.
• S. Hanafi, R. Mansi, and C. Wilbaut, Iterative relaxation-based heuristics for the multiple-choice multidimensional knapsack problem. volume 5818 of Lecture Notes in Computer Science, pages 7383. Springer Verlag, 2009.
• T. Ghasemi and M. Razzazi, Development of core to solve the multidimensional multiple-choice knapsack problem. Computers and Operations Research, 60:349-360, 2010.
• M. Razzazi and T. Ghasemi, An exact algorithm for the multiple-choice multidimensional knapsack based on the core. Advances in Computer Science and Engineering, Communications in Computer and Information Science, 6:275-282, 2008.
• N. Cherfi and M. Hifi, Hybrid algorithms for the multiplechoice multi-dimensional knapsack problem. International Journal of Operational Research, 5(1):89-109, 2009.
• Rad Mansi, Cludio Alves, J. M. Valrio de Carvalho and Said Hanafi, A hybrid heuristic for the multiple choice multidimensional knapsack problem. Engineering Optimization, 2012. DOI:10. 1080/0305215X. 2012. 717072 .
• Gaige. W, Lihong. G, A Novel Hybrid Bat Algorithm with Harmony Search for Global Numerical Optimization, Journal of Applied Mathematics, vol. 2013, 21pages, 2013. doi 10. 1155/2013/696491
• Gaige. W, Lihong. G, Hong. Duan, Heqi. W, Luo. L, and Mingzhen. S. A Hybrid Metaheuristic DE/CS Algorithm for UCAV Three-Dimension Path Planning, The Scientific World Journal, vol. 2012, 11 pages, 2012. doi:10. 1100/2012/583973

Index Terms

Keywords