OR-tools returns sub-optimal TSP solution

Question

I'm trying to replicate a TSP code to calculate an optimal route from a user-supplied array of distances, but the code returns never giving me the optimized option. The return is always fixed at 90.

Given this code:

# Bibliotecas

from __future__ import print_function
import math
import pandas as pd
import scipy.spatial as sp
import numpy as np
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

# Início matriz de distâncias

R = int(input("Adicione o número de linhas:"))
C = int(input("Adicione o número de colunas:"))
print('Adicione a matriz de distâncias com os conteúdos separados por um espaço simples')
 
# Início matriz

entries = list(map(int, input().split()))

matrix = np.array(entries).reshape(R, C)

# Print matriz distâncias
print(matrix)
 

# Print matriz distâncias

# Fim matriz de distâncias

# TSP ínicio

# Armazena dados matriz

def create_data_model():

    data = {}

    data['distance_matrix'] = matrix
    
    data['num_vehicles'] = 1
    data['depot'] = 0
    return data

def print_solution(manager, routing, solution):

# Print das soluções
#     

    print('Objective: {} miles'.format(solution.ObjectiveValue()))
    index = routing.Start(0)
    plan_output = 'Route for vehicle 0:\n'
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += ' {} ->'.format(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += ' {}\n'.format(manager.IndexToNode(index))
    print(plan_output)
    plan_output += 'Route distance: {}miles\n'.format(route_distance)


# Resolução primária do problema
def main():
    """Entry point of the program."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                           data['num_vehicles'], data['depot'])

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)


    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC)

    search_parameters.local_search_metaheuristic = (
           routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

    search_parameters.time_limit.seconds = 30

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(manager, routing, solution)

if __name__ == '__main__':
    main()

I am using OR-Tools to solve a MIP with SCIP. OR-Tools returns optimal values for continuous and integer (binary) variables of my problem.

When I then fix the binary variables of this MIP to the optimal values returned by OR-Tools (for the MIP) and I solve the corresponding LP with GLOP, OR-Tools returns new values for the optimal values of the continuous variables.

My understanding is that the initial problem does not have a unique solution (in terms of optimal values of variables).

So my question is: How can I make OR-tools return the optimal solution? The optimal route should be 80

Answer 1

try to increase the solver time limit

"search_parameters.time_limit.seconds = xxxxx"