The Number Partitioning Problem

 

Description:

      The Number Partitioning Problem [GJ79] (NPP) is one of the "six-essential" NP-complete problems. It can be defined as:

     Input:

           A set A of n positive integer numbers {a1, ..., an}.

 

     Question:

           Is there a partition of A, i.e., two disjoint sets A1 and A2 with A=A1 U A2, such that
?
           Associated to this problem there is a combinatorial optimization problem that can be formulated as the task of finding a set y={v1, ..., vn}, where vi can be either 1 or -1, such that y minimizes the following objective function [RNMS96]:

.

Click here to get the figure in eps format.

Problem Instances:

      In order to define an instance of this problem we need to provide the value of A (the set of numbers to be partitioned). There are no public datasets for this problem. In order to generate a random instance, it must be taken into account the existance of an easy-hard-easy phase transition [Korf95]. Thus, the hardest instances are located at precise combinations of n (the number of elements in A) and M (the number of digits of each number in A) [GW98]. Furthermore, it can be shown that numbers cannot be picked uniformly at random from (0,10M) since spurious correlations are likely to appear [BCM03]. The authors of this latter work indicate hard instances are obtained when the probability of a number being in the interval [10k,10k+1), 0 <= k < M, is .1M-(k+1).91-d(k,0), where d(i,j) = 1 for i=j, being zero otherwise. A state-of-the-art memetic algorithm for solving this problem is also described in that work.

Related Papers:

[BCM03] R. Berretta, C. Cotta, and P. Moscato. “Enhancing the Performance of Memetic Algorithms using Weight-Matching Recombination: Results on the Number Partitioning Problem”. Metaheuristics: Computer Decision Making, M. Resende, J. de Sousa (eds.), Kluwer Academic Publishers, 2003.

[GJ79] M.R. Garey and D.S. Johnson. “Computers and Intractability”. W.H. Freeman and Co., 1979.

[GW98] I. Gent and T. Walsh.“ Analysis of heuristics for number partitioning”. Computational Intelligence 14(3):430-451, 1998

[Korf95] R. Korf. “ From Approximate to Optimal Solutions: a case study of Number Partitioning”. Proceedings of the 14th Joint Conference on Artificial Intelligence, C.S. Mellish (ed.), pp. 266-272, Morgan Kaufmann, 1995

[RMNS96] W. Ruml, J.T. Ngo, J. Marks, and S. Shieber. “Easily Searched Encodings for Number Partitioning”. Journal of Optimization Theory and Applications 89(2):251-291, 1996.

Last Updated: 4/2/03                                                                               For any question or suggestion, click here to contact with us.