CODEWITHSUNDEEP
algorithmcomputer-sciencegraph-algorithm
Leopd
Leopd

Reputation: 42767

Solving unbounded knapsack with A*

I'm trying to reconcile two seemingly contradictory ideas:

  1. The unbounded knapsack optimization problem is known to be NP-hard
  2. My colleague and I think we can solve a minor variation on it in polynomial time using A*

Sounds crazy, right? That's what I think!

The variation of the problem is described in terms of a cargo plane that must unload some of its goods in order to reduce its payload to the plane's capacity. So there's a set of items each with a weight and a value, and a target weight which must be unloaded -- optimize the goods to unload so that you have at least W weight removed, and minimize the total value of the goods. Consider the unbounded problem where there are arbitrarily many items available each of N different types.

The proposed solution uses a graph which starts at a node (vertex) representing nothing unloaded. Each unload operation represents an edge, so the graph grows exponentially out from the starting point with every possible combination of goods unloaded. The destination node is a virtual aggregate in that all combinations with total weight >= the target are considered the target node. The total weight unloaded so far gets stored in each node and is used to determine whether the target has been reached or not. The cost of each edge is the value of the item being unloaded. So a shortest-path algorithm such as Dijkstra or A* will find the optimum set of goods.

Dijkstra clearly takes exponential time since it is exploring all possible combinations. But with an admissible heuristic, I think A* should run in polynomial time. And I think the following heuristic should work. For every good, calculate the "specific value" which is the ratio of value to weight. Pick the good with the highest specific value. As a heuristic for a given node, calculate the weight still needed to be unloaded times the maximum specific value. This provides an estimate which is either exactly correct in the case that the target weight can be achieved by an integer number of optimal goods, or in all other cases underestimates the distance (weight) remaining because the actual number of goods would need to be rounded up. So the heuristic is admissible.

I haven't proven runtime complexity in any rigorous way. But the way A* works, it will greedily add items towards the goal, exploring the best options quickly, which intuitively feels like it should run in polynomial time for N. And with a properly admissible heuristic the solution is guaranteed to be optimal.

So what's wrong with this solution? I absolutely do not believe we have found a novel solution to a well-studied problem by applying a well-known algorithm. But this seems like it should work.

Upvotes: 0

Views: 513

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65488

This sounds like the standard branch and bound method for knapsack. It's good when there's variety in the ratios but devolves to exponential-time brute force when the ratios are the same.

Upvotes: 2

Related Questions