""" npp.py: simple heuristics for the Number Partitioning Problem. The Number Partitioning Problem (NPP) is a combinatorial optimization problem where: given a set of numbers, find a partition into two subsets such that the difference between the sum of their elements is minimal. This file contains a set of functions to illustrate: - the differencing method of Karmarkar and Karp (differencing_construct) - a greedy heuristics, the longest processing time (longest_processing_time) - the differencing method extended for more than two partitions (multi_differencing_construct) Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2009 """ from heapq import * from graphtools import adjacent LOG = True # whether or not to print intermediate solutions def mk_part(adj,p1,p2,node): """make a partition of nodes from a graph, for the differencing_construct""" p1.append(node) for j in adj[node]: adj[j].remove(node) mk_part(adj,p2,p1,j) return p1,p2 def differencing_construct(data): """partition a list of items with the differencing method -- case of two partitions""" if LOG: print "log of the execution with differencing_construct:" # create heap with data and their indices # as we want decreasing order, we set -data[] as the key n = len(data) label = [] for i in range(n): heappush(label, (-data[i],i)) # added tuples have a -datum and its index in 'data' if LOG: print "created heap of (weight,vertex) pairs:", [(-w, i) for w, i in label] # differencing method: create graph with labels updated with differences edges = [] if LOG: print "poping elements from heap, creating edge set" while len(label) > 1: d1,i1 = heappop(label) d2,i2 = heappop(label) # calculate differences between two largest elements # update the label of the largest with the difference heappush(label, (d1-d2, i1)) edges.append((i1,i2)) # edge will force the two items in different partitions if LOG: print "popped %d and %d, pushed %d; heap: %s --> added edge %s" % \ (-d1, -d2, -(d1-d2), [(-w, i) for w, i in label], (i1, i2)) # last element of the heap has the difference between the two partitions (i.e., the objective) obj,_ = heappop(label) obj = -obj if LOG: print "edges:", edges # create the partitions by going through the graph created nodes = range(n) adj = adjacent(nodes,edges) p1, p2 = mk_part(adj,[],[],0) # make a list with the weights for each partition d1 = [data[i] for i in p1] d2 = [data[i] for i in p2] if LOG: print "solution:" print "p1 indices:", p1, "weights:", d1, sum(d1) print "p2 indices:", p2, "weights:", d2, sum(d2) print "objective:", obj return obj, d1, d2 def longest_processing_time(data_,m): """separate 'data' into 'm' partitions with longest_processing_time method""" if LOG: print "log of the execution with longest_processing_time:" # copy and sort data by decreasing order data = list(data_) data.sort() data.reverse() if LOG: print "initial data:", data part = [[] for i in range(m)] # initialize partition with empty lists weight = [] # heap with weights on each partition for p in range(m): heappush(weight, (0,p)) # for each item, add it to the partition with least weight for item in data: w,p = heappop(weight) part[p].append(item) w += item heappush(weight, (w,p)) if LOG: print "added %d to partition %d" % (item, p) if LOG: print "solution:" for i in range(m): print " partition %d: %s, sum=%d" % (i, part[i], sum(part[i])) return part def multi_differencing_construct(data, m): """partition a list of items with the differencing method for more than two partitions""" n = len(data) # create a heap to hold tuples with the information required by the algorithm # each 3-tuple has (a,b,c) where # a -- label # b -- list of the lists of items on each partition # c -- sum of the weights on each partition (for ordering them) # eg: heap = [(-4, [[10], [8, 5], [14]], [10, 13, 14]), (-1, [[], [], [1]], [0, 0, 1]), ...] if LOG: print "log of the execution with multi_differencing_construct:" heap = [] for i in range(n): datum = data[i] part = [[] for p in range(m)] # initially, all partitions are empty sums = [0 for p in range(m)] part[-1].append(datum) # insert one item on the last partition sums[-1] = datum # update the sum of weights for last partition label = -datum # as the heap is in increasing order heappush(heap, (label, part, sums)) if LOG: print "initial heap: %s\n" % [(-label, part, sums) for label, part, sums in heap] # differencing method while len(heap) > 1: # join two elements with largest weights in the heap label1,part1,sums1 = heappop(heap) label2,part2,sums2 = heappop(heap) if LOG: print "popped:", (-label1,part1,sums1) print "popped:", (-label2,part2,sums2) # on each element sort the sets of items by the # corresponding sum tmp = [] for p in range(m): part = part1[p] + part2[-1-p] # join the lists of items by reverse order sums = sums1[p] + sums2[-1-p] # update the sum of weights in each list tmp.append((sums, part)) tmp.sort() # sort by increasing order of weights sums = [i for (i,_) in tmp] # extract the sum of item's weights part = [p for (_,p) in tmp] # extract the lists of items label = sums[0] - sums[-1] # the new label is the different between the farthest sums of weights heappush(heap,(label, part, sums)) if LOG: print "pushed:", (-label, part, sums) print "current heap:", [(-label, part, sums) for label, part, sums in heap] print # last element of the heap has the two partitions, the sums # difference between the two partitions (i.e., the objective) obj,part,sums = heappop(heap) obj = -obj if LOG: print "solution:" print "objective:", obj for i in range(m): print " partition %d: %s, sum=%d" % (i, part[i], sum(part[i])) return obj,part,sums if __name__ == '__main__': """Heuristics for the Number Partitioning Problem: sample usage.""" # data = [1,1,10,30,30,40,60,80] data = [1, 2, 5, 8, 10, 14] n = len(data) n = 500 print "initial data:", data print "\n\n*** differencing_construct: case of two partitions ***" obj, p1, p2 = differencing_construct(data) print "partitions:", p1, p2, "obj:", obj print "\n\n*** longest processing time heuristic ***" part = longest_processing_time(data,2) print "partitions:", part[0], part[1], "obj:", abs(sum(part[0]) - sum(part[1])) print "\n\n*** differencing_construct: multi partition ***" print "\nresults for two partitions" m = 2 obj,part,sums = multi_differencing_construct(data,m) print "partitions:", part, "obj:", obj print "\nresults for three partitions" m = 3 obj,part,sums = multi_differencing_construct(data,3) print "partitions:", part, "obj:", obj