A New Knapsack Solution Approach by Integer Equivalent Aggregation and Consistency Determination

Djangir A. Babayev, Fred Glover, Jennifer Ryan

INFORMS Journal on Computing · 1997 · Volume 9 · Issue 1

Abstract

We present a new and highly efficient algorithm for the integer knapsack problem based on a special strategy for aggregating integer-valued equations. Employing a new theorem for creating a single equation with the same nonnegative integer solution set as a system of original equations, we transform the integer knapsack problem into an equivalent problem of determining the consistency of an aggregated equation for a parameterized right hand side. This last problem is solved by a newly developed algorithm with complexity O (min( n α 1 , n + α 1 2 )), where n is the number of variables and α 1 is the smallest coefficient in the aggregated equation. Empirical outcomes show our procedure is significantly superior to advanced branch-and-bound methods (previously established to be the most efficient knapsack solution procedures), obtaining solutions several orders of magnitude faster for hard problems.

Keywords

programming, integer, algorithms, theory, mathematics, combinatorics, equivalent aggregation of integer valued equations, testing the consistency of a linear equation in integer variables

Enable JavaScript for citation tools and additional paper interactions.