The Easiest Hard Problem: Now Even Easier

Horn, Ruben; Thomson, Sarah L; van den Berg, Daan; Adriaans, Pieter

Abstract

We present an exponential decay function that characterizes the number of solutions to instances of the Number Partitioning Problem (NPP) with uniform distribution of bits across the integers. This function is fitted on the number of optimal solutions of random instances with lengths between 10 and 20 integers and may be used as a heuristic either directly by new algorithms for the NPP or as a benchmark to evaluate how well different Evolutionary Algorithms (EAs) cover the search space. Despite the long history of the NPP, it seems such a characterization does not yet exist.

Citation

Horn, R., Thomson, S. L., van den Berg, D., & Adriaans, P. (2024, July). The Easiest Hard Problem: Now Even Easier. Presented at ACM Genetic and Evolutionary Computation Conference (GECCO) 2024, Melbourne, Australia

• Presentation Conference Type: Conference Abstract
• Conference Name: ACM Genetic and Evolutionary Computation Conference (GECCO) 2024
• Start Date: Jul 14, 2024
• End Date: Jul 18, 2024
• Acceptance Date: May 2, 2024
• Online Publication Date: Aug 1, 2024
• Publication Date: 2024
• Deposit Date: May 3, 2024
• Publicly Available Date: Aug 1, 2024
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Not Peer Reviewed
• Pages: 97-98
• Book Title: Genetic and Evolutionary Computation Conference (GECCO ’24), July 14–18, 2024, Melbourne, VIC, Australia
• DOI: https://doi.org/10.1145/3638530.3664099
• Keywords: The Easiest Hard Problem, Number Partitioning Problem, Combinatorial Optimization