Dynamic-Programming-Based Inequalities for the Unbounded Integer Knapsack Problem

Article type: Research Article

Authors: He, Xueqi^{1; *} | Hartman, Joseph C.² | Pardalos, Panos M.¹

Affiliations: [1] Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA. E-mail: [email protected] | [2] Francis College of Engineering, University of Massachusetts Lowell, Lowell, MA 01854, USA

Correspondence: [*] Corresponding author.

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.

Keywords: integer programming, dynamic programming, unbounded knapsack problem, valid inequalities

Journal: Informatica, vol. 27, no. 2, pp. 433-450, 2016