Picture of knapsack problem

In my combinatorial optimization class, we had to write a program to solve the {0,1} knapsack problem, and then characterize its performance. I decided to create a picture of the "hardness landscape" of a particular class of knapsack problem (described below) when tackled via branch-and-bound. I want to share the pictures because I found them fascinating.

Here's a birds-eye view of the hardness landscape, zoomed out 100x, where capacity ranges from 0 to 40,000 and number of items ranges from 0 to 30,000.

Here's a close up view of the upper-right corner of the graph where there seems to be the most "static". Capacity ranges from 39,600 to 40,000 and num items ranges from 2000 to 2300.

Each pixel in these graphs represents the time required to find the optimal solution to the problem at that pixel. Black means the solution was found in zero seconds, while white means the solution took more than 0.5 seconds.

Here's the problem structure I used:

randomItems numItems = map mkItem [1..numItems]
    where mkItem n = Item {weight = (n `div` base) + 1,
                           cost = n `mod` base}
          base = round $ sqrt $ fromIntegral numItems

Posted on March 13, 2006 12:22 PM
More school articles