Cached Iterative Weakening for Optimal Multi-Way Number Partitioning


  • Ethan Schreiber University of California, Los Angeles
  • Richard Korf University of California, Los Angeles



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


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.




How to Cite

Schreiber, E., & Korf, R. (2014). Cached Iterative Weakening for Optimal Multi-Way Number Partitioning. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1).



Main Track: Search and Constraint Satisfaction