Novel Solutions to the Multidimensional Knapsack Problem Using CPLEX: New Results on ORX Benchmarks
背包问题
计算机科学
数学优化
算法
数学
作者
Khelifa Meriem,Mezzoudj Saliha,Hacini Mohammed abdelaziz,Fenniche Mohammed Amine,Babasidi Mohammed Khaled
出处
期刊:Journal of Ubiquitous Computing and Communication Technologies [Inventive Research Organization] 日期:2024-09-01卷期号:6 (3): 294-310被引量:1
标识
DOI:10.36548/jucct.2024.3.007
摘要
The Multidimensional Knapsack Problem (MKP) is a challenging combinatorial optimization problem that extends the classical knapsack problem by introducing multiple capacity constraints across various dimensions. This problem has significant practical applications, including resource allocation in supply chain management, portfolio optimization in finance, and cargo loading in logistics, where the goal is to maximize the total profit of selected items while adhering to these constraints. In this research, the CPLEX solver was applied to address the MKP using a set of complex instances from the OR-Library, specifically the ORX Benchmarks. The study focuses on 270 MKP instances characterized by varying numbers of variables (n = 100, 250, 500), constraints (m = 5), and tightness ratios (α = 0.25). Through advanced CPLEX techniques, new results were successfully obtained by employing advanced CPLEX methods, contributing to the existing literature, and setting new benchmarks for these instances.