Treffer: An optimization framework for solving large scale multidemand multidimensional knapsack problem instances employing a novel core identification heuristic.

By applying the core concept to solve a binary integer program (BIP), certain variables of the BIP are fixed to their anticipated values in the optimal solution. In contrast, the remaining variables, called core variables, are used to construct and solve a core problem (CP) instead of the BIP. A new approach for identifying CP utilizing a local branching (LB) alike constraint is presented in this article. By including the LB-like constraint in the linear programming relaxation of the BIP, this method transfers batches of variables to the set of core variables by analyzing changes to their reduced costs. This approach is sensitive to problem hardness because more variables are moved to the core set for hard problems compared to easy ones. This novel core identification approach is embedded in a multi-stage framework to solve the multidemand, multidimensional knapsack problems (MDMKP), where at each stage, more variables are added to the previous stage CP. The default branch and bound of CPLEX20.10 is used to solve the first stage, and a tabu search algorithm is used to solve subsequent stages until all variables are added to CP in the last stage. The new framework has shown equivalent to superior results compared to the state-of-the-art algorithms in solving large MDMKP instances having 500 and 1,000 variables. • New core identification approach that is sensitive to problem hardness. • A multi-stage optimization framework to solve large MDMKP instances. • A new set of large scale MDMKP instances that are made public. • New best solutions fond for a set of classical MDMKP instances. • A short review and discussion about core identification algorithms. [ABSTRACT FROM AUTHOR]

Copyright of European Journal of Operational Research is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)