Or-tools: Routing library - SearchParameter is ignored once calling ReadAssignmentFromRoute

[ghost]

Issue

Once calling the method RoutingModel::ReadAssignmentFromRoutes()

The method RoutingModel::SolveFromAssignmentWithParameters() or RoutingModel::SolveWithParameters ignore the SearchParameter argument (without any warning)...

i.e.

1. The log search parameter is ignored and does not print anything.
2. The solver seems to fall back to a greedy descent instead of using the specified metaheuristic. I checked it by using a solution obtained by a greedy descent without initial solution. This solution is close to the best one obtained when using the GLS metaheuristic without initial solution. Yet the solver can not find it because it requires to degrade the solution, which is impossible with a greedy descent.

Test

Environment

OR tools version : 7.4
OS: Ubuntu 18.04 using binaries.

Test samples

Here is the tested code (modified version of the CVRP tutorial code)

// [START program]
// [START import]
#include "ortools/constraint_solver/routing.h"
#include "ortools/constraint_solver/routing_enums.pb.h"
#include "ortools/constraint_solver/routing_index_manager.h"
#include "ortools/constraint_solver/routing_parameters.h"
#include <iterator>
// [END import]

namespace operations_research {
// [START data_model]
struct DataModel {
  const std::vector<std::vector<int64>> distance_matrix{
      {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},
  };
  // [START demands_capacities]
  const std::vector<int64> demands{
      0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8,
  };
  const std::vector<int64> vehicle_capacities{15, 15, 15, 15};
  // [END demands_capacities]
  const int num_vehicles = 4;
  const RoutingIndexManager::NodeIndex depot{0};
};
// [END data_model]

// [START solution_printer]
//! @brief Print the solution.
//! @param[in] data Data of the problem.
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const DataModel &data, const RoutingIndexManager &manager,
                   const RoutingModel &routing, const Assignment &solution) {
  int64 total_distance{0};
  int64 total_load{0};
  for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
    int64 index = routing.Start(vehicle_id);
    LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
    int64 route_distance{0};
    int64 route_load{0};
    std::stringstream route;
    while (routing.IsEnd(index) == false) {
      int64 node_index = manager.IndexToNode(index).value();
      route_load += data.demands[node_index];
      route << node_index << " Load(" << route_load << ") -> ";
      int64 previous_index = index;
      index = solution.Value(routing.NextVar(index));
      route_distance += routing.GetArcCostForVehicle(previous_index, index,
                                                     int64{vehicle_id});
    }
    LOG(INFO) << route.str() << manager.IndexToNode(index).value();
    LOG(INFO) << "Distance of the route: " << route_distance << "m";
    LOG(INFO) << "Load of the route: " << route_load;
    total_distance += route_distance;
    total_load += route_load;
  }
  LOG(INFO) << "Total distance of all routes: " << total_distance << "m";
  LOG(INFO) << "Total load of all routes: " << total_load;
  LOG(INFO) << "";
  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}
// [END solution_printer]

void VrpCapacity() {
  constexpr bool use_initial_solution = true;
  // Instantiate the data problem.
  // [START data]
  DataModel data;
  // [END data]

  // Create Routing Index Manager
  // [START index_manager]
  RoutingIndexManager manager(data.distance_matrix.size(), data.num_vehicles,
                              data.depot);
  // [END index_manager]

  // Create Routing Model.
  // [START routing_model]
  RoutingModel routing(manager);
  // [END routing_model]

  // Create and register a transit callback.
  // [START transit_callback]
  const int transit_callback_index = routing.RegisterTransitCallback(
      [&data, &manager](int64 from_index, int64 to_index) -> int64 {
        // Convert from routing variable Index to distance matrix NodeIndex.
        int from_node = manager.IndexToNode(from_index).value();
        int to_node = manager.IndexToNode(to_index).value();
        return data.distance_matrix[from_node][to_node];
      });
  // [END transit_callback]

  // Define cost of each arc.
  // [START arc_cost]
  routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);
  // [END arc_cost]

  // Add Capacity constraint.
  // [START capacity_constraint]
  const int demand_callback_index = routing.RegisterUnaryTransitCallback(
      [&data, &manager](int64 from_index) -> int64 {
        // Convert from routing variable Index to demand NodeIndex.
        int from_node = manager.IndexToNode(from_index).value();
        return data.demands[from_node];
      });
  routing.AddDimensionWithVehicleCapacity(
      demand_callback_index,   // transit callback index
      int64{0},                // null capacity slack
      data.vehicle_capacities, // vehicle maximum capacities
      true,                    // start cumul to zero
      "Capacity");
  // [END capacity_constraint]

  // Setting first solution heuristic.
  // [START parameters]
  RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
  searchParameters.set_local_search_metaheuristic(
      LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH);
  google::protobuf::Duration *time_limit = new google::protobuf::Duration();
  time_limit->set_seconds(10);
  searchParameters.set_allocated_time_limit(time_limit);
  searchParameters.set_log_search(true);

  // [END parameters]

  // Solve the problem.
  // [START solve]
  const Assignment *solution = nullptr;
  if (use_initial_solution) {
    // Start with an initial solution
    // [START init]
    std::vector<std::vector<int64>> node_solution = {
        {1, 3, 4, 7}, {2, 5, 6, 8}, {9, 10, 13, 15}, {11, 12, 14, 16}};
    // Uncomment to start with a solution close to the best one obtained from
    // the GLS
    //    std::vector<std::vector<int64>> node_solution = {
    //        {1, 4, 3, 15}, {14, 16, 10, 2}, {7, 13, 12, 11}, {9, 8, 6, 5}};
    const Assignment *initial_solution =
        routing.ReadAssignmentFromRoutes(node_solution, true);
    LOG(INFO) << "Initial solution: ";
    PrintSolution(data, manager, routing, *initial_solution);
    // [START init]

    solution = routing.SolveFromAssignmentWithParameters(initial_solution,
                                                         searchParameters);
  } else {
    solution = routing.SolveWithParameters(searchParameters);
  }

  // Print solution on console.
  // [START print_solution]
  if (solution)
    PrintSolution(data, manager, routing, *solution);
  // [END print_solution]
}
} // namespace operations_research

int main(int argc, char **argv) {
  operations_research::VrpCapacity();
  return EXIT_SUCCESS;
}
// [END program]

[ghost]

I think I found out why it does not work.
When calling the ReadAssignmentFromRoutes method, it internally calls QuietCloseModel
https://github.com/google/or-tools/blob/b4298f709f116de08f490ac2bfe5e295fcc91f40/ortools/constraint_solver/routing.cc#L3525-L3528
which calls QuietCloseModelWithParameters(DefaultRoutingSearchParameters()).
https://github.com/google/or-tools/blob/b4298f709f116de08f490ac2bfe5e295fcc91f40/ortools/constraint_solver/routing.cc#L1696-L1698

It means that when we call SolveFromAssignmentWithParameters (ed or SolveWithParameters), the model is already closed so the custom searchParameters is ignored. This explains why a greedy descent is used (default metaheuristic) and no logging is printed.

Note that no warning are displayed because "SolveFromAssignmentWithParameters" calls "QuietCloseModelWithParameters(parameters);" which does nothing if the model is already closed.

The workaround : close the model before calling "ReadAssignmentFromRoutes".

Below is the final code that seems to work. I hope it helped.

// [START program]
// [START import]
#include "ortools/constraint_solver/routing.h"
#include "ortools/constraint_solver/routing_enums.pb.h"
#include "ortools/constraint_solver/routing_index_manager.h"
#include "ortools/constraint_solver/routing_parameters.h"
#include <iterator>
// [END import]

namespace operations_research {
// [START data_model]
struct DataModel {
  const std::vector<std::vector<int64>> distance_matrix{
      {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},
  };
  // [START demands_capacities]
  const std::vector<int64> demands{
      0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8,
  };
  const std::vector<int64> vehicle_capacities{15, 15, 15, 15};
  // [END demands_capacities]
  const int num_vehicles = 4;
  const RoutingIndexManager::NodeIndex depot{0};
};
// [END data_model]

// [START solution_printer]
//! @brief Print the solution.
//! @param[in] data Data of the problem.
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const DataModel &data, const RoutingIndexManager &manager,
                   const RoutingModel &routing, const Assignment &solution) {
  int64 total_distance{0};
  int64 total_load{0};
  for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
    int64 index = routing.Start(vehicle_id);
    LOG(WARNING) << "Route for Vehicle " << vehicle_id << ":";
    int64 route_distance{0};
    int64 route_load{0};
    std::stringstream route;
    while (routing.IsEnd(index) == false) {
      int64 node_index = manager.IndexToNode(index).value();
      route_load += data.demands[node_index];
      route << node_index << " Load(" << route_load << ") -> ";
      int64 previous_index = index;
      index = solution.Value(routing.NextVar(index));
      route_distance += routing.GetArcCostForVehicle(previous_index, index,
                                                     int64{vehicle_id});
    }
    LOG(INFO) << route.str() << manager.IndexToNode(index).value();
    LOG(INFO) << "Distance of the route: " << route_distance << "m";
    LOG(INFO) << "Load of the route: " << route_load;
    total_distance += route_distance;
    total_load += route_load;
  }
  LOG(INFO) << "Total distance of all routes: " << total_distance << "m";
  LOG(INFO) << "Total load of all routes: " << total_load;
  LOG(INFO) << "";
  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}
// [END solution_printer]

void VrpCapacity() {
  constexpr bool use_initial_solution = true;
  // Instantiate the data problem.
  // [START data]
  DataModel data;
  // [END data]

  // Create Routing Index Manager
  // [START index_manager]
  RoutingIndexManager manager(data.distance_matrix.size(), data.num_vehicles,
                              data.depot);
  // [END index_manager]

  // Create Routing Model.
  // [START routing_model]
  RoutingModel routing(manager);
  // [END routing_model]

  // Create and register a transit callback.
  // [START transit_callback]
  const int transit_callback_index = routing.RegisterTransitCallback(
      [&data, &manager](int64 from_index, int64 to_index) -> int64 {
        // Convert from routing variable Index to distance matrix NodeIndex.
        int from_node = manager.IndexToNode(from_index).value();
        int to_node = manager.IndexToNode(to_index).value();
        return data.distance_matrix[from_node][to_node];
      });
  // [END transit_callback]

  // Define cost of each arc.
  // [START arc_cost]
  routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);
  // [END arc_cost]

  // Add Capacity constraint.
  // [START capacity_constraint]
  const int demand_callback_index = routing.RegisterUnaryTransitCallback(
      [&data, &manager](int64 from_index) -> int64 {
        // Convert from routing variable Index to demand NodeIndex.
        int from_node = manager.IndexToNode(from_index).value();
        return data.demands[from_node];
      });
  routing.AddDimensionWithVehicleCapacity(
      demand_callback_index,   // transit callback index
      int64{0},                // null capacity slack
      data.vehicle_capacities, // vehicle maximum capacities
      true,                    // start cumul to zero
      "Capacity");
  // [END capacity_constraint]

  // Setting first solution heuristic.
  // [START parameters]
  RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
  searchParameters.set_local_search_metaheuristic(
      LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH);
  google::protobuf::Duration *time_limit = new google::protobuf::Duration();
  time_limit->set_seconds(1);
  searchParameters.set_allocated_time_limit(time_limit);
  searchParameters.set_log_search(true);

  // Parameters are ignored when using an initial solution if you do not close
  // the model
  routing.CloseModelWithParameters(searchParameters);

  // [END parameters]

  // Solve the problem.
  // [START solve]
  const Assignment *solution = nullptr;
  if (use_initial_solution) {
    // Start with an initial solution
    // [START init]
    //    std::vector<std::vector<int64>> node_solution = {
    //        {1, 3, 4, 7}, {2, 5, 6, 8}, {9, 10, 13, 15}, {11, 12, 14, 16}};
    // Uncomment to start with a solution close to the best one obtained from
    // the GLS
    std::vector<std::vector<int64>> node_solution = {
        {1, 4, 3, 15}, {14, 16, 10, 2}, {7, 13, 12, 11}, {9, 8, 6, 5}};
    const Assignment *initial_solution =
        routing.ReadAssignmentFromRoutes(node_solution, true);
    LOG(INFO) << "Initial solution: ";
    PrintSolution(data, manager, routing, *initial_solution);
    // [START init]

    solution = routing.SolveFromAssignmentWithParameters(initial_solution,
                                                         searchParameters);
  } else {
    solution = routing.SolveWithParameters(searchParameters);
  }

  // Print solution on console.
  // [START print_solution]
  if (solution)
    PrintSolution(data, manager, routing, *solution);
  // [END print_solution]
}
} // namespace operations_research

int main(int argc, char **argv) {
  operations_research::VrpCapacity();
  return EXIT_SUCCESS;
}
// [END program]

[Mizux]

Thanks a lot for your time investigating this bug ! Hope to have time to work on it soon...