I'm currently studying TSP formulations using Pulp in Python. Originally, I was using three different point sets with 29, 38 and 194 cities, and the code solved them pretty well and even got the optimal solution. However, when I tried using 734 (uy734) cities, the LpProblem was created as a NoneType (after creatitng it, I tried printing it and all I got was a blank space, and its variables were also NoneType).
This link leads to a .zip file with all that's needed to run the code, including the point sets I'm using.
I didn't do much since this came up, I tried searching similar problems and questions, thought could be something I should be returning, but it still bugs me that it only happens with larger problems, and they aren't that large either, at least Python seems tot be able to keep up with a lot more than that.
Here's the main function for calling all the others.
def testing_all_3(i):
#these are the file names
file = ['wi29', 'dj38', 'qa194', 'uy734', 'zi929', 'lu980', 'rw1621', 'mu1979', 'nu3496', 'ca4663']
print("===============")
print("Testando o arquivo", file[i] + ".tsp")
#I open the current file using a special function
#(the file type is TSP, which has its own library to work with)
bench = _tspfile(file[i] + ".tsp")
n = bench.dimension
#I use the data that I got from the file, making a list of nodes
#(which I represent with numbers)
cidades, destinos = _append(n)
#the weight of each node that I transform into a dictionary for Pulp
costs = _tsp(n, bench)
costs = makeDict([cidades, destinos], costs, 0)
#prob = creating(cidades, destinos)
#Then I call two function that are very similar for solving the problem
print("Resolvendo com MTZ")
solvingMTZ(cidades, destinos, n, costs, file[i])
print("===============")
print("Testando o arquivo", file[i] + ".tsp")
print("Resolvendo com DL")
solvingDL(cidades, destinos, n, costs, file[i])
for i in range(5,10):
#I would make this range from 0 to 9
#but I only get the warning at the 4th and beyond file
testing_all_3(i)
Here's the function for solving the problem (putting just the MTZ one because DL is nearly identical)
def solvingMTZ(cidades, destinos, n, costs, file):
prob = LpProblem("Teste", LpMinimize)
road = [(cid_i, cid_j) for cid_i in cidades for cid_j in destinos]
var = LpVariable.dicts("Road", (cidades, destinos), 0, 1, LpInteger)
prob += lpSum([var[cid_i][cid_j] * costs[cid_i][cid_j] for (cid_i, cid_j) in road]) #função obj
for i in cidades:
prob += lpSum([var[i][cid_j] for cid_j in destinos if i != cid_j]) == 1 #única entrada
for j in destinos:
prob += lpSum([var[cid_i][j] for cid_i in cidades if j != cid_i]) == 1 #única saída
prob = mtz(n, prob, cidades, var)
timelimit = max_time
start = time.time()
prob.solve(GUROBI_CMD(timeLimit=timelimit, msg=1, gapRel=0))
end = time.time()
timelimit = timelimit - end + start
print(timelimit)
#imprimo os valores das variáveis e o resultado final da função
print_prob(prob, timelimit)
make_node_fileMTZ(prob, file, timelimit)
return
#the function I called to help solving the problem
#the DL one (solvingDL) is nearly identical, so I didn't add it here
def mtz(n, prob, cidades, var):
u = LpVariable.dicts('u', (i for i in cidades), 1, n-1, LpInteger)
for i in cidades[1:]:
for j in cidades[1:]:
#if i != j:
prob += u[i] - u[j] + (n - 1) * var[i][j] <= n - 2
return prob
And finally, where I discovered the problem (when I tried printing out the values of my variables and the objective).
def print_prob(prob, timelimit):
for v in prob.variables():
if (v.varValue >= 1):
print(v.name, "=", v.varValue)
print(value(prob.objective))
if timelimit >= 0:
print("Tempo de execução restante:", timelimit)
print("Tempo de execução total:", max_time - timelimit)
else:
print("O ótimo não foi encontrado com o tempo dado.")
#print(prob)
return
I'm sorry for the mixage of languages, I'm Brazilian and it's a bit hard to change your entire code for one language to another, hope this is enough so someone can help me. I need to fix this so I can continue witht my research, and thank you for anyone that can think of a solution
timelimitis in your code, but it is certainly possible that when you take the massive jump up to 700+ cities that the problem is not solved in time. The status should be shown when you print the problem. TSP with 700+ nodes is a massive problem. You might try removing the time limit and solving progressively larger problems from like {10, 20, 50, 100, 200} nodes and plotting the times it takes to solve as a part of your research... :)prob.solve()statement that isprint(prob)and see what comes out...