Multiway Number Partitioning

The multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. The problem is parametrized by a positive integer k, and called k-way number partitioning. There is a special case, called simply the partition problem, in which k = 2. You can often meet the latter in more casual terms, for example, "given a set of integers, divide it into two subsets such that the absolute difference between their sums is minimum" or just "split a set into two equal subsets". Sometimes it is also called "Minimum Sum Partition Problem". The calculator below performs k-way number partitioning using the Complete Greedy Algorithm. If you use k = 2 ("Number of partitions" field) you will be obviously solving minimum sum partition problem. You can read about the algorithm used by the calculator below the calculator.

Multiway Number Partitioning

Integers

Number of partitions

Calculate

Maximum subset difference

 

The file is very large. Browser slowdown may occur during loading and creation.

Download 

 Link  Save  Widget

Multiway Number Partitioning

The number partitioning problem (NPP) can be defined as: Given a list a₁, a₂, ..., aₙ of positive integers, find a partition, that is, a subset A ⊂ { 1, ..., n } minimizing the discrepancy

A perfect partition is a partition with for even, or for odd¹.

The problem was first presented by Ronald Graham in 1969 in the context of the Identical-machines scheduling problem². That's why it is also referred to as the multiprocessor scheduling problem. It has plenty of practical applications, from multiprocessor scheduling to choosing up sides in a ball game. You can think of it as of the fairest possible division into parts. As our site visitor Michela put it asking for this calculator: "For example, a situation that requires this type of calculation arises when it is necessary to do a group presentation work for school or work, and it is necessary to divide a certain number of elements to study (ex. Chapters of a book), each of a given length (ex. number of words), in a given number of parts equal to the members of the group."

The Complete Greedy Algorithm

Number partitioning is the NP-complete problem. Nonetheless, there have been continuous algorithmic improvements leading to multiple orders of magnitude speedup for solving this problem for five decades³.
This calculator uses the Complete Greedy Algorithm as described in the work by Richard E. Korf⁴. It is relatively simplier than the other existing algorithms, but I believe the performance of this algorithm should be enough for any practical problems of the fairest division, which the site visitors will be looking for.

The algorithm belongs to the class of the anytime algorithms. The anytime algorithms find better solutions the longer they are allowed to run. This class of algorithms is sitting in between the complete algorithms that are guaranteed to find an optimal solution eventually, but run in exponential time, and polynomial-time algorithms that only find approximate solutions, with no way of improving their solutions given more running time.

Here is how it works. The obvious greedy heuristic for this problem is to first sort the numbers in decreasing order, and place the largest number in the first empty subset. Then, place each remaining number in the subset with the smaller total sum thus far, until all the numbers are assigned. Of course it does not always find an optimal solution.

To make if complete, we produce a k-ary tree. Thus the leftmost branch at any level is generated by placing the next number in the subset with the smallest sum so far, the next branch is generated by placing it in the next larger subset, and so on. The algorithm performs a deep search along the tree looking for the better solution than the solution achieved so far. Note that the first found solution will be the greedy solution.

There are several techniques to prune the tree, thus reducing the computational time.

First, we should never place a number into more than one empty subset to avoid the generation of duplicate partitions. More general, we should never place a number in two different subsets with the same subset sum

Second, we should use branch-and-bound approach and maintain the smallest difference found so far for a complete partition. Given the largest current subset sum, the best we can do is to bring each of the remaining subset sums up to the value of the largest. To see if this is possible, we add all the numbers not belonging the the largest subset and divide the result by k - 1. If this quotient is less than the largest subset sum, then the difference between them is the best possible final difference we could achieve (it is a perfect solution to a k - 1-way partitioning problem). If the resulting difference is greater than the best complete partition difference found so far, we can prune this branch of the tree, since we cannot find the better solution.

And, finally, we should check any found solution and stop immediately once a perfect partition is found.