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. 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. |
||||