"""
npp_dfs.py: breadth-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 breadth-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 npp_dfs import mk_part_II, display, Infinity
from chrono import clock
import sys
sys.setrecursionlimit(10000) # required for the large benchmarks
LOG = False
global init
global count
class Beam:
"""hold beam information:
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
remain - sum of weights for current list of items
UB - an upper bound (obtained with the differencing method)
"""
def __cmp__(self,other):
# does not work for long ints return int(self.UB-other.UB)
if self.DEVother.DEV:
return 1
if self.UBother.UB:
return 1
return 0
def __cmp____(self,other):
# does not work for long ints return int(self.UB-other.UB)
if self.UBother.UB:
return 1
return 0
def __str__(self):
s = ""
s += "label: " + str(self.label) + "\n"
s += "disj: " + str(self.disjoin) + "\n"
s += "join: " + str(self.join) + "\n"
s += "remain: " + str(self.remain) + "\n"
s += "dev: " + str(self.DEV) + "\n"
try:
s += "UB: " + str(self.UB) + "\n"
except:
pass
return s
def differencing_UB(label_):
"""fast version, only for obtaining objective
"""
label = [d for d,_ in label_]
for _ in range(len(label)-1):
d1 = label.pop()
d2 = label.pop()
insort(label, d1-d2)
return label.pop()
def differencing_edges(label_):
label = list(label_)
edges = []
for _ in range(len(label)-1):
d1,i1 = label.pop()
d2,i2 = label.pop()
insort(label, (d1-d2, i1))
edges.append((i1,i2)) # edge will force the two items in different partitions
return edges
def npp_bs(n, label, disjoin, join, remain, bestobj, LB, bmax):
"""beam 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
opt = True
# construct initial beam
b = Beam()
b.label = label
b.disjoin = disjoin # edges that force vertices to be in separate partitions
b.join = join # edges that force vertices to be in the same partition
b.remain = remain # remaining items/differences
b.DEV = 0 # number of sums (right branches) up to the current node
b.UB = None # upeer bound
# initial list of beams
B = [b]
while B != []:
sys.stdout.flush()
if count % 1 == 0 and clock() > limit:
print "cpu time exceeded..."
opt = False
break
if LOG:
print
print
print
print "NEW ITERATION n=%d" % n, len(B), "BEAMS"
print
cut = []
i = -1
for b in B:
i += 1
count += 1
if LOG:
print count, "branches, current beam:"
print b
# check if current branch can be cut
d1,i1 = b.label.pop()
b.slack = (2*d1 - b.remain) # difference between largest item and sum of others
if b.slack >= 0 or abs(b.slack) == LB: # first item is larger that the sum of the others
# best solution that can be achieved = slack
if b.slack >= bestobj:
if LOG: print "CUT:", display(b.slack), ">", display(bestobj)
cut.append(i)
continue
else:
print "UPDATING BEST: A ***",
print display(b.slack), "<", display(bestobj), "cpu:", clock()-init, "/", limit-init, "\t", count, "nodes"
sys.stdout.flush()
# first item must be in a partition, and remaining items in another:
bdisj = list(b.disjoin)
for d2,i2 in b.label:
bdisj.append((i1,i2))
bestobj = abs(b.slack)
best = (bestobj, list(bdisj), list(b.join))
if bestobj == LB:
# optimal solution found: first element == sum others (+-1)
print "optimal solution found",
return True, best
# no better solution can be obtained from here
cut.append(i)
continue
insort(b.label, (d1, i1)) # restore first element in label list
# calculate upper bounds
if b.UB == None:
b.UB = differencing_UB(b.label)
if LOG:
print "updating UB, current beam:"
print b
if b.UB < bestobj:
print "UPDATING BEST: B ***",
print display(b.UB), "<", display(bestobj), "cpu:", clock()-init, "/", limit-init, "\t", count, "nodes"
sys.stdout.flush()
best = (b.UB, b.disjoin+differencing_edges(b.label), list(b.join))
bestobj = b.UB
# print "best:", best
if bestobj == LB:
# optimal solution found: first element == sum others
print "optimal solution found with differencing"
return True, best
for i in reversed(cut):
B.pop(i)
B.sort()
if len(B) > bmax:
opt = False
del B[bmax:]
sys.stdout.flush()
if count % 1 == 0 and clock() > limit:
print "cpu time exceeded..."
opt = False
break
#print len(B), "/", bmax, "intermediate beams for n=", n
#sys.stdout.flush()
n -= 1
# for 4 or less items, differencing is exact
if n <= 3: # 4, but n was already decremented
break
newB = [] # where to place the new beams
for b in B:
if LOG:
print "SECOND PHASE, current beam:"
print b
# print "current list:", label, "disjoin:", disjoin, "join:", join
d1,i1 = b.label.pop()
d2,i2 = b.label.pop()
#
# FIRST BRANCH: try the same as differencing heuristic
#
insort(b.label, (d1-d2, i1))
b.disjoin.append((i1,i2)) # edge will force the two items in different partitions
b1 = Beam()
b1.label = list(b.label)
b1.disjoin = list(b.disjoin)
b1.join = list(b.join)
b1.remain = b.remain-2*d2 # -(d1+d2)+(d1-d2) = -2*d2
b1.UB = b.UB
b1.DEV = b.DEV
newB.append(b1)
if LOG:
print "created new beam:"
print b1
# restore data structures
pos = bisect_left(b.label,(d1-d2, i1))
b.label.pop(pos)
b.disjoin.pop()
#
# SECOND BRANCH: try the other possibility: put i1 and i2 on the same partition
#
if n <= 3:
continue
insort(b.label, (d1+d2, i1))
b.join.append((i1,i2)) # to assure i1 and i2 will be in same partition
b.UB = None
b.DEV += 1
if LOG:
print "updated beam:"
print b
if n <= 3:
B = newB
else:
B = newB + B
return opt, best
def differencing_bfs(data, bmax, 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 beam search
opt, (obj,disjoin,join) = npp_bs(n, label, disjoin, join, remain, bestobj, LB, bmax)
# make the partition, based on the disjoin/join edges
p1,p2 = mk_part_II(adjacent(range(n),disjoin),adjacent(range(n),join),[],[],0)
# print "\n\nbest partition:", p1,p2
# make a list with the weights for each partition
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:", display(obj)
print "number of nodes on BFS:", count
sys.stdout.flush()
return opt, obj, d1, d2
if __name__ == '__main__':
try:
bmax = int(sys.argv[1])
except IndexError:
# print "usage:", sys.argv[0], "bmax filename"
bmax = Infinity
# bmax = 1000
try:
filename = sys.argv[2]
except IndexError:
filename = "INSTANCES/NPP/toy.dat"
# filename = "INSTANCES/NPP/easy0070.dat"
# filename = "INSTANCES/NPP/hard0020.dat"
filename = "INSTANCES/NPP/n015d10e00.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:", filename, ",\tlog2(sum+1)=", display(sum(data))
print "bmax:", bmax
# print "\ndifferencing_construct: case of two partitions"""
# obj, d1, d2 = differencing_construct(data)
#
# 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 "objective:", pmax - pmin
print "\nbeam search"""
opt, obj,d1,d2 = differencing_bfs(data,bmax,320)
if opt == True:
star = '*'
else:
star = ''
c = d1+d2
c.sort()
assert abs(sum(d1)-sum(d2)) == obj
assert c == data
print "BeamSearch objective:", display(obj), star
sys.stdout.flush()