In the multidimensional multiple choice knapsack problem (MMKP), items with nonnegative profits are partitioned into groups. Each item consumes a predefined nonnegative amount of a set of resources with given availability. The problem looks for a subset of items consisting of exactly one item for each group that maximizes the overall profit without violating the resource constraints. The MMKP is among the most complex problems in the knapsack family. In the literature, although a plethora of heuristic approaches have been proposed, very few exact methods can be found, and all of them work only on limited size instances. In this paper, we propose a new exact approach to the problem. The method exactly solves subproblems of increasing size by means of a recursive variable-fixing process until an optimality condition is satisfied. The algorithm has several properties. Memory requirement remains almost constant during computation, and the method is general enough to be easily adapted to other knapsack problems. Finally, it can be converted at no cost into a heuristic approach. We close to optimality 10 open benchmark instances and improve the best-known values for many of the remaining ones. Interesting enough, our algorithm is able to find, within three minutes, better solutions than the ones found by Gurobi in one hour.

A Core-Based Exact Algorithm for the Multidimensional Multiple Choice Knapsack Problem

Renata Mansini;Roberto Zanotti
2020-01-01

Abstract

In the multidimensional multiple choice knapsack problem (MMKP), items with nonnegative profits are partitioned into groups. Each item consumes a predefined nonnegative amount of a set of resources with given availability. The problem looks for a subset of items consisting of exactly one item for each group that maximizes the overall profit without violating the resource constraints. The MMKP is among the most complex problems in the knapsack family. In the literature, although a plethora of heuristic approaches have been proposed, very few exact methods can be found, and all of them work only on limited size instances. In this paper, we propose a new exact approach to the problem. The method exactly solves subproblems of increasing size by means of a recursive variable-fixing process until an optimality condition is satisfied. The algorithm has several properties. Memory requirement remains almost constant during computation, and the method is general enough to be easily adapted to other knapsack problems. Finally, it can be converted at no cost into a heuristic approach. We close to optimality 10 open benchmark instances and improve the best-known values for many of the remaining ones. Interesting enough, our algorithm is able to find, within three minutes, better solutions than the ones found by Gurobi in one hour.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11379/521133
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 9
social impact