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

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

0.00 Avg rating0 Votes
Article ID: iaor19983013
Country: United States
Volume: 9
Issue: 1
Start Page Number: 43
End Page Number: 50
Publication Date: Dec 1997
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: combinatorial analysis
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 + α21)), 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.

Reviews

Required fields are marked *. Your email address will not be published.