Solving the Revenue Optimization Knapsack Problem in Practice

Recall that, as mentioned in the previous post, Onera can cast the problem of optimizing revenue without degrading customer experience as the following knapsack problem. Specifically, we have the following problem formulation:

In the above formulation, the retailer sells a set of items I. Each item i in I, has value v(i) which is the expected revenue (or margin) that the retailer makes if they sell that item and corresponding to that there is w(i) which is the expected number of dissatisfied customers (the size of the item in the knapsack problem). The problem asks for us to maximize the total expected revenue while ensuring that the total customer dissatisfaction remains below threshold W.

The knapsack problem as stated above is expressed as an integer linear program. Specifically, note that the variables x can only take on a value of either a 0 or a 1. If we hypothetically assume that we can include an item into the knapsack fractionally (nonsensical in the real-world when filling a knapsack made of rigid items), then we obtain what is called as a linear programming relaxation of the integer program. In the linear programming relaxation we just convert the variables x from being binary in {0, 1} to a real number in [0, 1]. The linear programming relaxation is a problem that is in P while the above integer linear program is a problem that is NP-complete like mentioned before. This should make intuitive sense since if I can fit an item fractionally, then I should be able to fill the knapsack up fully and it makes the problem a whole lot easier.

Notice that there are I variables, I constraints that ensure that the variables are all binary (or 2I constraints in the relaxation enforcing that x is in [0, 1]) and a single constraint that enforces that the sum of the sizes of the items selected is at most W. We will call that single constraint as the knapsack constraint and the remaining 2I constraints as binary boundary constraints. In this problem, the 2I + 1 constraints each are I-dimensional hyperplanes each of which enforce feasibility on one side. These constraints together, using their intersections, define an I-dimensional polytope within which lie all feasible solutions to the knapsack problem. The points outside the polytope are those that violate at least one of the above set of constraints.

In a classical work, it has been shown that all linear programs have an optimal solution that lies at an extreme point. Think of an extreme point as just a generalization of a vertex, for example a point at the intersection of a polygon, such as the three points of a triangle or 4 points of a square.

The solution at the extreme point is called as the basic feasible solution, which was the defining concept used in Simplex, one of the big results in computer science history to solve linear programs fast in practice. It is fairly intuitive to see this if one can imagine any polygon and an objective function as a direction vector.

We now examine these extreme points of the knapsack polytope (again the linear relaxation) to find a beautiful structure that helps us solve them extremely fast. Note that an extreme point in this I-dimensional polytope is defined exactly as the intersection of I-linearly independent I-dimensional hyperplanes. Consider any such extreme point in the knapsack problem’s polytope. To get I-linearly independent hyperplanes, we need either I of the boundary constraints each of which corresponding to a unique variable or we have I-1 linearly independent boundary constraints each of which corresponding to a unique variable and the 1 knapsack constraint. In the former case, the extreme point would simply be defined by planes each of which enforce that the variable is binary (in {0, 1}) but not in between. In the latter case, we have I-1 variables set to 0 or 1 and possibly one variable, corresponding to the only variable that was not part of the I boundary constraints but part of the knapsack constraint have a fractional value in (0, 1).

This implies that when we solve the linear program relaxation of the integer program using Simplex, it will give us a solution where all the variables are binary with the exception of at most 1 variable.

This has huge significance in practice. Let us take an example where, as in the case of Onera’s systems, each variable corresponds to an item that the retailer might carry. Retailers typically carry and sell millions of products and so this program contains millions of variables. In one quick solve of the linear program relaxation, we get a solution where all but at most one variable is integral. Said another way, we actually have the optimal solution if you ignore only that single product in the entire catalog of products that the retailer carries. Indeed, the effect of that is so small that it only takes in practice a few more branch-and-bound relaxations to find the true optimality but even otherwise, the solution is incredibly close to optimal straight away by solving a problem in P. The chances are that if you have a million products you can argue that your solution will be instantly about 99.99% accurate by solving this relaxation. The 0.01% is definitely not going to be the problem in your models in practice.

Take Aways. What does this all mean? Here are some simple, handy observations:

1. When the problem you are solving can be modeled as a knapsack problem, do not immediately worry that it is NP-complete. In fact, we can be happy that it is knapsack.
2. One can generalize the above statement beyond the knapsack of course. Specifically when constructing the integer linear programming model, see if it can be defined with just a few non-boundary constraints. The number of those constraints is an upper bound on the number of fractional variables in the linear programming relaxation. The fewer that those are, the faster and closer to optimal solution one can get.

Side note: Although you can essentially always solve the knapsack very fast in practice, it is still very much NP-complete and the ‘fast in practice’ does not translate to other NP-complete problems like the k-clique or Steiner minimum tree which are not only NP-complete but are also hard to solve in practice. These things also do not make a dent on complexity classes and so things like public key encryption remain unaffected.