Knapsack problem

Let us consider a trivial model for capital budgeting decisions. We must allocate a given budget B of money to a set of N potential investments. For each investment opportunity, we know

• The initial capital outlay c_i, i = 1, …, n
• The profit π_i that we will get from the investment (which we assume to be certain)

We would like to select the subset of investments that yields the highest total profit, subject to a limited budget B. This looks like a portfolio optimization model; the key difference is that our decision must be “all or nothing.” For each investment opportunity we may decide whether we take it or leave it, but we cannot “buy” a fractional share of it. In typical portfolio optimization models, assets are assumed to be infinitely divisible, which may often be a reasonable approximation, e.g., for stocks, but not in this case. It may be helpful to think of our investments as projects that can be started or not.

The decision variables must reflect the logical nature of our decision. This is obtained by specifying the following decision variables:

Now it is easy to build an optimization model:

This model is grossly simplified, but it is a first example of an integer programming model; more precisely, it is a pure binary programming problem. It is also well known as the knapsack problem, as each investment may be interpreted as an object of given value π_i and volume c_i, and we want to determine the maximum value subset of objects that fit the knapsack capacity B. A model like this looks deceptively simple. However, it cannot be solved by ordinary optimization methods for continuous models. One could think of simply enumerating all of the feasible solutions, which are a finite set, in order to spot the best one. Unfortunately, this is not feasible in general, as the number of feasible solutions may be very large, even though finite. To see this, notice that there are n variables that can take two values; hence, there are 2ⁿ possible variable assignments. Many of them would be ruled out by the budget constraint, but we see that the computational effort of complete enumeration grows exponentially with the size of the problem. A possible solution approach would be to rank the items in decreasing order of their return π_i/c_i and selecting them until the budget allows. This would work with divisible assets, but it does not guarantee the optimal solution in the discrete case. As a counterexample, let us consider the following problem:

The returns are, respectively, 5.00, 7.00, 4.17, 4.80. Hence, according to this logic we would select investment 2 first, then investment 1, and we would stop there, with profit 17, because no other investment fits the residual budget. This is a really bad solution, leaving much budget unused (4 units out of 7). There are two solutions that exploit the whole budget: [1, 0,0, 1], with total profit 34, and [0, 1,1, 0], with total profit 32. In this trivial case it is easy to see that the first one is optimal.

An important property of the knapsack problem is that if we solve its continuous relaxation, i.e., we relax the integrality requirement x_i ∈ {0, 1} to x_i ∈ [0, 1] and solve the problem as a continuous LP, we obtain a solution with at most one fractional variable. In the case above, [1, 1, 0, 0.8]. It is easy to see that this is the solution we obtain by applying the return-based heuristic above, allowing for a fractional investment in the fourth project, which is the third one in the ranking, in order to saturate the budget. This property can be exploited in ad hoc solution methods for the knapsack problem but, for the sake of generality, we illustrate later how the problem can be solved by general purpose branch and bound methods (see Examples 12.24 and 12.26).

12.4.2 Modeling logical constraints

In the knapsack model, each choice is independent from the other ones, as there is no link whatsoever among different projects. It may be the case that there are additional constraints on subsets of activities, taking into account their mutual relationships and overall requirements. Here are a few examples, where binary decision variables x_j are again related to the decision of starting activity j:

• Exactly one activity within a subset S must start (exclusive OR):
• At least one activity within a subset S must start (inclusive OR):
• At most one activity within a subset S may start:
• If activity j is started, then activity k must start, too:

All the constraints above may be generalized to more complex situations that are relevant, for instance, if you want to enforce qualitative constraints on a portfolio of investments or activities.