This repo implements a number of heuristics for solving the Number Partition Problem (NP-Complete). Repeated random, hill climbing, and simulated annealing are used on 1.) a randomized solution and 2.) a pre-partitioned solution. As input, the number partition problem takes a sequence A = (a1, a2, ..., an) of non-negative integers. The output is a sequence S = (s1, s2, ..., sn) of signs si in {-1, +1} such that the residue (the absolute value of their sum) is minimized.
The first is a standard representation of a solution, which is simply as a sequence S of +1 and -1 values. A random solution can be obtained by generating a random sequence of n such values. An alternative way to represent a solution called pre-partitioning is as follows. We represent a solution by a sequence P = {p1, p2, ..., pn} where pi in {1, ..., n}. The sequence P represents a pre-partitioning of the elements of A, in the following way: if pi = pj, then we enforce the restriction that ai and aj have the same sign. Equivalently, if pi = pj, then ai and aj both lie in the same subset, either A1 or A2.
For a full writeup refer to: number-partitioning-writeup.pdf.
$ make
$ ./kk inputfile
inputfile is a list of unsorted integers (100 integers is standard), one per line, and the output is the residue obtained by running Karmarkar-Karp with these 100 numbers as input. To run the heuristic algorithms, change algo_flag in main.cpp to a non-zero value.