""" npp_mk_inst: generate a series of benchmark instances for number partitnioning files easy*.dat: - random numbers with n/2 bits (for sets with n elements) - large number of perfect partitions - easy instances files hard*.dat: - random numbers with n bits (for sets with n elements) - small/null number of perfect partitions - hard instances Notice that according to S.Mertens, "The easiest hard problem", the critical number of bits in random generated integers, for a problem with N items is: def kc(N): return 1 - (log2(N) - log2(pi/6))/(1.*N) """ import random def mk_data_trivial(n, min_value, max_value): """make random data number partitioning: trivial case""" return [min_value + int(random.random() * (max_value-min_value+1)) for i in range(n)] def mk_data(n, nbits): """make random data number partitioning: using integers with 'nbits' bits""" data = [] for i in range(n): value = 0 for b in range(nbits): if random.random() >= 0.5: value += 2**b data.append(value) return data def mk_data_decimal(n, nbits): """make random data number partitioning: using integers with 'nbits' bits""" data = [] for i in range(n): value = 0 for b in range(nbits): value = 10*value + int(random.random()*10) data.append(value) return data def write_data(filename,data): print filename f = open(filename, 'w') for i in data: print >>f, i f.close() # names of the instances EASY = ["easy%04d.dat" % n \ for n in [10,20,30,40,50,60,70,80,90,100,200,300,400,500,600,700,800,900,1000]] HARD = ["hard%04d.dat" % n \ for n in [10,20,30,40,50,60,70,80,90,100,200,300,400,500,600,700,800,900,1000]] DECIMAL = ["n%03dd%02de%02d.dat" % (n,b,e)\ for b in [10,12,14] for n in [15,25,35,45,55,65,75,85,95,105] for e in range(10)] if __name__ == "__main__": random.seed(1) for n in [10,20,30,40,50,60,70,80,90,100,200,300,400,500,600,700,800,900,1000]: # easy instances data = mk_data(n,n/2) data.sort() filename = "easy%04d.dat" % n write_data(filename,data) # hard instances data = mk_data(n,n) data.sort() filename = "hard%04d.dat" % n write_data(filename,data) for b in [10,12,14]: for n in [15,25,35,45,55,65,75,85,95,105]: for e in range(10): data = mk_data_decimal(n,b) data.sort() filename = "n%03dd%02de%02d.dat" % (n,b,e) write_data(filename,data)