The Number Partitioning Problem


Description:The Number Partitioning Problem [GJ79] (NPP) is one of the "sixessential" NPcomplete problems. It can be defined as: Input:A set A of n positive integer numbers {a_{1}, ..., a_{n}}. 

Question:Is there a partition of A, i.e., two disjoint sets A_{1} and A_{2} with A=A_{1} U A_{2}, such that. 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 easyhardeasy 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,10^{M}) 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 [10^{k},10^{k+1}), 0 <= k < M, is .1^{M(k+1)}.9^{1d(k,0)}, where d(i,j) = 1 for i=j, being zero otherwise. A stateoftheart 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 WeightMatching 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):430451, 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. 266272, 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):251291, 1996. 

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