Uncommon Dantzig‐Wolfe Reformulation for the Temporal Knapsack Problem

Uncommon Dantzig‐Wolfe Reformulation for the Temporal Knapsack Problem

0.00 Avg rating0 Votes
Article ID: iaor20134952
Volume: 25
Issue: 3
Start Page Number: 560
End Page Number: 571
Publication Date: Jun 2013
Journal: INFORMS Journal on Computing
Authors: , ,
Keywords: knapsack problem, Dantzig-Wolfe
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.

Reviews

Required fields are marked *. Your email address will not be published.