Forma Analysis and new Heuristic Ideas for the Number Partitioning Problem

Introduction and Motivation The Min Number Partitioning problem has been a hard challenge for metaheuristics for at least a decade. It was originally the paper by Johnson et al.[4] that first identified the problem that a metaheuristic of prestige among physicists, Simulated Annealing (SA), was having to address this problem [15]. The problem is an open challenge for other metaheuristics like Genetic Algorithms (GAs) [7] [13], SA [4] [15] [14], problem space local search [16], GRASP [1], and Tabu Search [6]. The decision version is widely cited as being a conspicuous member of the NP-complete class, one of the "six-essential" NP-complete problems. Moreover, the problem has another source of interest if we also have in mind that is essentially equivalent to find the ground-state of an infinite range Ising spin-glass system with antiferromagnetic couplings. As a consequence, we can think of this problem as being a worst-case scenario [12] among the tasks of finding the ground-state of