Novel Solutions to the Multidimensional Knapsack Problem Using CPLEX: New Results on ORX Benchmarks - Meriem, Khelifa; Saliha, Mezzoudj; abdelaziz, Hacini Mohammed; Amine, Fenniche Mohammed; Khaled, Babasidi Mohammed (Journal of Ubiquitous Computing and Communication Technologies, 2024)
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.