AAAI Publications, Twenty-Eighth AAAI Conference on Artificial Intelligence

Font Size: 
Cached Iterative Weakening for Optimal Multi-Way Number Partitioning
Ethan L Schreiber, Richard E Korf

Last modified: 2014-06-21

Abstract


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. We present a new algorithm, cached iterative weakening (CIW), for solving this problem optimally. It incorporates three ideas distinct from the previous state of the art: it explores the search space using iterative weakening instead of branch and bound; generates feasible subsets once and caches them instead of at each node of the search tree; and explores subsets in cardinality order instead of an arbitrary order. The previous state of the art is represented by three different algorithms depending on the values of n and k. We provide one algorithm which outperforms all previous algorithms for k >= 4. Our run times are up to two orders of magnitude faster.

Keywords


Heuristic Search and Optimization; Heuristic Search; Optimization; Search (General/Other)

Full Text: PDF