In a recent blog post, economist Alex Tabarrok sees potential to use quantum annealers for knapsack problems. To an optimizer like me, this seems silly.
Knapsack problems are NP-hard in the worst-case, but are typically very easy in practice. For example, existing integer programming software like Gurobi or CPLEX can quickly solve instances with millions of items. Moreover, they provide exact (“globally optimal”) solutions, which quantum annealers do not ensure.
Here are solve times for some random instances (code here):
items time (sec) 2 0 4 0 8 0 16 0 32 0 64 0 128 0 256 0.35 512 0.41 1024 0.02 2048 0.01 4096 0.03 8192 0.04 16384 0.09 32768 0.17 65536 0.35 131072 0.83 262144 2.05 524288 5.16 1048576 11.58 2097152 25.57 4194304 55.69
Notably, these running times are obtained using a general purpose solver. Specialized exact algorithms can be much faster, see the knapsack algorithms by David Pisinger.
I wonder: what knapsack instances do economists want to solve? Maybe some optimizers can help them out.
Farkas' Dilemma 