Bi-criteria multiple knapsack problem with grouped items

Francisco Castillo-Zunino () and Pinar Keskinocak ()
Additional contact information
Francisco Castillo-Zunino: Georgia Institute of Technology
Pinar Keskinocak: Georgia Institute of Technology

Journal of Heuristics, 2021, vol. 27, issue 5, No 2, 747-789

Abstract: Abstract The multiple knapsack problem with grouped items aims to maximize rewards by assigning groups of items among multiple knapsacks, without exceeding knapsack capacities. Either all items in a group are assigned or none at all. We study the bi-criteria variation of the problem, where capacities can be exceeded and the second objective is to minimize the maximum exceeded knapsack capacity. We propose approximation algorithms that run in pseudo-polynomial time and guarantee that rewards are not less than the optimal solution of the capacity-feasible problem, with a bound on exceeded knapsack capacities. The algorithms have different approximation factors, where no knapsack capacity is exceeded by more than 2, 1, and $$1/2$$ 1 / 2 times the maximum knapsack capacity. The approximation guarantee can be improved to $$1/3$$ 1 / 3 when all knapsack capacities are equal. We also prove that for certain cases, solutions obtained by the approximation algorithms are always optimal—they never exceed knapsack capacities. To obtain capacity-feasible solutions, we propose a binary-search heuristic combined with the approximation algorithms. We test the performance of the algorithms and heuristics in an extensive set of experiments on randomly generated instances and show they are efficient and effective, i.e., they run reasonably fast and generate good quality solutions.

Keywords: Multiple knapsacks; Approximation algorithms; Heuristics; Bi-criteria optimization; Computational study (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-021-09476-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joheur:v:27:y:2021:i:5:d:10.1007_s10732-021-09476-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-021-09476-y

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().