Branch and solve strategies-based algorithm for the quadratic multiple knapsack problem

Méziane Aïder, Oussama Gacem and Mhand Hifi

Journal of the Operational Research Society, 2022, vol. 73, issue 3, 540-557

Abstract: Suppose a manager has to assign agents for multiple projects, where each agent has its own budget. The manager knows the salary and productivity of each agent, both individually and in pairs. The goal of the manager is to assign a subset of agents to each project at the same time in such a way that the total productivity, without exceeding the budget of any project, is maximised. This problem can be formulated as a quadratic multiple knapsack, an NP-hard problem. This paper investigates the use of branch and solve strategies in order to solve large-scale quadratic multiple knapsack problems. An enhanced fix and solve solution procedure is developed, which is embedded in the local branching-based method, where the branches reflect intensification and diversification search around a solution. The proposed method is analyzed on a set of benchmark instances taken from the literature and new generated large-scale instances. Its provided solution values are compared to those achieved by more recent algorithms available in the literature and the state-of-the-art exact Cplex solver. The experimental study shows that the method is able to reach new solutions, match several best available solutions and, outperforms the Cplex on the new hardness instances.

Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2020.1843982 (text/html)
Access to full text is restricted to subscribers.

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:taf:tjorxx:v:73:y:2022:i:3:p:540-557

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2020.1843982

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().