Optimal Multi-Way Number Partitioning
The NP-hard number-partitioning problem is to separate a multiset S of
n positive integers into k subsets, such that the largest sum of the
integers assigned to any subset is minimized. The classic application
is scheduling a set of n jobs with different run times onto k
identical machines such that the makespan, the time to complete the
schedule, is minimized. The two-way number-partitioning decision
problem is one of the original 21 problems Richard Karp proved
NP-complete. It is also one of Garey and Johnson's six fundamental
NP-complete problems, and the only one involving numbers.
This thesis explores algorithms for solving multi-way
number-partitioning problems optimally. We explore previously existing
algorithms as well as our own algorithms: sequential number
partitioning (SNP), a branch-and-bound algorithm; binary-search
improved bin completion (BSIBC), a bin-packing algorithm; cached
iterative weakening (CIW), an iterative weakening algorithm; and a
variant of CIW, low cardinality search (LCS). We show experimentally
that for high precision random problem instances, SNP, CIW and LCS are
all state of the art algorithms depending on the values of n and k.
All three outperform previous algorithms by multiple orders of
magnitude in terms of run time.