"""
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