Number Partitioning

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 = (a₁, a₂, ..., a_n) of non-negative integers. The output is a sequence S = (s₁, s₂, ..., s_n) of signs s_i 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 = {p₁, p₂, ..., p_n} where p_i in {1, ..., n}. The sequence P represents a pre-partitioning of the elements of A, in the following way: if p_i = p_j, then we enforce the restriction that a_i and a_j have the same sign. Equivalently, if p_i = p_j, then a_i and a_j both lie in the same subset, either A₁ or A₂.

For a full writeup refer to: number-partitioning-writeup.pdf.

Usage

$ 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.