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

equation1
Full-size image (<1 K)
is minimized. Alternatively, we can search for the Ising spin configurations Full-size image (<1 K) that minimize the energy or cost function
equation2
Full-size image (<1 K)
where sj=1 if ajA and sj=−1 if ajB. Also of interest is the problem of constrained partitions, in which the difference between the cardinalities of sets A and B is fixed, i.e.,
equation3
Full-size image (<1 K)
so that the cardinality of the largest set is N(1+m)/2. Henceforth, we will restrict our analysis to the case where the aj's are statistically independent random variables uniformly distributed in the unit interval.

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 Full-size image (<1 K) 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 Full-size image (<1 K) 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 Full-size image (<1 K) is of order of Full-size image (<1 K) for unconstrained partitions [4] and [8]. A recent exact calculation of this quantity yielded Full-size image (<1 K)[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 Full-size image (<1 K) 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,

equation4
Full-size image (<1 K)

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,

equation5
Full-size image (<1 K)
where Full-size image (<1 K) and η is an arbitrarily small parameter that determines the step-size of the descent.

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 Full-size image (<1 K) 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 Full-size image (<1 K) tends to the average energy of a randomly chosen Ising spin configuration, Full-size image (<1 K). 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

equation6
Full-size image (<1 K)
where Zu(T) is the partition function
equation7
Full-size image (<1 K)
with Full-size image (<1 K) given by Eq. (2). Here δ(x) is the Dirac delta and T is the temperature. The notation 〈…〉a stands for the average over the random variables ai. The limit T→0 in Eq. (6) ensures that only the states that minimize Full-size image (<1 K) will contribute to Zu. We now proceed with the explicit evaluation of the partition function (7). Using the integral representation of the Dirac delta function we write
equation8
Full-size image (<1 K)
The integrals over sj and Full-size image (<1 K) can easily be performed yielding
equation9
Full-size image (<1 K)
where Full-size image (<1 K). At this stage the integral over ζ can be readily carried out by assuming T→0. The result is simply
equation10
Full-size image (<1 K)
where
equation11
Full-size image (<1 K)
In the limit of large N, the integral over x can be evaluated using the saddle-point method. Noting that the saddle point is the imaginary xs=1/2i, the unconstrained partition function is finally written as
equation12
Full-size image (<1 K)
Since Zu decreases linearly with decreasing T, Eq. (6) yields Full-size image (<1 K). This result was verified numerically using the gradient descent dynamics (5) together with an adaptive prescription to decrease the step-size η during the descent.