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.
展开▼
