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

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 α₁, n + α₁²)), where n is the number of variables and α₁ 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.