Fast Simple Solutions to the Knapsack Problem

I find it rewarding to look at algorithms that have provable guarantees while also being very simple to implement, debug and maintain. As part of this you may like to read my previous post on solving real-world matching problems fast in practice in KISSing algorithms. In a prior life, I worked in similar vein in solving versions of the Steiner minimum tree problem and the max-cut problem. In this write-up I wanted to talk about a simple observation on Knapsack, another classic discrete algorithms problem that is at the heart of Onera’s models.

Given its relevance to Onera this is very much part of algorithms in the real world. Before introducing the problem itself it is worth talking about P vs NP which is always one of the favorite topics in theoretical computer science discussions.

P vs NP: Broadly speaking, problems in computer science fall under many complexity classes, each of which characterize the hardness of solving a problem. At one end of it are problems so hard that computers will never be able to solve them, called as Undecidable Problems. You can read about some of my personal philosophical thoughts about undecidability and limits of computing. P is the complexity class that modern day computers (no quantum computers needed) can be thought of as solving efficiently and so you will interchangeably hear the term ‘tractable’ for these problems. Harder (more precisely, not easier) than those are problems in NP. NP-Complete is a complexity class that contains a bunch of problems that are all ‘equally’ hard such that in a (essentially, kind-of) Nobel prize winning work, was shown that if you show one of them to be tractable then all of them are tractable. Problems in this believed-to-be-intractable complexity class, include many that are important for us to solve - for example simple characterizations of the protein folding problem. However, we have also leveraged this (possible) gap in tractability in good ways. For example, all of internet security by the way of public key crypto-systems rely on the assumption that there are fundamentally intractable problems in NP-complete but are not in P. If that assumption fails, then the entire fabric of public key crypto-systems fails and the world economy will crash completely (for the computer science folks - no not specifically because of FACTOR but because if P=NP then it can be shown that there are no cryptographic one-way functions).

Knapsack problem: The Knapsack is a classic problem that is NP-complete and in fact was among the first problems shown to be NP-complete in the above mentioned classic computer science paper. It is a problem that every person has faced while packing a bag for vacation. You have I different items, each item i has a value v and size w. You want to pack the set of most valuable items, defined as the sum of all its values, while ensuring that the sum of their sizes do not exceed the size of the knapsack W. This is a deceptively simple problem but if you can write a computer program to solve it fast provably, then you will bring down the world economy.

However in practice this problem comes up all the time. In the case of Onera, at a high-level, the objective of selecting items translates to maximizing our customer’s revenue and the constraint of keeping the total size less than W, translates to ensuring that the customer dissatisfaction is never much. We are not in the business of breaking crypto-systems but we do want to solve such problems in practice. So what do you do?

The good news is that you can solve the knapsack and other related problems incredibly fast in practice. In fact, we could not even devise ways to construct hard instances to solve. Here’s why.

Fast Near Optimal Solutions: Formally, the knapsack problem can be expressed as the above integer linear program. The linear programming relaxation of that integer program just converts 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.

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. In a classical work, it has been shown that all linear programs have an optimal solution that lies at an extreme point, 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 you can imagine any polytope and an objective function as a direction vector. Note that an extreme point in this I-dimensional polytope is defined exactly at 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, you need either I of the boundary constraints each of which corresponding to a unique variable or you 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 a single solve of the linear program relaxation of the integer program using Simplex will give you a solution where all the variables are binary with the exception of at most 1 variable.

This is huge in practice. Let us take an example where, as in the case of Onera’s systems, each variable corresponds to a product that the retailer might carry. Retailers typically carry 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 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. Not constant fraction approximation ratios etc. 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 that 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. If you model the problem you are solving as a knapsack problem, do not immediately worry that it is NP-complete. In fact, be very happy that it is knapsack.
2. You can generalize the above statement beyond the knapsack of course. Specifically when you construct your integer linear programming model, see if you can define it 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 you 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.