Knapsack Problem

JavaTools provides a very efficient method for solving the knapsack problem exactly. The method is guaranteed to produce an optimal solution, not just a heuristic solution (the solution is not necessarily unique, there can in theory be multiple solutions). Note that the general knapsack problem is NP-complex as well as NP-complete.

Applicability

A hiker has a backpack with limited capacity. He/she wishes to include the items that provide maximum utility/value that “fit” within the capacity constraint of the backpack. In other words, the objective is to max out the capacity with items that provide maximum utility value, but the “weights” of the items cannot total more than what he/she can carry on that trip. The knapsack problem is one of the most basic, fundamental problems in combinatorial optimization, opening many avenues for problem solving by means of problem reduction. In the science of combinatorial optimization the knapsack problem is considered BASIC and FUNDAMENTAL. For the practitioner, the knapsack problem allows the modelling of many applied tasks, ranging from capital budgeting over cargo loading to cutting stock. Simply consider a freight airplane or an ocean tanker that can carry only a fixed amount of weight or volume, but the carrier wants to maximize the “bang for the buck”, and can pick-and-choose which items to carry and which items to leave at home. Or consider an investor who has a fixed amount of capital and wants to allocate all or part of his/her capital to various investment alternatives, where every investment alternative requires a certain amount of capital knapsack_1.gif to be deposited, and promises a return or profit of knapsack_2.gif. It is obvious that the knapsack solution of that problem is the optimal investment decision.

Example

For a simple introductory example we assume the following data:

Utility values: item 1, 40, item 2, 15, item 3, 20, item 4, 10

Costs/weights: item 1, 4, item 2, 2, item 3, 3, item 4, 1

Capacity: 6

knapsack_3.gif

knapsack_4.gif

This means items 1 and 2 should be included in the hike, yielding a utility value of 55 (40+15), and all other items should be excluded. We can see clearly that this solution is optimal: Items 1 and 2 have costs of 4 and 2, which total 6, which is the capacity restriction. If we tried to “max out” the 6 with other combinations of items, for example picking items 2, 3, and 4 (with costs 2+3+1=6), we’d only get 15+20+10, or 45, as utility value. Picking items 1 and 2 is better, they provide a greater utility value.

In the following example we generate random data to show the performance for large problems.

knapsack_5.gif

knapsack_6.gif

knapsack_7.gif

knapsack_8.gif

knapsack_9.gif

knapsack_10.gif

knapsack_11.gif

knapsack_12.gif

knapsack_13.gif

Note the capacity utilization:

knapsack_14.gif

knapsack_15.gif

which maxes out, but does not violate, the capacity restriction. The slack is capacity minus total costs, or

knapsack_16.gif

knapsack_17.gif

or 0 slack.

The total=maximum utility possibly attainable with that capacity restriction is

knapsack_18.gif

knapsack_19.gif

That means a) in some 10 seconds we determined that items 12, 36, 48, 67, 71, 83, 90, 102, 136, 147, 200, 237, 336, 403, 413, 429, 444, 478, 487, 490 should be included in the trip, which b) provides maximum utility value possibly attainable (which is 6551), and c) maxes out the capacity restriction, but d) doesn’t violate it, and e) is guaranteed to be optimal (among possibly other optimal solutions), and f) is not just a heuristic solution, but guaranteed optimal, and g) no other solution yields a higher utility total.

Note that for efficiency/speed reasons the JKnapsack[] method in JavaTools only accepts integer data. If you have fractional data, you have to rationalize your data (Mathematica’s function Rationalize[]) and multiply your data with the largest denominator. This is in line with the fact that most high-performance optimization algorithms in combinatorial optimization operate MUCH faster on integer data, and the cost of converting fractional data to integer data is by far inferior to the speed gains obtained by operating only on integer data.

The JKnapsack[] method in JavaTools is very efficient because internally it uses SparseArray[]s for the Mathematica parts and an extremely advanced dynamic programming method for the Java parts to obtain its guaranteed optimal solution.

The author is inviting competing implementations in Mathematica or Java or both for large problems at info@lauschkeconsulting.net to challenge the presented performance claim.

Spikey Created with Wolfram Mathematica 9.0