Inconsistent solver results between Python 3.8 and Python 3.10 with identical model and or-tools 9.12.4544

[wly2014]

What version of OR-Tools and what language are you using?
Version: 9.12.4544
Language: Python 3.8 and Python 3.10 in Conda

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)
Routing Library

What operating system (Linux, Windows, ...) and version?
Operating System: Windows 11

What did you do?
Steps to reproduce the behavior:

1. Run the same OR-Tools optimization program using Python 3.8 with or-tools==9.12.
2. Observe correct solution output.
3. Run the identical program using Python 3.10 (same OS, same or-tools version installed via pip)
4. Observe incorrect solution

What did you expect to see?
The solver should produce the same correct result in both Python 3.8 and Python 3.10 environments, as the model and OR-Tools version are identical.

What did you saw instead?
In Python 3.10, the solver returns an incorrect solution. No error is raised, but the result is logically inconsistent with the expected model behavior.

Make sure you include information that can help us debug (full error message, model Proto).
The benchmark program used is a case from the official vrp tutorial (example). I only added some code related to the time dimension. In my understanding, this additional code should not affect the original optimization result, and the results from running it in Python 3.8 confirm this.

"""Simple Vehicles Routing Problem (VRP).

   This is a sample using the routing library python wrapper to solve a VRP
   problem.
   A description of the problem can be found here:
   http://en.wikipedia.org/wiki/Vehicle_routing_problem.

   Distances are in meters.
"""

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp


def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data["distance_matrix"] = [
        # fmt: off
      [0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
      [548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
      [776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
      [696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
      [582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
      [274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
      [502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
      [194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
      [308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
      [194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
      [536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
      [502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
      [388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
      [354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
      [468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
      [776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
      [662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0],
        # fmt: on
    ]
    data["num_vehicles"] = 4
    data["depot"] = 0
    return data


def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    max_route_distance = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"Route for vehicle {vehicle_id}:\n"
        route_distance = 0
        while not routing.IsEnd(index):
            plan_output += f" {manager.IndexToNode(index)} -> "
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id
            )
        plan_output += f"{manager.IndexToNode(index)}\n"
        plan_output += f"Distance of the route: {route_distance}m\n"
        print(plan_output)
        max_route_distance = max(route_distance, max_route_distance)
    print(f"Maximum of the route distances: {max_route_distance}m")



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)

    # Create and register a transit callback.
    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)

    # Add Distance constraint.
    dimension_name = "Distance"
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        3000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name,
    )
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

    # ======================= additional code =======================
    def time_callback(from_index, to_index):
        return 1.0
    time_callback_index = routing.RegisterTransitCallback(time_callback)

    dimension_name_time = "Time"
    routing.AddDimension(
        time_callback_index,
        0,  # no slack
        3000,  # vehicle maximum travel time
        True,  # start cumul to zero
        dimension_name_time,
    )
    time_dimension = routing.GetDimensionOrDie(dimension_name_time)
    # ======================= additional code =======================

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

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

    # Print solution on console.
    if solution:
        status = routing.status()
        print(f"routing.status: {status}")
        print_solution(data, manager, routing, solution)
    else:
        print("No solution found !")


if __name__ == "__main__":
    main()

The results are the same with or without the additional code:

routing.status: 1
Objective: 177500
Route for vehicle 0:
 0 ->  9 ->  10 ->  2 ->  6 ->  5 -> 0
Distance of the route: 1712m

Route for vehicle 1:
 0 ->  16 ->  14 ->  8 -> 0
Distance of the route: 1484m

Route for vehicle 2:
 0 ->  7 ->  1 ->  4 ->  3 -> 0
Distance of the route: 1552m

Route for vehicle 3:
 0 ->  13 ->  15 ->  11 ->  12 -> 0
Distance of the route: 1552m

Maximum of the route distances: 1712m

However, when I run the same code in Python 3.10, the solution differs from that in Python 3.8, as shown below:

routing.status: 7
Objective: 0
Route for vehicle 0:
 0 -> 0
Distance of the route: 0m

Route for vehicle 1:
 0 -> 0
Distance of the route: 0m

Route for vehicle 2:
 0 -> 0
Distance of the route: 0m

Route for vehicle 3:
 0 ->  16 ->  15 ->  14 ->  13 ->  12 ->  11 ->  10 ->  9 ->  8 ->  7 ->  6 ->  5 ->  4 ->  3 ->  2 ->  1 -> 0
Distance of the route: 0m

Maximum of the route distances: 0m

Anything else we should know about your project / environment

• OR-Tools was installed via pip (pip install ortools==9.12.4544) in both Conda environments.

[Mizux]

1. Why the last route in python 3.10 trace is 0 ? also the objective is zero which is strange to say the least...
   EDIT: routing status is 7 Optimal since 0 is the lower bound of this minimization pb...
   

   or-tools/ortools/constraint_solver/routing_enums.proto

   Lines 168 to 169 in 93dafb7

   	// Problem has been solved to optimality.
   	ROUTING_OPTIMAL = 7;

2. You should try to use the Guided local search, while not deterministic it should help solver to converge to a good (optimal?) solution...

[wly2014]

After trying a few things, I figured out why this problem was happening—it was a feature or bug. If I change the returned value of time_callback to an int, I get the right result in both Python 3.8 and Python 3.10.

    # ======================= additional code =======================
    def time_callback(from_index, to_index):
        return int(1.0)
    time_callback_index = routing.RegisterTransitCallback(time_callback)

[Mizux]

After trying a few things, I figured out why this problem was happening—it was a feature or bug. If I change the returned value of time_callback to an int, I get the right result in both Python 3.8 and Python 3.10.

    # ======================= additional code =======================
    def time_callback(from_index, to_index):
        return int(1.0)
    time_callback_index = routing.RegisterTransitCallback(time_callback)

Callbacks must return an std::int64_t i.e. wrapped as a Python int by SWIG.

or-tools/ortools/routing/types.h

Lines 49 to 50 in 7e348a7

	typedef std::function<int64_t(int64_t)> RoutingTransitCallback1;
	typedef std::function<int64_t(int64_t, int64_t)> RoutingTransitCallback2;

[wly2014]

Is it possible that in a Python 3.8 environment, the conversion process from float to int can be done automatically?

[Mizux]

Is it possible that in a Python 3.8 environment, the conversion process from float to int can be done automatically?

yes, we call it "undefined behaviour" and can't trust any result... IIRC the address is reinterpret cast as an int so if your float has no exposant it may work...