Description

TITION problem, which is (of course) NP-complete. 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 ∈ {−1,+1} such that the residue
n
usiai

is minimized. Another way to view the problem is the goal is to split the set (or multi-set) of numbers given by A into two subsets A1 and A2 with the sums of A1 and A2 being as close to equal as possible. The absolute value of the difference of the sums is the residue.
As a warm-up exercise, you will first prove that even though Number Partition is NP-complete, it can be solved in pseudo-polynomial time. That is, suppose the sequence of integers in A sum up to some number b. Then each of the numbers in A has at most logb bits, so a polynomial time algorithm would take time polynomial in nlogb. Instead you should find a dynamic programming algorithm that takes time polynomial in nb.
Give a dynamic programming solution to the Number Partition problem.
The Karmarkar-Karp algorithm repeatedly takes the largest two elements remaining in A at each step and uses differencing on them. For example, if A is intially (10,8,7,6,5), then the KK algorithm proceeds as follows:
(10,8,7,6,5) → (2,0,7,6,5)
→ (2,0,1,0,5)
→ (0,0,1,0,3)
→ (0,0,0,0,2)
Hence the KK algorithm returns a residue of 2. However, the best possible residue for the example is 0.
Explain briefly how the Karmarkar-Karp algorithm can be implemented in O(nlogn) steps, assuming the values in A are small enough that arithmetic operations take one step.
You will compare the Karmarkar-Karp algorithm and a variety of randomized heuristic algorithms on random input sets. Let us first discuss two ways to represent solutions to the problem and the state space based on these representations. Then we discuss heuristic search algorithms you will use.
The standard representation of a solution 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. Thinking of all possible solutions as a state space, a natural way to define neighbors of a solution S is as the set of all solutions that differ from S in either one or two places. This has a natural interpretation if we think of the +1 and −1 values as determining two subsets A1 and A2 of A. Moving from S to a neighbor is accomplished either by moving one or two elements from A1 to A2, or moving one or two elements from A2 to A1, or swapping a pair of elements where one is in A1 and one is in A2.
An alternative way to represent a solution called prepartitioning is as follows. We represent a solution by a sequence P = {p1, p2,…, pn} where pi ∈ {1,…,n}. The sequence P represents a prepartitioning 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. You can think of prepartitioning as being the opposite of differencing: where differencing splits two elements apart, prepartioning is a way of forcing elements together.
We turn a solution of this form into a solution in the standard form using two steps:
• We derive a new sequence A0 from A which enforces the prepartioning from P. Essentially A0 is derived by resetting ai to be the sum of all values j with pj = i, using for example the following pseudocode:
A0 = (0,0,…,0) for j = 1 to n
a0pj = a0pj +aj
• We run the KK heuristic algorithm on the result A0.
For example, if A is initially (10,8,7,6,5), the solution P = (1,2,2,4,5) corresponds to the following run of the KK algorithm:
A = (10,8,7,6,5) → A0 = (10,15,0,6,5)
(10,15,0,6,5) → (0,5,0,6,5)
→ (0,0,0,1,5)
→ (0,0,0,0,4)
Hence in this case the solution P has a residue of 4.
Notice that all possible solution sequences S can be generated using this prepartition representation, as any split of A into sets A1 and A2 can be obtained by initially assigning pi to 1 for all ai ∈ A1 and similarly assigning pi to 2 for all ai ∈ A2.
A random solution can be obtained by generating a sequence of n values in the range [1,n] and using this for P. Thinking of all possible solutions as a state space, a natural way to define neighbors of a solution P is as the set of all solutions that differ from P in just one place. The interpretation is that we change the prepartitioning by changing which partition one element lies in. A random move on this state space can be defined as follows. Choose two random indices i and j from [1,n] with pi 6= j and set pi to j.
You will try each of the following three algorithms for both representations.
• Repeated random: repeatedly generate random solutions to the problem, as determined by the representation.
Start with a random solution S for iter = 1 to max iter S0 = a random solution
if residue(S0) < residue(S) then S = S0
return S
• Hill climbing: generate a random solution to the problem, and then attempt to improve it through moves to better neighbors.
Start with a random solution S for iter = 1 to max iter S0 = a random neighbor of S if residue(S0) < residue(S) then S = S0
return S
• Simulated annealing: generate a random solution to the problem, and then attempt to improve it through moves to neighbors, that are not always better.
Start with a random solution S S00 = S
for iter = 1 to max iter S0 = a random neighbor of S if residue(S0) < residue(S) then S = S0
else S = S0 with probability exp(−(res(S0)-res(S))/T(iter)) if residue(S) < residue(S00) then S00 = S
return S00
Note that for simulated annealing we have the code return the best solution seen thus far.
You will run experiments on sets of 100 integers, with each integer being a random number chosen uniformly from the range [1,1012]. Note that these are big numbers. You should use 64 bit integers. Pay attention to things like whether your random number generator works for ranges this large!
Below is the main problem of the assignment.
First, write a routine (ideally compiled by make, as in the last programming assignments, and that will run on nice) of the form
$ ./kk inputfile
is the residue obtained by running Karmarkar-Karp with these 100 numbers as input.
Second, generate 50 random instances of the problem as described above. For each instance, find the result from using the Karmarkar-Karp algorithm. Also, for each instance, run a repeated random, a hill climbing, and a simulated annealing algorithm, using both representations, each for at least 25,000 iterations.
Give tables and/or graphs clearly demonstrating the results – give both the numerical results, and the time taken by the algorithms. Compare the results and discuss.
For the simulated annealing algorithm, you must choose a cooling schedule. That is, you must choose a function T(iter). We suggest T(iter) = 1010(0.8)biter/300c for numbers in the range [1,1012], but you can experiment with this as you please.
Note that, in our random experiments, we began with a random initial starting point.
Discuss briefly how you could use the solution from the Karmarkar-Karp algorithm as a starting point for the randomized algorithms, and suggest what effect that might have. (No experiments are necessary, but feel free to try it.)
Finally, the following is entirely optional; you’ll get no credit for it. But if you want to try something else, it’s interesting to do.