Advanced search
Publication Cover
Journal of the Operational Research Society Volume 55, 2004 - Issue 12
Submit an article Journal homepage
423
Views
94
CrossRef citations to date
0
Altmetric
Theoretical Paper

Heuristic algorithms for the multiple-choice multidimensional knapsack problem

M HifiLaRIA, UPJVAmiensFrance;CERMSEM-CNRS UMR 8095, Universite de Paris 1ParisFranceCorrespondence[email protected]
,
M MichrafyCERMSEM-CNRS UMR 8095, Universite de Paris 1ParisFrance
&
A SbihiLaRIA, UPJVAmiensFranceCorrespondence[email protected]
Pages 1323-1332 | Received 01 Mar 2003, Accepted 01 Apr 2004, Published online: 21 Dec 2017

Citations (94)

Keep up to date with the latest research on this topic with citation updates for this article.

Subscribe to citation updates

Read on this site (8)

Timothy Sprock, Conrad Bock & Leon F. McGinnis. (2019) Survey and classification of operational control problems in discrete event logistics systems (DELS). International Journal of Production Research 57:15-16, pages 5215-5238.
Read now
Nicolas Brulard, Van-Dat Cung, Nicolas Catusse & Cyril Dutrieux. (2019) An integrated sizing and planning problem in designing diverse vegetable farming systems. International Journal of Production Research 57:4, pages 1018-1036.
Read now
Stefan Voß & Eduardo Lalla-Ruiz. (2016) A set partitioning reformulation for the multiple-choice multidimensional knapsack problem. Engineering Optimization 48:5, pages 831-850.
Read now
Mhand Hifi & Lei Wu. (2015) Lagrangian heuristic-based neighbourhood search for the multiple-choice multi-dimensional knapsack problem. Engineering Optimization 47:12, pages 1619-1636.
Read now
A Sbihi. (2013) Adaptive perturbed neighbourhood search for the expanding capacity multiple-choice knapsack problem. Journal of the Operational Research Society 64:10, pages 1461-1473.
Read now
Raïd Mansi, Cláudio Alves, J. M. Valério de Carvalho & Saïd Hanafi. (2013) A hybrid heuristic for the multiple choice multidimensional knapsack problem. Engineering Optimization 45:8, pages 983-1004.
Read now
Natalie S. Cherbaka & Russell D. Meller. (2008) Modeling multiple plant sourcing decisions. International Journal of Production Research 46:18, pages 5165-5190.
Read now
M Hifi & M Michrafy. (2006) A reactive local search-based algorithm for the disjunctively constrained knapsack problem. Journal of the Operational Research Society 57:6, pages 718-726.
Read now

Articles from other publishers (86)

Simona Mancini, Carlo Meloni & Michele Ciavotta. (2022) A decomposition approach for multidimensional knapsacks with family‐split penalties. International Transactions in Operational Research 31:4, pages 2247-2271.
Crossref
Mohammadreza Valaei & Vahid Khodakarami. (2024) A Framework for Valuation and Portfolio Optimization of Venture Capital Deals with Contractual Terms. Mathematical Problems in Engineering 2024, pages 1-21.
Crossref
Hao Luo & Hung-Yu Wei. (2023) Resource Orchestration at the Edge: Intelligent Management of mmWave RAN and Gaming Application QoE Enhancement. IEEE Transactions on Network and Service Management 20:1, pages 385-399.
Crossref
Lisha Wang, Chenglin Li, Wenrui Dai, Shaohui Li, Junni Zou & Hongkai Xiong. (2023) QoE-Driven Adaptive Streaming for Point Clouds. IEEE Transactions on Multimedia 25, pages 2543-2558.
Crossref
Oleksandr Trofymchuk, Volodymyr Vasyanin, Volodymyr Sokolov, Arkadii Chikrii & Liudmyla Ushakova. (2022) On the Use of Gray Codes for Solving 0-1 Combinatorial Problems of Optimization in Environmental and Economic Systems. Cybernetics and Computer Technologies:4, pages 15-32.
Crossref
Valentina Cacchiani, Manuel Iori, Alberto Locatelli & Silvano Martello. (2022) Knapsack problems — An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems. Computers & Operations Research 143, pages 105693.
Crossref
Kyle Robert Harrison, Saber M. Elsayed, Terence Weir, Ivan L. Garanovich, Sharon G. Boswell & Ruhul A. Sarker. (2022) Solving a novel multi-divisional project portfolio selection and scheduling problem. Engineering Applications of Artificial Intelligence 112, pages 104771.
Crossref
Jaeyoung Yang, Yong-Hyuk Kim & Yourim Yoon. (2022) A Memetic Algorithm with a Novel Repair Heuristic for the Multiple-Choice Multidimensional Knapsack Problem. Mathematics 10:4, pages 602.
Crossref
Leonardo Lamanna, Renata Mansini & Roberto Zanotti. (2022) A two-phase kernel search variant for the multidimensional multiple-choice knapsack problem. European Journal of Operational Research 297:1, pages 53-65.
Crossref
Christophe Wilbaut, Saïd Hanafi, Igor Machado Coelho & Abilio Lucena. 2022. The Palgrave Handbook of Operations Research. The Palgrave Handbook of Operations Research 105 151 .
Kyle Robert Harrison, Saber M. Elsayed, Ivan L. Garanovich, Terence Weir, Sharon G. Boswell & Ruhul Amin Sarker. 2022. Evolutionary and Memetic Computing for Project Portfolio Selection and Scheduling. Evolutionary and Memetic Computing for Project Portfolio Selection and Scheduling 89 123 .
Lin Yang, Ali Zeynali, Mohammad H. Hajiesmaili, Ramesh K. Sitaraman & Don Towsley. (2021) Competitive Algorithms for Online Multidimensional Knapsack Problems. Proceedings of the ACM on Measurement and Analysis of Computing Systems 5:3, pages 1-30.
Crossref
Narges Ahani, Tommy AnderssonAlessandro MartinelloAlexander Teytelboym & Andrew C. Trapp. (2021) Placement Optimization in Refugee Resettlement. Operations Research 69:5, pages 1468-1486.
Crossref
Lei Yang, Jiannong Cao, Zhenyu Wang & Weigang Wu. (2021) Network Aware Mobile Edge Computation Partitioning in Multi-User Environments. IEEE Transactions on Services Computing 14:5, pages 1478-1491.
Crossref
Kyle Robert Harrison, Saber Elsayed, Ruhul A. Sarker, Ivan L. Garanovich, Terence Weir & Sharon G. Boswell. (2021) Project portfolio selection with defense capability options. Project portfolio selection with defense capability options.
Lisha Wang, Chenglin Li, Wenrui Dai, Junni Zou & Hongkai Xiong. (2021) QoE-Driven and Tile-Based Adaptive Streaming for Point Clouds. QoE-Driven and Tile-Based Adaptive Streaming for Point Clouds.
Yaxiong Yuan, Lei Lei, Thang X. Vu, Symeon Chatzinotas, Sumei Sun & Bjorn Ottersten. (2021) Energy Minimization in UAV-Aided Networks: Actor-Critic Learning for Constrained Scheduling Optimization. IEEE Transactions on Vehicular Technology 70:5, pages 5028-5042.
Crossref
Simona Mancini, Michele Ciavotta & Carlo Meloni. (2021) The Multiple Multidimensional Knapsack with Family-Split Penalties. European Journal of Operational Research 289:3, pages 987-998.
Crossref
Francescomaria Faticanti, Francesco De Pellegrini, Domenico Siracusa, Daniele Santoro & Silvio Cretti. (2020) Throughput-Aware Partitioning and Placement of Applications in Fog Computing. IEEE Transactions on Network and Service Management 17:4, pages 2436-2450.
Crossref
Himangshu Kalita & Jekan Thangavelautham. (2020) Automated Design of CubeSats using Evolutionary Algorithm for Trade Space Selection. Aerospace 7:10, pages 142.
Crossref
Arij Mkaouar, Skander Htiouech & Habib Chabchoub. (2020) Solving the Multiple choice Multidimensional Knapsack problem with ABC algorithm. Solving the Multiple choice Multidimensional Knapsack problem with ABC algorithm.
Yaping Sun, Zhiyong Chen, Meixia Tao & Hui Liu. (2020) Bandwidth Gain From Mobile Edge Computing and Caching in Wireless Multicast Systems. IEEE Transactions on Wireless Communications 19:6, pages 3992-4007.
Crossref
Renata Mansini & Roberto Zanotti. (2020) A Core-Based Exact Algorithm for the Multidimensional Multiple Choice Knapsack Problem. INFORMS Journal on Computing.
Crossref
Shan Li, Kun Zhu, Yuanyuan Xu, Ran Wang & Yanchao Zhao. (2019) Resource Allocation for Mobile Blockchain: A Hierarchical Combinatorial Auction Approach. Resource Allocation for Mobile Blockchain: A Hierarchical Combinatorial Auction Approach.
Yaping Sun, Zhiyong Chen, Meixia Tao & Hui Liu. (2019) Communications, Caching, and Computing for Mobile Virtual Reality: Modeling and Tradeoff. IEEE Transactions on Communications 67:11, pages 7573-7586.
Crossref
A. Rogeau, R. Girard, Y. Abdelouadoud & G. Kariniotakis. (2019) Retrofitting a building stock: modeling and optimization for decision aiding at territory scale. Journal of Physics: Conference Series 1343:1, pages 012029.
Crossref
Marco Caserta & Stefan Voß. (2019) The robust multiple-choice multidimensional knapsack problem. Omega 86, pages 16-27.
Crossref
Mohamed Abdel-Basset, Doaa El-Shahat, Hossam Faris & Seyedali Mirjalili. (2019) A binary multi-verse optimizer for 0-1 multidimensional knapsack problems with application in interactive multimedia systems. Computers & Industrial Engineering 132, pages 187-206.
Crossref
Reuven Cohen & Evgeny Moroshko. (2018) Sampling-on-Demand in SDN. IEEE/ACM Transactions on Networking 26:6, pages 2612-2622.
Crossref
Hui Yu, Jiahai Yang, Carol Fung, Raouf Boutaba & Yi Zhuang. (2018) ENSC: Multi-Resource Hybrid Scaling for Elastic Network Service Chain in Clouds. ENSC: Multi-Resource Hybrid Scaling for Elastic Network Service Chain in Clouds.
Yaping Sun, Zhiyong Chen, Meixia Tao & Hui Liu. (2018) Modeling and Trade-Off for Mobile Communication, Computing and Caching Networks. Modeling and Trade-Off for Mobile Communication, Computing and Caching Networks.
Nazih Salhab, Rana Rahim & Rami Langar. (2018) Throughput-Aware RRHs Clustering in Cloud Radio Access Networks. Throughput-Aware RRHs Clustering in Cloud Radio Access Networks.
Ewa M. Bednarczuk, Janusz Miroforidis & Przemysław Pyzel. (2018) A multi-criteria approach to approximate solution of multiple-choice knapsack problem. Computational Optimization and Applications 70:3, pages 889-910.
Crossref
Ali A. Haghighi, Shahram Shahbazpanahi & Shahram Shah Heydari. (2018) Stochastic QoE-Aware Optimization in Cloud-Based Content Delivery Networks. IEEE Access 6, pages 32662-32672.
Crossref
Ramón Alvarez-Valdes, Maria Antónia Carravilla & José Fernando Oliveira. 2018. Handbook of Heuristics. Handbook of Heuristics 1 46 .
Ramón Alvarez-Valdes, Maria Antónia Carravilla & José Fernando Oliveira. 2018. Handbook of Heuristics. Handbook of Heuristics 931 977 .
Abdullah Alsheddy, Christos Voudouris, Edward P. K. Tsang & Ahmad Alhindi. 2018. Handbook of Heuristics. Handbook of Heuristics 261 297 .
Lei Yang, Jiannong Cao, Zhenyu Wang & Weigang Wu. (2017) Network Aware Multi-User Computation Partitioning in Mobile Edge Clouds. Network Aware Multi-User Computation Partitioning in Mobile Edge Clouds.
Chao Gao, Guanzhou Lu, Xin Yao & Jinlong Li. (2017) An iterative pseudo-gap enumeration approach for the Multidimensional Multiple-choice Knapsack Problem. European Journal of Operational Research 260:1, pages 1-11.
Crossref
Mehdi Azarmi & Bharat Bhargava. (2017) An End-to-End Dynamic Trust Framework for Service-Oriented Architecture. An End-to-End Dynamic Trust Framework for Service-Oriented Architecture.
Hongbin Dong, Xue Yang, Xuyang Teng & Yuhai Sha. (2016) A diversity reserved quantum particle swarm optimization algorithm for MMKP. A diversity reserved quantum particle swarm optimization algorithm for MMKP.
David S.W. Lai, Ozgun Caliskan Demirag & Janny M.Y. Leung. (2016) A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transportation Research Part E: Logistics and Transportation Review 86, pages 32-52.
Crossref
Abdullah Alsheddy, Christos Voudouris, Edward P. K. Tsang & Ahmad Alhindi. 2016. Handbook of Heuristics. Handbook of Heuristics 1 37 .
Yongluan Zhou, Lidan Shou, Xuan Shang & Ke Chen. (2015) Dissemination of anonymized streaming data. Dissemination of anonymized streaming data.
Sylvain Barde. (2014) Back to the Future: Economic Self-Organisation and Maximum Entropy Prediction. Computational Economics 45:2, pages 337-358.
Crossref
Youxin Xia, Chao Gao & JinLong Li. 2015. Bio-Inspired Computing -- Theories and Applications. Bio-Inspired Computing -- Theories and Applications 513 522 .
Skander Htiouech & Sadok Bouamama. (2014) A Lagrangian and surrogate information enhanced tabu search for the MMKP. A Lagrangian and surrogate information enhanced tabu search for the MMKP.
Alejandra Duenas, Christine Di Martinelly & G. Yazgı Tütüncü. 2014. Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications. Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications 539 546 .
Hamid Shojaei, Twan Basten, Marc Geilen & Azadeh Davoodi. (2013) A fast and scalable multidimensional multiple-choice knapsack heuristic. ACM Transactions on Design Automation of Electronic Systems 18:4, pages 1-32.
Crossref
Eileen A. Bjorkman, Shahram Sarkani & Thomas A. Mazzuchi. (2013) Test and Evaluation Resource Allocation Using Uncertainty Reduction. IEEE Transactions on Engineering Management 60:3, pages 541-551.
Crossref
Skander Htiouech, Sadok Bouamama & Rabeh Attia. (2013) Using surrogate information to solve the multidimensional multi-choice knapsack problem. Using surrogate information to solve the multidimensional multi-choice knapsack problem.
Kaveh Khalili-Damghani, Majid Nojavan & Madjid Tavana. (2013) Solving fuzzy Multidimensional Multiple-Choice Knapsack Problems: The multi-start Partial Bound Enumeration method versus the efficient epsilon-constraint method. Applied Soft Computing 13:4, pages 1627-1638.
Crossref
Vincent C. Li, Yun-Chia Liang & Huan-Fu Chang. (2012) Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method. Computers & Operations Research 39:9, pages 2111-2121.
Crossref
Boaz Patt-Shamir & Dror Rawitz. (2012) Vector bin packing with multiple-choice. Discrete Applied Mathematics 160:10-11, pages 1591-1600.
Crossref
Shahaf I. Wayer & Arie Reichman. (2012) Resource Management in Satellite Communication Systems: Heuristic Schemes and Algorithms. Journal of Electrical and Computer Engineering 2012, pages 1-10.
Crossref
Zhi-gang Ren, Zu-ren Feng & Ai-min Zhang. (2012) Fusing ant colony optimization with Lagrangian relaxation for the multiple-choice multidimensional knapsack problem. Information Sciences 182:1, pages 15-29.
Crossref
Igor Crévits, Saïd Hanafi, Raïd Mansi & Christophe Wilbaut. (2012) Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem. Computers & Operations Research 39:1, pages 32-41.
Crossref
Victor Boskamp, Alex Knoops, Flavius Frasincar & Adriana Gabor. (2011) Maximizing revenue with allocation of multiple advertisements on a Web banner. Computers & Operations Research 38:10, pages 1412-1424.
Crossref
Brian Dougherty, Jules White & Douglas Schmidt. (2011) Automated software and hardware evolution analysis for distributed real-time and embedded systems. Open Computer Science 1:1.
Crossref
S. Raja Balachandar & K. Kannan. (2011) A Heuristic Algorithm for Resource Allocation/Reallocation Problem. Journal of Applied Mathematics 2011, pages 1-11.
Crossref
Mark Sh. Levin, Aliaksei Andrushevich & Alexander Klapproth. 2011. Modern Approaches in Applied Intelligence. Modern Approaches in Applied Intelligence 459 468 .
James J. Cochran, Louis A. CoxJr.Jr., Pinar Keskinocak, Jeffrey P. Kharoufeh & J. Cole SmithChristos Voudouris, Edward P. K. Tsang & Abdullah Alsheddy. 2011. Wiley Encyclopedia of Operations Research and Management Science. Wiley Encyclopedia of Operations Research and Management Science.
Shahrear Iqbal, Md. Faizul Bari & M. Sohel Rahman. (2010) A novel ACO technique for fast and near optimal solutions for the Multi-dimensional Multi-choice Knapsack Problem. A novel ACO technique for fast and near optimal solutions for the Multi-dimensional Multi-choice Knapsack Problem.
Shahaf I. Wayer & Arie Reichman. (2010) Resource management in satellite communication systems — Heuristic algorithms. Resource management in satellite communication systems — Heuristic algorithms.
Hiram Galeana-Zapien & Ramon Ferrus. (2010) Design and Evaluation of a Backhaul-Aware Base Station Assignment Algorithm for OFDMA-Based Cellular Networks. IEEE Transactions on Wireless Communications 9:10, pages 3226-3237.
Crossref
Zhigang Ren & Zuren Feng. (2010) An ant colony optimization approach to the multiple-choice multidimensional knapsack problem. An ant colony optimization approach to the multiple-choice multidimensional knapsack problem.
N. Cherfi & M. Hifi. (2008) A column generation method for the multiple-choice multi-dimensional knapsack problem. Computational Optimization and Applications 46:1, pages 51-73.
Crossref
Bing Han, Jimmy Leblet & Gwendal Simon. (2010) Hard multidimensional multiple choice knapsack problems, an empirical study. Computers & Operations Research 37:1, pages 172-181.
Crossref
Qian Zhou & Wenjian Luo. 2010. Advances in Computation and Intelligence. Advances in Computation and Intelligence 148 157 .
Shahrear Iqbal, Md. Faizul Bari & M. Sohel Rahman. 2010. Swarm Intelligence. Swarm Intelligence 312 323 .
Boaz Patt-Shamir & Dror Rawitz. 2010. Algorithm Theory - SWAT 2010. Algorithm Theory - SWAT 2010 248 259 .
Christos Voudouris, Edward P.K. Tsang & Abdullah Alsheddy. 2010. Handbook of Metaheuristics. Handbook of Metaheuristics 321 361 .
Md. Iftakharul Islam & Md. Mostofa Akbar. (2009) Heuristic algorithm of the multiple-choice multidimensional knapsack problem (MMKP) for cluster computing. Heuristic algorithm of the multiple-choice multidimensional knapsack problem (MMKP) for cluster computing.
Brian Dougherty, Jules White, Chris Thompson & Douglas C. Schmidt. (2009) Automating Hardware and Software Evolution Analysis. Automating Hardware and Software Evolution Analysis.
Saïd Hanafi, Raïd Mansi & Christophe Wilbaut. 2009. Hybrid Metaheuristics. Hybrid Metaheuristics 73 83 .
Vincent Van Peteghem & Mario Vanhoucke. 2009. Evolutionary Computation in Combinatorial Optimization. Evolutionary Computation in Combinatorial Optimization 85 96 .
H. Galeana, F. Novillo & R. Ferrus. (2008) A Cost-Based Approach for Base Station Assignment in Mobile Networks with Limited Backhaul Capacity. A Cost-Based Approach for Base Station Assignment in Mobile Networks with Limited Backhaul Capacity.
A.M. Otebolaku, J.S. Iyilade & M.O. Adigun. (2008) CAAM: A Context Aware Adaptation Model for Mobile Grid Service Infrastructure. CAAM: A Context Aware Adaptation Model for Mobile Grid Service Infrastructure.
Abu Zafar M. Shahriar, M. Mostofa Akbar, M. Sohel Rahman & Muhammad Abdul Hakim Newton. (2007) A multiprocessor based heuristic for multi-dimensional multiple-choice knapsack problem. The Journal of Supercomputing 43:3, pages 257-280.
Crossref
Bing Han & Gwendal Simon. 2009. Distributed Computing and Networking. Distributed Computing and Networking 294 305 .
Maria Chantzara & Miltiades Anagnostou. (2007) User‐sensitive and quality‐driven discovery of context information for the successful delivery of context‐aware services. International Journal of Pervasive Computing and Communications 2:3, pages 219-228.
Crossref
Abdelkader Sbihi. (2006) A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem. Journal of Combinatorial Optimization 13:4, pages 337-351.
Crossref
M. Hifi, M. Michrafy & A. Sbihi. (2005) A Reactive Local Search-Based Algorithm for the Multiple-Choice Multi-Dimensional Knapsack Problem. Computational Optimization and Applications 33:2-3, pages 271-285.
Crossref
M. Chantzara, M. Anagnostou & E. Sykas. (2006) Designing a quality-aware discovery mechanism for acquiring context information. Designing a quality-aware discovery mechanism for acquiring context information.
Maria Chantzara & Miltiades Anagnostou. 2006. Computational Science – ICCS 2006. Computational Science – ICCS 2006 579 587 .
Maria Chantzara & Miltiades Anagnostou. 2006. Modeling and Retrieval of Context. Modeling and Retrieval of Context 101 117 .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.