Statistical mechanics analysis of the continuous number partitioning problem
Abstract
The number partitioning problem consists of partitioning a sequence of positive numbers {a1,a2,…,aN} into two disjoint sets, A and B, such that the absolute value of the difference of the sums of aj over the two sets is minimized. We use statistical mechanics tools to study analytically the linear programming relaxation of this NP-complete integer programming. In particular, we calculate the probability distribution of the difference between the cardinalities of A and B and show that this difference is not self-averaging.
PACS
- 87.10.+e;
- 64.60.Cn
Keywords
- Number partitioning;
- Linear programming relaxation
1. Introduction
Although most of the statistical mechanics analyses of stochastic versions of combinatorial optimization problems have focused mainly on the calculation of the average cost of the global optima [1], the tools of equilibrium statistical mechanics can also be used to evaluate the average performance of simple heuristics as well as that of relaxed versions of the original problem [2]. In this paper we study both numerically and analytically the linear programming (LP) relaxation of a classical NP-complete integer programming problem, namely, the number partitioning problem [3] and [4].
The number partitioning problem (NPP) is stated as follows [4]. Given a sequence of positive numbers {a1,a2,…,aN}, the NPP consists of partitioning them into two disjoint sets A and B such that the difference




The interest in the NPP stems mainly from the remarkable failure of the stochastic heuristic simulated annealing to find good solutions to it, as compared with the solutions found by deterministic heuristics [5]. The reason for that failure is probably due to the existence of order of 2N local minima whose energies are of order of 1/N [8], which undermines the usual strategy of exploring the space of configurations through single spin flips. It is interesting to note that a very simple deterministic heuristic, the differencing method of Karmarkar and Karp, can find with high probability solutions whose energies are of order of
for some α>0 [6] and [7]. For large N, however, the energies of the solutions found by the differencing method are orders of magnitude higher than those predicted by theoretical analyses, which indicate that the average global optimal energy
is of order of
for unconstrained partitions [4] and [8]. A recent exact calculation of this quantity yielded
[9]. It must be noted that, in contrast with combinatorial problems for which the global optimal energy is extensive [1], for the NPP this energy is not self-averaging [8] and [9] and hence
cannot be viewed as a realization independent minimal energy.
In the LP relaxation we relax the integrality requirement on the Ising variables si so that they become real variables, i.e., si∈(−∞,∞). In order to keep these variables finite we impose a spherical constraint on the norm of the solutions,

Obviously, minimizing the square of the cost (2) with si real but constrained to obey the condition (4) yields a lower bound to the optimal (square) cost of the corresponding integer programming problem. Moreover, a simple gradient descent dynamics suffices to attain those bounds numerically. In fact, using a Lagrangian multiplier to handle the constraint (4) we find that the following dynamics minimizes the NPP energy,


The remainder of this paper is organized as follows. In Section 2 we show that the LP relaxation yields a trivial lower bound (i.e. the LP cost is zero) for unconstrained partitions. That analysis yields, nonetheless, some interesting pieces of information as, for instance, the average energy obtained by clipping (i.e. taking the sign of) the spins of the global optimal configurations of the LP relaxation. The average performance of the clipping heuristic is studied in Section 3, where it is shown that
tends to the average energy of a randomly chosen Ising spin configuration,
. In Section 4 we calculate the probability distribution of the difference between the cardinalities of A and B for the LP global optimal configurations, Pc(m), and show that m is not self-averaging. Finally, in Section 5 we present some concluding remarks.
2. Linear programming relaxation
In the canonical ensemble formalism of the statistical mechanics the average value of the optimal energy for unconstrained partitions is given by











