INFORMATICA Informatica 0868-4952 0868-4952 VU INFO1098 10.15388/Informatica.2016.93 Research Article Dynamic-Programming-Based Inequalities for the Unbounded Integer Knapsack Problem He Xueqi he0429@ufl.edu * Hartman Joseph C. Pardalos Panos M. Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA Francis College of Engineering, University of Massachusetts Lowell, Lowell, MA 01854, USA Corresponding author. 01 01 2016 27 2 433 450 01 01 2015 01 04 2015 Vilnius University 2016

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.

 integer programming dynamic programming unbounded knapsack problem valid inequalities