Name
Abstract | ||
|---|---|---|
We study a natural generalization of the knapsack problem, in which each item exists only for a given time interval. One has to select a subset of the items as in the classical case, guaranteeing that for each time instant, the set of existing selected items has total weight no larger than the knapsack capacity. We focus on the exact solution of the problem, noting that prior to our work, the best method was the straightforward application of a general-purpose solver to the natural integer linear programming formulation. Our results indicate that much better results can be obtained by using the same general-purpose solver to tackle a nonstandard Dantzig-Wolfe reformulation in which subproblems are associated with groups of constraints. This is also interesting because the more natural Dantzig-Wolfe reformulation of single constraints performs extremely poorly in practice. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1287/ijoc.1120.0521 | INFORMS Journal on Computing |
Keywords | Field | DocType |
general-purpose solver,nonstandard dantzig-wolfe reformulation,knapsack problem,natural dantzig-wolfe reformulation,uncommon dantzig-wolfe reformulation,time instant,time interval,natural integer linear programming,natural generalization,temporal knapsack problem,knapsack capacity,best method,column generation | Exact solutions in general relativity,Mathematical optimization,Column generation,Change-making problem,Integer linear programming formulation,Continuous knapsack problem,Cutting stock problem,Knapsack problem,Solver,Mathematics | Journal |
Volume | Issue | ISSN |
25 | 3 | 1091-9856 |
Citations | PageRank | References |
8 | 0.52 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alberto Caprara | 1 | 1729 | 160.76 |
| Fabio Furini | 2 | 104 | 16.85 |
| Enrico Malaguti | 3 | 312 | 21.69 |