""" npp_dfs.py: depth-first search for 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 for doing tree search for this problem, using depth-first search. The search can be complete or incomplete; it is interrupted if the CPU time used exceeds the limit allowed. Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2009 """ from bisect import * from graphtools import adjacent from npp import mk_part, differencing_construct, longest_processing_time from copy import deepcopy from chrono import clock Infinity=1.e10000 import sys sys.setrecursionlimit(10000) # required for the large benchmarks global count global init def mk_part_II(disjoin,join,p1,p2,node): """make a partition of nodes from a graph, according to 'disjoin' and 'join' edges""" p1.append(node) for j in join[node]: # vertices that must be in the same partition join[j].remove(node) mk_part_II(disjoin,join,p1,p2,j) for j in disjoin[node]: # vertices that must be in different partitions disjoin[j].remove(node) mk_part_II(disjoin,join,p2,p1,j) return p1,p2 def display(bignumber): """users friendly printing for very large numbers""" from math import log if bignumber == Infinity: return "inf" if bignumber < 0: return "-%.4g" % (log(-bignumber+1)/log(2)) return "%.5g" % (log(bignumber+1)/log(2)) def npp_dfs(n, label, disjoin, join, remain, bestobj, LB): """depth-first search for number partitioning, based on differencing method Arguments: n - number of items (on the current list) label - sorted list with pairs [(wi,i),...], where wi is the weight of item i disjoin - edges [(i,j),...] indicating that i and j must be in different partitions join - edges [(i,j),...] indicating that i and j must be in the same partition bestobj - objective value for the best known solution remain - sum of weights for current list of items LB - known lower bound (0 for even sum of weights, 1 for odd) """ global init, limit, count # check cpu count += 1 opt = True if count % 100000 == 0 and clock() > limit: # check if must interrupt print "cpu time exceeded..." opt = False # check if current branch can be cut d1,i1 = label.pop() slack = (2*d1 - remain) # difference between largest item and sum of others if slack >= 0 or abs(slack) == LB: # first item is larger that the sum of the others # best solution that can be achieved = slack if slack >= bestobj: # cut, as there is no way of improving the objective # print "CUT:", display(slack), ">", display(bestobj) return opt, Infinity, None, None print "UPDATING BEST: - ***", print display(slack), "<", display(bestobj), "\tcpu:", clock()-init, "/", limit-init while label != []: d2,i2 = label.pop() # first item must be in a partition, and remaining items in another: disjoin.append((i1,i2)) if abs(slack) == LB: # optimal solution found: first element == sum others print "optimal solution found", if slack<0: print "- ***", print return opt, LB, disjoin, join return opt, slack, disjoin, join # print "current list:", label, "disjoin:", disjoin, "join:", join d2,i2 = label.pop() # copy data structures label_orig = list(label) disjoin_orig = list(disjoin) join_orig = list(join) # # FIRST BRANCH: try the same as differencing heuristic # insort(label, (d1-d2, i1)) disjoin.append((i1,i2)) # edge will force the two items in different partitions opt,obj1,disjoin1,join1 = npp_dfs(n-1, label, disjoin, join, remain-2*d2, bestobj, LB) # -(d1+d2)+(d1-d2) = -2*d2 if obj1 < bestobj: bestobj = obj1 if bestobj <= LB: # print bestobj, "< LB", LB, "REACHED!!!" return opt,obj1,disjoin1,join1 # for 4 or less items, differencing is exact if n <= 4 or opt == False: return opt,obj1,disjoin1,join1 # # SECOND BRANCH: try the other possibility: put i1 and i2 on the same partition # insort(label_orig, (d1+d2, i1)) join_orig.append((i1,i2)) # to assure i1 and i2 will be in same partition opt,obj2,disjoin2,join2 = npp_dfs(n-1, label_orig, disjoin_orig, join_orig, remain, bestobj, LB) if obj1 <= obj2: return opt,obj1,disjoin1,join1 # else return opt,obj2,disjoin2,join2 def differencing_dfs(data, cpulimit): """depth-first search based on the differencing method: partition a list of items into two partitions * prepare data * call the recursive function for the actual depth-first search * return the two partitions obtained """ global init, limit, count init = clock() limit = cpulimit count = 0 # copy and sort data by decreasing order n = len(data) label = [(data[i],i) for i in range(n)] label.sort() # initialize data for the differencing method's graph bestobj = Infinity disjoin = [] # edges that force vertices to be in separate partitions join = [] # edges that force vertices to be in the same partition remain = sum(data) # remaining items/differences LB = remain & 1 # LB=1 for odd sums, 0 for even # call the depth-first recursion opt,obj,disjoin,join = npp_dfs(n, label, disjoin, join, remain, bestobj, LB) # make the partition, based on the disjoin/join edges p1,p2 = mk_part_II(adjacent(range(n),disjoin),adjacent(range(n),join),[],[],0) # make a list with the weights for each partition # print "\n\nbest partition:", p1,p2 d1 = [data[i] for i in p1] d2 = [data[i] for i in p2] # print "p1 indices:", p1, "weights:", d1, sum(d1) # print "p2 indices:", p2, "weights:", d2, sum(d2) # print "objective:", obj print "number of nodes on DFS:", count return opt, obj, d1, d2 import sys if __name__ == '__main__': try: filename = sys.argv[1] except IndexError: filename = "INSTANCES/NPP/easy0060.dat" filename = "INSTANCES/NPP/hard0010.dat" filename = "INSTANCES/NPP/test.dat" try: f = open(filename) except IOError: print "file", filename, "could not be read" exit(-1) data = f.readlines() f.close() data = [int(i) for i in data] print "initial data:", data, "sum=", sum(data) print "\ndifferencing_construct: case of two partitions""" obj, d1, d2 = differencing_construct(data) print "Differencing objective:", obj c = d1+d2 c.sort() assert c == data print "\nlongest_processing_time: case of two partitions""" part = longest_processing_time(data,2) pmax = 0 pmin = Infinity for p in part: s = sum(p) # print p, s pmin = min(pmin,s) pmax = max(pmax,s) print "LPT objective:", pmax - pmin print "\nDFS""" opt,obj,d1,d2 = differencing_dfs(data,3600) c = d1+d2 c.sort() assert abs(sum(d1)-sum(d2)) == obj assert c == data print "B&B objective:", obj print d1, d2