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.

References in zbMATH (referenced in 27 articles , 1 standard article )

Showing results 1 to 20 of 27.
Sorted by year (citations)

1 2 next

  1. Chen, Yuning; Hao, Jin-Kao: Iterated responsive threshold search for the quadratic multiple knapsack problem (2015)
  2. Kataoka, Seiji; Yamada, Takeo: Upper and lower bounding procedures for the multiple knapsack assignment problem (2014)
  3. Fortz, B.; Labbé, M.; Louveaux, F.; Poss, M.: Stochastic binary problems with simple penalties for capacity constraints violations (2013)
  4. Mizutani, Tomohiko; Yamashita, Makoto: Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables (2013)
  5. Fukunaga, Alex S.: A branch-and-bound algorithm for hard multiple knapsack problems (2011)
  6. Haksöz, Çağrı; Pinedo, Michael: Economic lot scheduling with resources in parallel (2011)
  7. Hübner, Alexander: Retail category management. Decision support systems for assortment, shelf space, inventory and price planning. (2011)
  8. You, Byungjun; Yamada, Takeo: An exact algorithm for the budget-constrained multiple knapsack problem (2011)
  9. Adewumi, A.O.; Ali, M.M.: A multi-level genetic algorithm for a multi-stage space allocation problem (2010)
  10. Wang, Zhenbo; Xing, Wenxun: A successive approximation algorithm for the multiple knapsack problem (2009)
  11. Yamada, Takeo; Takeoka, Takahiro: An exact algorithm for the fixed-charge multiple knapsack problem (2009)
  12. Fukunaga, Alex S.: Integrating symmetry, dominance, and bound-and-bound in a multiple knapsack solver (2008)
  13. Wilbaut, Christophe; Hanafi, Said: A survey of effective heuristics and their application to a variety of knapsack problems (2008)
  14. Ang, James S.K.; Cao, Chengxuan; Ye, Heng-Qing: Model and algorithms for multi-period sea cargo mix problem (2007)
  15. Fukunaga, A.S.; Korf, R.E.: Bin completion algorithms for multicontainer packing, Knapsack, and covering problems (2007)
  16. Wäscher, Gerhard; Haußner, Heike; Schumann, Holger: An improved typology of cutting and packing problems (2007)
  17. Crauwels, H.A.J.; Beullens, P.; van Oudheusden, D.: Parallel machine scheduling by family batching with sequence-independent set-up times (2006)
  18. Dahl, Geir; Foldnes, Njål: LP based heuristics for the multiple knapsack problem with assignment restrictions (2006)
  19. Ahuja, Ravindra K.; Cunha, Claudio B.: Very large-scale neighborhood search for the $K$-constraint multiple knapsack problem (2005)
  20. Hifi, Mhand; Mhalla, Hedi; Sadfi, Slim: Sensitivity of the optimum to perturbations of the profit or weight of an item in the binary Knapsack problem (2005)

1 2 next