MULKNAP
An exact algorithm for the budget-constrained multiple knapsack problem This paper is concerned with a variant of the multiple knapsack problem (MKP), where knapsacks are available by paying certain `costs’, and we have a fixed budget to buy these knapsacks. Then, the problem is to determine the set of knapsacks to be purchased, as well as to allocate items into the accepted knapsacks in such a way as to maximize the net total profit. We call this the budget-constrained MKP and present a branch-and-bound algorithm to solve this problem to optimality. We employ the Lagrangian relaxation approach to obtain an upper bound. Together with the lower bound obtained by a greedy heuristic, we apply the pegging test to reduce the problem size. Next, in the branch-and-bound framework, we make use of the Lagrangian multipliers obtained above for pruning subproblems, and at each terminal subproblem, we solve MKP exactly by calling the MULKNAP code [{it D. Pisinger}, Eur. J. Oper. Res. 114, No. 3, 528--541 (1999; Zbl 0948.90110)]. Thus, we were able to solve test problems with up to 160,000 items and 150 knapsacks within a few minutes in our computing environment. However, solving instances with relatively large number of knapsacks, when compared to the number of items, still remains hard. This is due to the weakness of MULKNAP to this type of problems, and our algorithm inherits this weakness as well.
Keywords for this software
References in zbMATH (referenced in 35 articles , 1 standard article )
Showing results 1 to 20 of 35.
Sorted by year (- Dell’Amico, Mauro; Delorme, Maxence; Iori, Manuel; Martello, Silvano: Mathematical models and decomposition methods for the multiple knapsack problem (2019)
- Yang, Zhen; Chen, Haoxun; Chu, Feng; Wang, Nengmin: An effective hybrid approach to the two-stage capacitated facility location problem (2019)
- Zhen, Lu; Wang, Kai; Wang, Shuaian; Qu, Xiaobo: Tug scheduling for hinterland barge transport: a branch-and-price approach (2018)
- Fischetti, Matteo; Liberti, Leo; Salvagnin, Domenico; Walsh, Toby: Orbital shrinking: theory and applications (2017)
- Simon, Jay; Apte, Aruna; Regnier, Eva: An application of the multiple knapsack problem: the self-sufficient marine (2017)
- Tönissen, D. D.; van den Akker, J. M.; Hoogeveen, J. A.: Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem (2017)
- Laalaoui, Y.; M’Hallah, R.: A binary multiple knapsack model for single machine scheduling with machine unavailability (2016)
- Qin, Jin; Xu, Xianhao; Wu, Qinghua; Cheng, T. C. E.: Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem (2016)
- Chen, Yuning; Hao, Jin-Kao: Iterated responsive threshold search for the quadratic multiple knapsack problem (2015)
- Kataoka, Seiji; Yamada, Takeo: Upper and lower bounding procedures for the multiple knapsack assignment problem (2014)
- Fortz, B.; Labbé, M.; Louveaux, F.; Poss, M.: Stochastic binary problems with simple penalties for capacity constraints violations (2013)
- Mizutani, Tomohiko; Yamashita, Makoto: Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables (2013)
- Fukunaga, Alex S.: A branch-and-bound algorithm for hard multiple knapsack problems (2011)
- Haksöz, Çağrı; Pinedo, Michael: Economic lot scheduling with resources in parallel (2011)
- Hübner, Alexander: Retail category management. Decision support systems for assortment, shelf space, inventory and price planning. (2011)
- You, Byungjun; Yamada, Takeo: An exact algorithm for the budget-constrained multiple knapsack problem (2011)
- Adewumi, A. O.; Ali, M. M.: A multi-level genetic algorithm for a multi-stage space allocation problem (2010)
- Wang, Zhenbo; Xing, Wenxun: A successive approximation algorithm for the multiple knapsack problem (2009)
- Yamada, Takeo; Takeoka, Takahiro: An exact algorithm for the fixed-charge multiple knapsack problem (2009)
- Fukunaga, Alex S.: Integrating symmetry, dominance, and bound-and-bound in a multiple knapsack solver (2008)