research-article

Open access

Optimal Multi-Way Number Partitioning

Authors:

Ethan L. Schreiber,

Richard E. Korf,

Michael D. MoffittAuthors Info & Claims

Journal of the ACM (JACM), Volume 65, Issue 4

Article No.: 24, Pages 1 - 61

https://doi.org/10.1145/3184400

Published: 25 July 2018 Publication History

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 runtimes on k identical machines such that the makespan, the elapsed time to complete the schedule, is minimized. The two-way number-partitioning decision problem is one of the original 21 problems that Richard Karp proved NP-complete. It is also one of Garey and Johnson’s six fundamental NP-complete problems and the only one based on numbers.

This article explores algorithms for solving multi-way number-partitioning problems optimally. We explore previous algorithms as well as our own algorithms, which fall into three categories: sequential number partitioning (SNP), a branch-and-bound algorithm; binary-search improved bin completion (BSIBC), a bin-packing algorithm; and cached iterative weakening (CIW), an iterative weakening algorithm. We show experimentally that, for large random numbers, SNP and CIW are state-of-the-art algorithms depending on the values of n and k. Both algorithms outperform the previous state of the art by up to seven orders of magnitude in terms of runtime.

References

[1]

H. B. Amor and J. V. de Carvalho. 2005. Cutting Stock Problems. Springer.

[2]

G. Belov and G. Scheithauer. 2006. A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. European Journal of Operational Research 171, 1, 85--106.

[3]

B. Chen. 2004. Parallel scheduling for early completion. In Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Joseph Y. T. Leung (Ed.). CRC Press, Boca Raton, FL.

[4]

V. Chvatal. 1983. Linear Programming. WH Freeman, San Francisco, CA.

[5]

E. G. Coffman Jr. and J. L. Bruno. 1976. Computer and Job-shop Scheduling Theory. John Wiley 8 Sons, Hoboken, NJ.

[6]

E. G. Coffman Jr, M. R. Garey, and D. S. Johnson. 1978. An application of bin-packing to multiprocessor scheduling. SIAM Journal on Computing 7, 1, 1--17.

Digital Library

[7]

E. G. Coffman Jr, M. R. Garey, and D. S. Johnson. 1997. Approximation algorithms for bin packing: A survey. Approximation Algorithms for NP-Hard Problems, Dorit S. Hochbaum (Ed.). PWS Publishing Co., 46--93.

Digital Library

[8]

G. B. Dantzig and M. N. Thapa. 1997. Linear Programming 1: Introduction. Vol. 1. Springer.

Digital Library

[9]

G. B. Dantzig and M. N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Vol. 1. Springer.

[10]

G. B. Dantzig and P. Wolfe. 1960. Decomposition principle for linear programs. Operations Research 8, 1, 101--111.

Digital Library

[11]

M. Dell’Amico, M. Iori, S. Martello, and M. Monaci. 2008. Heuristic and exact algorithms for the identical parallel machine scheduling problem. INFORMS Journal on Computing 20, 3, 333--344.

Digital Library

[12]

M. Dell’Amico and S. Martello. 1995. Optimal scheduling of tasks on identical parallel processors. ORSA Journal on Computing 7, 2, 191--200.

[13]

G. Dósa. 2007. The tight bound of first fit decreasing bin-packing algorithm is FFD (I) 11/9OPT (I)+ 6/9. In Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. Springer, 1--11.

Digital Library

[14]

S. Eilon and N. Christofides. 1971. The loading problem. Management Science 17, 5, 259--268.

Digital Library

[15]

A. S. Fukunaga and R. E. Korf. 2005. Bin Completion Algorithms for Packing and Knapsack Problems. PhD Dissertation. University of California at Los Angeles.

Digital Library

[16]

A. Fukunaga and R. E. Korf. 2007. Bin completion algorithms for multicontainer packing, knapsack, and covering problems. Journal of Artificial Intelligence Research 28, 393--429.

Digital Library

[17]

M. R. Garey, R. L. Graham, and J. D. Ullman. 1972. Worst-case analysis of memory allocation algorithms. In Proceedings of the 4th Annual ACM Symposium on Theory of Computing. ACM, 143--150.

Digital Library

[18]

M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, CA.

Digital Library

[19]

R. E. Gomory. 1958. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society 64, 5, 275--278.

[20]

R. L. Graham. 1966. Bounds for certain multiprocessing anomalies. Bell System Technical Journal 45, 9, 1563--1581.

[21]

R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Kan. 1979. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics 5, 287--326.

[22]

B. Hayes. 2002. The easiest hard problem. American Scientist 90, 2, 113--117.

[23]

E. Horowitz and S. Sahni. 1974. Computing partitions with applications to the knapsack problem. Journal of the ACM 21, 2, 277--292.

Digital Library

[24]

E. Huang and R. E. Korf. 2009. New improvements in optimal rectangle packing. In IJCAI. 511--516.

Digital Library

[25]

M. Iori and S. Martello. 2008. Scatter search algorithms for identical parallel machine scheduling problems. In Metaheuristics for Scheduling in Industrial and Manufacturing Applications. Springer, 41--59.

[26]

D. S. Johnson. 1973. Near-optimal Bin Packing Algorithms. Ph.D. dissertation. Massachusetts Institute of Technology, Cambridge, MA.

[27]

D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham. 1974. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing 3, 4, 299--325.

Digital Library

[28]

N. Karmarkar and R. M. Karp. 1982. The Differencing Method of Set Partitioning. Computer Science Division (EECS), University of California.

[29]

R. M. Karp. 1972. Reducibility Among Combinatorial Problems. Springer.

[30]

H. Kellerer, U. Pferschy, and D. Pisinger. 2004. Knapsack Problems. Springer.

[31]

R. E. Korf. 1998. A complete anytime algorithm for number partitioning. Artificial Intelligence 106, 2, 181--203.

Digital Library

[32]

R. E. Korf. 2002. A new algorithm for optimal bin packing. In Proceedings of the National Conference on Artificial Intelligence. 731--736.

Digital Library

[33]

R. E. Korf. 2003. An improved algorithm for optimal bin packing. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI’03), Acapulco, Mexico. 1252--1258.

Digital Library

[34]

R. E. Korf. 2009. Multi-way number partitioning. Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI’09), 538--543.

Digital Library

[35]

R. E. Korf. 2011. A hybrid recursive multi-way number partitioning algorithm. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI’11), Barcelona, Catalonia, Spain. 591--596.

Digital Library

[36]

R. E. Korf and E. L. Schreiber. 2013. Optimally scheduling small numbers of identical parallel machines. In 23rd International Conference on Automated Planning and Scheduling.

Digital Library

[37]

R. E. Korf, E. L. Schreiber, and M. D. Moffitt. 2014. Optimal sequential multi-way number partitioning. In International Symposium on Artificial Intelligence and Mathematics (ISAIM’14).

[38]

S. Martello and P. Toth. 1990a. Knapsack Problems: Algorithms and Computer Implementations. Chichester: John Wiley 8 Sons, New York, NY.

Digital Library

[39]

S. Martello and P. Toth. 1990b. Lower bounds and reduction procedures for the bin packing problem. Discrete Applied Mathematics 28, 1, 59--70.

Digital Library

[40]

S. Mertens. 2006. The easiest hard problem: Number partitioning. Computational Complexity and Statistical Physics 125, 2, 125--140.

[41]

M. D. Moffitt. 2013. Search strategies for optimal multi-way number partitioning. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence. AAAI Press, 623--629.

Digital Library

[42]

J. L. Mokotoff, E. Jimeno and A. I. Gutiérrez. 2001. List scheduling algorithms to minimize the makespan on identical parallel machines. Top 9, 2, 243--269.

[43]

M. Padberg and G. Rinaldi. 1991. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review 33, 1. 60--100.

Digital Library

[44]

M. L. Pinedo. 2012. Scheduling: Theory, Algorithms, and Systems. Springer.

[45]

F. J. Provost. 1993. Iterative weakening: Optimal and near-optimal policies for the selection of search bias. In AAAI. 749--755.

Digital Library

[46]

V. Sarkar. 1989. Partitioning and Scheduling Parallel Programs for Multiprocessors. MIT Press, Cambridge, MA.

Digital Library

[47]

J. E. Schoenfield. 2002. Fast, exact solution of open bin packing problems without linear programming. Draft, US Army Space 8 Missile Defense Command 45. Technical Report.

[48]

E. L. Schreiber and R. E. Korf. 2013. Improved bin completion for optimal bin packing and number partitioning. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI’13), Beijing, China. AAAI Press, 651--658.

Digital Library

[49]

E. L. Schreiber and R. E. Korf. 2014. Cached iterative weakening for optimal multi-way number partitioning. In Proceedings of the 28th Annual Conference on Artificial Intelligence (AAAI’14), Quebec City, Canada. AAAI Press.

Digital Library

[50]

R. Schroeppel and A. Shamir. 1981. A T=O(2&frac;n2), S=O(2&frac;n4) algorithm for certain NP-complete problems. SIAM Journal of Computing 10, 3, 456--464.

[51]

T. Walsh. 2009. Where are the really hard manipulation problems? The phase transition in manipulating the veto rule. In IJCAI. 324--329.

Digital Library

[52]

B. Yakir. 1996. The differencing algorithm LDM for partitioning: A proof of a conjecture of Karmarkar and Karp. Mathematics of Operations Research 21, 1, 85--99.

Digital Library

[53]

M. Yue. 1991. A simple proof of the inequality FFD (L) 11/9 OPT (L)+ 1, L for the FFD bin-packing algorithm. Acta Mathematicae Applicatae Sinica 7, 4, 321--331.

Cited By

Puccetti G(2024)The Beautiful Art of Rearranging MatricesSSRN Electronic Journal10.2139/ssrn.4818004Online publication date: 2024
https://doi.org/10.2139/ssrn.4818004
Horn RThomson Svan den Berg DAdriaans PLi XHandl J(2024)The Easiest Hard Problem: Now Even EasierProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664099(97-98)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664099
Sidiropoulos NKarakasis PKonar A(2024)Minimizing Low-Rank Models of High-Order Tensors: Hardness, Span, Tight Relaxation, and ApplicationsIEEE Transactions on Signal Processing10.1109/TSP.2023.333806272(129-142)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2023.3338062
Show More Cited By

Index Terms

Optimal Multi-Way Number Partitioning
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Discrete space search
      2. Game tree search

Recommendations

Two metaheuristic approaches for solving multidimensional two-way number partitioning problem

In this paper, we address two metaheuristic approaches, a Variable Neighborhood Search (VNS) and an Electromagnetism-like metaheuristic (EM), on an NP-hard optimization problem: Multi-dimensional Two-way Number Partitioning Problem (MDTWNPP). MDTWNPP is ...
An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem

We present a new iterated greedy algorithm for the permutation flowshop problem under makespan objective.Our algorithm applies local search on partial solutions after the destruction phase.Our algorithm compares favorably with others from the literature ...
Integer linear programming model for multidimensional two-way number partitioning problem

This paper introduces a multidimensional generalization of the two-way number partitioning problem, as well as an integer linear programming formulation of the problem. There are n binary variables and 2p constraints. The numerical experiments are made ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 65, Issue 4

Distributed Computing, Cryptography, Distributed Computing, Cryptography, Coding Theory, Automata Theory, Complexity Theory, Programming Languages, Algorithms, Invited Paper Foreword and Databases

August 2018

307 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3208081

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2018

Accepted: 01 January 2018

Revised: 01 May 2017

Received: 01 August 2016

Published in JACM Volume 65, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

NSF

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
6,028
Total Downloads

Downloads (Last 12 months)785
Downloads (Last 6 weeks)89

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Puccetti G(2024)The Beautiful Art of Rearranging MatricesSSRN Electronic Journal10.2139/ssrn.4818004Online publication date: 2024
https://doi.org/10.2139/ssrn.4818004
Horn RThomson Svan den Berg DAdriaans PLi XHandl J(2024)The Easiest Hard Problem: Now Even EasierProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664099(97-98)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664099
Sidiropoulos NKarakasis PKonar A(2024)Minimizing Low-Rank Models of High-Order Tensors: Hardness, Span, Tight Relaxation, and ApplicationsIEEE Transactions on Signal Processing10.1109/TSP.2023.333806272(129-142)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2023.3338062
Petrovan APop PSabo C(2024)On the Design of Diploid Memetic Algorithms for Solving the Multidimensional Multi-way Number Partitioning ProblemParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_1(3-19)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70055-2_1
Moffitt MAamodt TSwift MJerger N(2023)MiniMalloc: A Lightweight Memory Allocator for Hardware-Accelerated Machine LearningProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 410.1145/3623278.3624752(238-252)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3623278.3624752
Chen WMo ZXu HYe KXu CMohror KArnold DBadia R(2023)Interference-aware Multiplexing for Deep Learning in GPU Clusters: A Middleware ApproachProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3581784.3607060(1-15)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3581784.3607060
Du YWang ZLeung CLeung V(2023)Accelerating and Securing Blockchain-Enabled Distributed Machine LearningIEEE Transactions on Mobile Computing10.1109/TMC.2023.332533423:6(6712-6730)Online publication date: 19-Oct-2023
https://dl.acm.org/doi/10.1109/TMC.2023.3325334
Mao HLi YZhu WLi FXu Y(2023)On Optimizing Traffic Imbalance in Large-scale Block-based Cloud Storage: Trace Analysis and Algorithm Design2022 IEEE 28th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS56603.2022.00100(728-736)Online publication date: Jan-2023
https://doi.org/10.1109/ICPADS56603.2022.00100
Yang MXu CZhou D(2023)Quantum mutual information redistribution in a pure tripartite state by a number partitioning algorithmPhysical Review A10.1103/PhysRevA.108.052402108:5Online publication date: 2-Nov-2023
https://doi.org/10.1103/PhysRevA.108.052402
Cobeña BContreras IMartínez-Merino LRodríguez-Chía A(2023)The profit-oriented hub line location problem with elastic demandComputers and Operations Research10.1016/j.cor.2023.106335159:COnline publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1016/j.cor.2023.106335
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents