1

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

4
  • You don't show what the value of timelimit is 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... :) Commented Jan 23, 2023 at 20:15
  • I know, but it seems a bit irrelevant for this, I mean, I try printing the problem before solving within the time limit, and it doesn't print anything Commented Jan 24, 2023 at 21:08
  • I don't see where you are doing that. Add a line in right before the prob.solve() statement that is print(prob) and see what comes out... Commented Jan 24, 2023 at 21:44
  • Strange, I thought I did edit here as well, but I remember adding print(prob) after prob = LpProblem... and it was printing nothing Commented Jan 25, 2023 at 22:12

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.