from npp import mk_part, differencing_construct, longest_processing_time from npp_dfs import Infinity, display from chrono import clock import sys from npp_mk_inst import EASY, HARD, DECIMAL INST = EASY + HARD + DECIMAL INST = EASY[-3:-2] DIR = "INSTANCES/NPP/" # output = open("RESULTS/NPP/npp-bfs.csv","a") output = sys.stdout print >>output, "\t%-20s\t%s\t%s\t%s\t%s\t%s\t%s\t%s\t%s\t%s\t%s" % \ ("Instance", "n", "BFS: eta", "BFS: E", "t", "DIFF: eta", "DIFF: E", "t", "LPT: eta", "LPT: E", "t") # for bmax in [10, 100, 1000, 10000, 100000]: for bmax in [100000]: print >>output, "bmax=", bmax for inst in INST: print "\ninstance", inst, "bmax=", bmax filename = DIR+inst f = open(filename) data = f.readlines() data = [int(i) for i in data] # print "initial data:", data, "sum=", sum(data) K,star,t, K1, t1, K2, t2, K3, t3, K4, t4 = -1,'',0, -1,0, -1,0, -1,0, -1,0 S, S1, S2, S3, S4 = "", "", "", "", "" cpu = clock() if inst in DECIMAL: limit = 600 else: limit = 3600 from npp_bfs import differencing_bfs opt,K,d1,d2 = differencing_bfs(data, bmax, cpu+limit) S = display(K) if opt == True: star = '*' t = clock() - cpu c = d1+d2 c.sort() assert c == data print "BS:", K cpu = clock() K1, d1, d2 = differencing_construct(data) S1 = display(K1) t1 = clock() - cpu c = d1+d2 c.sort() assert c == data print "Differencing:", K1 cpu = clock() part = longest_processing_time(data,2) t2 = clock() - cpu pmax = 0 pmin = Infinity c = [] for p in part: s = sum(p) # print p, s pmin = min(pmin,s) pmax = max(pmax,s) c += p c.sort() assert c == data # print "objective:", pmax - pmin K2 = pmax - pmin S2 = display(K2) print "LPT:", K2 print >>output, "bmax=", bmax, "\t%-20s\t%d\t%s\t%d%2s\t%.2f\t%s\t%d\t%.2f\t%s\t%d\t%.2f" % \ (inst, len(data), S,K,star,t, S1,K1,t1, S2,K2,t2) output.flush() sys.stdout.flush()