In this paper, a new upper bound for the Multiple Knapsack Problem (MKP) is proposed, based on the idea of relaxing MKP to a Bounded Sequential Multiple Knapsack Problem, i.e., a multiple knapsack problem in which item sizes are divisible. Such a relaxation, called sequential relaxation, is obtained by suitably replacing the items of a MKP instance with items with divisible sizes. Experimental results on benchmark instances show that the upper bound is effective, in terms of quality, when the ratio between the number of items and the number of knapsacks is small.

Detti, P. (2021). A new upper bound for the multiple knapsack problem. COMPUTERS & OPERATIONS RESEARCH, 129 [10.1016/j.cor.2021.105210].

A new upper bound for the multiple knapsack problem

Detti P.
2021-01-01

Abstract

In this paper, a new upper bound for the Multiple Knapsack Problem (MKP) is proposed, based on the idea of relaxing MKP to a Bounded Sequential Multiple Knapsack Problem, i.e., a multiple knapsack problem in which item sizes are divisible. Such a relaxation, called sequential relaxation, is obtained by suitably replacing the items of a MKP instance with items with divisible sizes. Experimental results on benchmark instances show that the upper bound is effective, in terms of quality, when the ratio between the number of items and the number of knapsacks is small.
2021
Detti, P. (2021). A new upper bound for the multiple knapsack problem. COMPUTERS & OPERATIONS RESEARCH, 129 [10.1016/j.cor.2021.105210].
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0305054821000022-main.pdf

non disponibili

Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 528.11 kB
Formato Adobe PDF
528.11 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/1128571