TY - JOUR
T1 - Mathematical models and decomposition methods for the multiple knapsack problem
AU - Dell'Amico, Mauro
AU - Delorme, Maxence
AU - Iori, Manuel
AU - Martello, Silvano
N1 - Funding Information:
Research supported by MIUR-Italy (Grant PRIN 2015, Nonlinear and Combinatorial Aspects of Complex Networks ) and by Air Force Office of Scientific Research (under award number FA9550-17-1-0067 ). We thank three anonymous referees for helpful comments.
Publisher Copyright:
© 2018 Elsevier B.V.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.
PY - 2019/5/1
Y1 - 2019/5/1
N2 - We consider the multiple knapsack problem, that calls for the optimal assignment of a set of items, each having a profit and a weight, to a set of knapsacks, each having a maximum capacity. The problem has relevant managerial implications and is known to be very difficult to solve in practice for instances of realistic size. We review the main results from the literature, including a classical mathematical model and a number of improvement techniques. We then present two new pseudo-polynomial formulations, together with specifically tailored decomposition algorithms to tackle the practical difficulty of the problem. Extensive computational experiments show the effectiveness of the proposed approaches.
AB - We consider the multiple knapsack problem, that calls for the optimal assignment of a set of items, each having a profit and a weight, to a set of knapsacks, each having a maximum capacity. The problem has relevant managerial implications and is known to be very difficult to solve in practice for instances of realistic size. We review the main results from the literature, including a classical mathematical model and a number of improvement techniques. We then present two new pseudo-polynomial formulations, together with specifically tailored decomposition algorithms to tackle the practical difficulty of the problem. Extensive computational experiments show the effectiveness of the proposed approaches.
KW - Combinatorial optimization
KW - Decomposition methods
KW - Exact algorithms
KW - Multiple knapsack problem
KW - Pseudo-polynomial formulations
UR - http://www.scopus.com/inward/record.url?scp=85056693047&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2018.10.043
DO - 10.1016/j.ejor.2018.10.043
M3 - Article
AN - SCOPUS:85056693047
VL - 274
SP - 886
EP - 899
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 3
ER -