13 - The number partitioning problem

Summary

La pensée n'est qu'un éclair au millieu d'une longue nuit. Mais c'est cet éclair qui est tout.

Henri Poincaré, La valeur de la science.

With the Hopfield model we have seen that the range of applications of statistical mechanics goes beyond standard physics into biology and neuroscience. In recent years, many such extensions have been noted. A particularly lively area is that of combinatorial optimization, notably with applications to computer science. While I cannot cover this subject adequately, I will in this last chapter concentrate on possibly the simplest example, the number partitioning problem. The connection to statistical mechanics has been pointed out by S. Mertens, from whom I learned about this interesting problem.

Number partitioning as a spin-glass problem

The number partitioning problem is a classical optimization problem: Given N numbers n₁, n₂, …, n_N, find a way of distributing them into two groups such that their sums in each group are as similar as possible. One can easily imagine that this problem occurs all the time in real life, albeit with additional complication: Imagine you want to stuff two moving boxes with books of different weights. You clearly have an interest in making both boxes more or less the same weight, so that neither of them is too heavy. In computing, you want to distribute a certain number of jobs on, say, two processors, in such a way that all of your processes are executed in the fastest way, etcClearly, the two examples indicate that the problem has a natural generalization to partitionings into more than two groups. What is needed in practice is an algorithm that, when presented with the N numbers, finds the optimal partitioning as quickly as possible.