A Branch-and-Price Algorithm for the Multiple Knapsack Problem

Olivier Lalonde (), Jean-François Côté () and Bernard Gendron ()
Additional contact information
Olivier Lalonde: Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et le Transport (CIRRELT), Université de Montréal, Montreal, Quebec H3T 1J4, Canada
Jean-François Côté: Département d’Informatique et de Recherche Opérationnelle, Université de Montréal, Montreal, Quebec H3T 1J4, Canada
Bernard Gendron: Université Laval, Quebec, Quebec G1V 0A6, Canada

INFORMS Journal on Computing, 2022, vol. 34, issue 6, 3134-3150

Abstract: The multiple knapsack problem is a well-studied combinatorial optimization problem with several practical and theoretical applications. It consists of packing some subset of n items into m knapsacks such that the total profit of the chosen items is maximum. A new formulation of the problem is presented, where a Lagrangian relaxation is derived, and we prove that it dominates the commonly used relaxations for this problem. We also present a Dantzig-Wolfe decomposition of the new formulation that we solve to optimality using a branch-and-price algorithm, where its main advantage comes from the fact that it is possible to control whether an item is included in some knapsack or not. An improved algorithm for solving the resulting packing subproblems is also introduced. Computational experiments then show that the new approach achieves state-of-the-art results.

Keywords: multiple knapsack problem; branch-and-price; Lagrangian relaxation (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1223 (application/pdf)

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:inm:orijoc:v:34:y:2022:i:6:p:3134-3150

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().