Dynamic-Programming-Based Inequalities for the Unbounded Integer Knapsack Problem
Volume 27, Issue 2 (2016), pp. 433–450
Pub. online: 1 January 2016
Type: Research Article
Received
1 January 2015
1 January 2015
Accepted
1 April 2015
1 April 2015
Published
1 January 2016
1 January 2016
Abstract
We propose a new hybrid approach to solve the unbounded integer knapsack problem (UKP), where valid inequalities are generated based on intermediate solutions of an equivalent forward dynamic programming formulation. These inequalities help tighten the initial LP relaxation of the UKP, and therefore improve the overall computational efficiency. We also extended this approach to solve the multi-dimensional unbounded knapsack problem (d-UKP). Computational results demonstrate the effectiveness of our approach on both problems.