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

Sameh Al-Shihabi

European Journal of Operational Research, 2025, vol. 320, issue 3, 496-504

Abstract: 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.

Keywords: Core problem; Multidemand multidimensional knapsack problem; Exact solution; Tabu search; Local-branching (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724006684
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:320:y:2025:i:3:p:496-504

DOI: 10.1016/j.ejor.2024.08.025

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().