A new knapsack solution approach by integer equivalent aggregation and consistency determination

The authors 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, they 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 , where n is the number of variables and is the smallest coefficient in the aggregated equation. Empirical outcomes show the present 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.