.png){kind=icon}
Return
An exact algorithm for the fixed-charge multiple knapsack problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2007.10.024.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We formulate the fixed-charge multiple knapsack problem (FCMKP) as an extension of the multiple knapsack problem (MKP). The Lagrangian relaxation problem is easily solved, and together with a greedy heuristic we obtain a pair of upper and lower bounds quickly. We make use of these bounds in the pegging test to reduce the problem size. We also present a branch-and-bound (B&B) algorithm to solve FCMKP to optimality. This algorithm exploits the Lagrangian upper bound as well as the pegging result for pruning, and at each terminal subproblem solve MKP exactly by invoking MULKNAP code developed by Pisinger [Pisinger, D., 1999. An exact algorithm for large multiple knapsack problems. European Journal of Operational Research 114, 528-541]. As a result, we are able to solve almost all test problems with up to 32,000 items and 50 knapsacks within a few seconds on an ordinary computing environment, although the algorithm remains some weakness for small instances with relatively many knapsacks. (c) 2007 Elsevier B.V. All rights reserved.
Keywords:
Integer programming
Multiple knapsack problem
Fixed-charge problem
Combinatorial optimization
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
.png){kind=icon}
