Research On Exact Algorithm Of Knapsack Problem With Conflict Graph

The knapsack problem is a classic problem in combinatorial optimization problems.This problem often appears in resource allocation.Decision makers must choose from a set of indivisible projects or tasks within a prescribed time or budget.The knapsack problem has been studied for more than a century,with early works dating as far back as 1897.In the 0-1knapsack problem,given a knapsack with a fixed capacity and a series of items,each item has a profit attribute and a weight attribute,and the goal is to select a number of items to put into the knapsack(each item can only choose at most once)to satisfy that the sum of the weight of all items in the knapsack does not exceed the capacity of the knapsack,and maximize the sum of the profits of all the items in the knapsack.The knapsack problem with conflict graph studied in this paper is an extension of the 0-1knapsack problem.Given a conflict graph,incompatible attributes between items and items are predefined,that is,there are certain items that cannot be put into the knapsack at the same time.The goal of this problem is to maximize the sum of the profits of all items in the knapsack under the premise of satisfying the knapsack capacity constraint and the incompatibility constraint(each item can only choose at most once).Based on previous studies,this paper proposes a new algorithm for calculating the upper bound.The time complexity of the newly proposed algorithm isO(?n~2),where is related to the input.It can be seen that this is a pseudo-polynomial time complexity algorithm.According to literature data,the time complexity of the current latest algorithm isO(n~3).When?<n,the time complexity of the new algorithm proposed in this paper is lower than that of the current latest algorithm.The upper bound algorithm is embedded into the framework of the branch and bound algorithm,and a large number of numerical experiments are carried out.The experimental results show that for the graph with density greater than or equal to 0.1,the branch-and-bound algorithm based on the new algorithm is 1.6458 times faster than the state-of-the-art algorithm on random(the profit of each item is randomly generated)instances.For correlated(the profit of each item is equal to its weight plus 10)instances,the branch-and-bound algorithm based on the new algorithm is 1.6352 times faster than the state-of-the-art algorithm.In addition,the branch and bound algorithm based on the new upper bound algorithm is the fastest for 96.5278%of the random instances and 92.564%of the correlated instances.Moreover,the branch-and-bound algorithm based on the new algorithm can optimally solve more instances than the state-of-the-art algorithm in a given time limit.