Name
Abstract | ||
|---|---|---|
We consider a class of knapsack problems that include setup costs for families of items. An individual item can be loaded into the knapsack only if a setup cost is incurred for the family to which it belongs. A mixed integer programming formulation for the problem is provided along with exact and heuristic solution methods. The exact algorithm uses cross decomposition. The proposed heuristic gives fast and tight bounds. In addition, a Benders decomposition algorithm is presented to solve the continuous relaxation of the problem. This method for solving the continuous relaxation can be used to improve the performance of a branch and bound algorithm for solving the integer problem. Computational performance of the algorithms are reported and compared to CPLEX. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.ejor.2007.07.003 | European Journal of Operational Research |
Keywords | Field | DocType |
Integer programming,Knapsack,Cross decomposition,Benders decomposition | Heuristic,Mathematical optimization,Exact algorithm,Change-making problem,Heuristic (computer science),Continuous knapsack problem,Integer programming,Cutting stock problem,Knapsack problem,Mathematics | Journal |
Volume | Issue | ISSN |
190 | 3 | 0377-2217 |
Citations | PageRank | References |
1 | 0.36 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nezih Altay | 1 | 271 | 14.90 |
| Powell E. Robinson Jr. | 2 | 1 | 0.36 |
| Kurt M. Bretthauer | 3 | 300 | 23.24 |