2
$\begingroup$

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?
Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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 $\endgroup$
    – fontanf
    Mar 22, 2022 at 16:52
  • $\begingroup$ 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 $\endgroup$
    – fontanf
    Mar 22, 2022 at 16:55
  • $\begingroup$ 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). $\endgroup$
    – prubin ♦
    Mar 22, 2022 at 21:43
  • $\begingroup$ 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. $\endgroup$
    – batwing
    Mar 25, 2022 at 3:50

1 Answer 1

Reset to default
1
$\begingroup$

In "Optimal Multi-Way Number Partitioning" (Schreiber, Korf and Moffitt, JACM 2018) the authors present experiments with random integers with 16, 32 and 48 bits. 16 bit integers are relatively easy, since most random instances have a perfect partition. 32 bit integers are harder, and with 48 bit integers, almost all instances do not have a perfect partition. So, to generate hard instances for number partitioning, one can simply increase the number of bits (and then, even instances with 100 integers are already hard):

values = np.random.randint(1,2**48-1, 100)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.