# How to generate hard instances for number partitioning?

I am trying to compare the performance of some algorithms for multiway number partitioning. I run them on randm instances that I generate with Python's numpy:

values = np.random.randint(1,1000, 100000)


Then I run the algorithm for partitioning the values into 10 bins. But in all instances that I try, the simple greedy number partitioning algorithm returns an optimal partition (all sums are the same up to 1).

• What is a dataset of large real-world number partitioning problems, that are hard (that is, cannot be solved easily by exhaustive search or by a greedy algorithm)?
• How can one generate such large instances randomly?
• A first idea is to replace the uniform distribution by another distribution, a normal one for example. Second, you can increase the number of bins, so that you end up with about 3 to 5 items in bins Mar 22, 2022 at 16:52
• I don't know if there are standard datasets for the Multiway Number Partitioning Problem, but there are some for the Bin Packing Problem or.dei.unibo.it/library/bpplib from which you could built Multiway Number Partitioning instances Mar 22, 2022 at 16:55
• Seconding the comment by @fontanf about a different distribution, you might also try a mixture distribution, for instance taking part of the sample from a distribution with low mean and another part from a distribution with high mean (and perhaps a lower bound greater than the mean or even max of the first sample).
– prubin
Mar 22, 2022 at 21:43
• Since the 1D bin packing problem is very similar to the number partitioning problem, you may be able to find hard problem sets from that literature. Mar 25, 2022 at 3:50

values = np.random.randint(1,2**48-1, 100)