SetBreakDistanceDurationOfVehicle leads to failed construction-heuristics (examples/cpp/cvrptw.cc)

[sschnug]

• Version: v9.7
• Language: C++ | bazel
• Routing Solver
• Ubuntu 22.04

I'm trying to make SetBreakDistanceDurationOfVehicle work.

See also: #3898

It seems that there are either some implementation issues or some hidden assumption / limitations i'm not seeing as this functionality always leads to issues.

Let's focus on one of the official examples and enrich it with this feature. We will see, that the solver won't find any solution anymore.

In my opinion, the solver should be able to find a solution (having some assumptions about it's functionality; maybe i'm wrong and there is some simple issue like greedy/backtracking-free construction-heur which might run into trouble as we might need to backtrack one level (to add a slack before we have reached our limit) if we don't check consistency in advance?):

• The break-duration is based on the best-case = 1
• The break-placement freedom is maximized
  • (and we made sure, that there are no transits > break-duration (can only break / add to slack once per transit)
• The orders are all optional
• The horizon in combination with everything else should allow to move unused breaks after the tour
  • Cannot make static set of breaks optional as no incentive to make active -> we allow to move those to the end (which should work)

Reproducible Code

diff --git examples/cpp/cvrptw.cc examples/cpp/cvrptw.cc
index c9aa53597f..ef5cacedbc 100644
--- examples/cpp/cvrptw.cc
+++ examples/cpp/cvrptw.cc
@@ -48,6 +48,10 @@ using operations_research::RoutingNodeIndex;
 using operations_research::RoutingSearchParameters;
 using operations_research::ServiceTimePlusTransition;
 
+ABSL_FLAG(bool, RELAX_CAPACITIES, false, "Use int::max for vehicle-capas?");
+ABSL_FLAG(bool, RELAX_TWS, false, "Skip posting TW-based domain-holes?");
+ABSL_FLAG(bool, RELAX_BREAK_DISTANCE, false, "Skip posting SetBreakDistanceDurationOfVehicle?");
+
 ABSL_FLAG(int, vrp_orders, 100, "Number of nodes in the problem");
 ABSL_FLAG(int, vrp_vehicles, 20, "Number of vehicles in the problem");
 ABSL_FLAG(bool, vrp_use_deterministic_random_seed, false,
@@ -75,7 +79,10 @@ int main(int argc, char** argv) {
   const RoutingIndexManager::NodeIndex kDepot(0);
   RoutingIndexManager manager(absl::GetFlag(FLAGS_vrp_orders) + 1,
                               absl::GetFlag(FLAGS_vrp_vehicles), kDepot);
-  RoutingModel routing(manager);
+
+  auto params = operations_research::DefaultRoutingModelParameters();
+  params.mutable_solver_parameters()->set_print_local_search_profile(true);
+  RoutingModel routing(manager, params);
 
   // Setting up locations.
   const int64_t kXMax = 100000;
@@ -97,7 +104,11 @@ int main(int argc, char** argv) {
   routing.SetArcCostEvaluatorOfAllVehicles(vehicle_cost);
 
   // Adding capacity dimension constraints.
-  const int64_t kVehicleCapacity = 40;
+
+  int64_t kVehicleCapacity = 40;
+  if(absl::GetFlag(FLAGS_RELAX_CAPACITIES))
+    kVehicleCapacity = std::numeric_limits<int64_t>::max();
+
   const int64_t kNullCapacitySlack = 0;
   RandomDemand demand(manager.num_nodes(), kDepot,
                       absl::GetFlag(FLAGS_vrp_use_deterministic_random_seed));
@@ -128,6 +139,48 @@ int main(int argc, char** argv) {
       kHorizon, kHorizon, /*fix_start_cumul_to_zero=*/true, kTime);
   const RoutingDimension& time_dimension = routing.GetDimensionOrDie(kTime);
 
+  // Add vehicle-breaks
+  // ------------------
+  int64_t n_nodes = absl::GetFlag(FLAGS_vrp_orders) + 1;
+  
+  int64_t worst_case_transit_time = -1;
+  for(int64_t i=0; i<n_nodes; ++i)
+    for(int64_t j=0; j<n_nodes; ++j)
+      worst_case_transit_time = std::max(worst_case_transit_time, time.Compute(manager.IndexToNode(i), manager.IndexToNode(j)));
+  LOG(INFO) << "worst_case_transit_time: " << worst_case_transit_time;
+
+  int64_t max_break_distance = worst_case_transit_time;
+  LOG(INFO) << "max_break_distance = worst_case_transit_time: " << max_break_distance;
+
+  int64_t min_break_time = 1;  // as easy as possible
+  LOG(INFO) << "min_break_time: " << min_break_time;
+
+  int64_t n_breaks_needed_max = std::ceil(static_cast<double>(kHorizon) / max_break_distance) - 1;
+  LOG(INFO) << "n_breaks_needed_max: " << n_breaks_needed_max;
+
+  for(unsigned int v=0; v<absl::GetFlag(FLAGS_vrp_vehicles); ++v) {
+    std::vector<operations_research::IntervalVar*> break_intervals;
+
+    for(unsigned int b=0; b<n_breaks_needed_max; ++b) {
+      operations_research::Solver* const solver = routing.solver();
+      operations_research::IntervalVar* const break_interval = solver->MakeIntervalVar(
+          0,              // break could be everywhere
+          kHorizon,       // """
+          min_break_time, 
+          kHorizon,
+          0,              // break could be everywhere
+          kHorizon,       // """
+          false,          // not optional: can always put them after tour
+          absl::StrCat("Break for vehicle ", v));
+      break_intervals.push_back(break_interval);
+    }
+
+    RoutingDimension* time_dimension_mut = routing.GetMutableDimension(kTime);
+    time_dimension_mut->SetBreakIntervalsOfVehicle(break_intervals, v, -1, -1);
+    if(!absl::GetFlag(FLAGS_RELAX_BREAK_DISTANCE))
+      time_dimension_mut->SetBreakDistanceDurationOfVehicle(max_break_distance, min_break_time, v);
+  }
+
   // Adding time windows.
   std::mt19937 randomizer(
       GetSeed(absl::GetFlag(FLAGS_vrp_use_deterministic_random_seed)));
@@ -135,7 +188,8 @@ int main(int argc, char** argv) {
   for (int order = 1; order < manager.num_nodes(); ++order) {
     const int64_t start =
         absl::Uniform<int32_t>(randomizer, 0, kHorizon - kTWDuration);
-    time_dimension.CumulVar(order)->SetRange(start, start + kTWDuration);
+    if(!absl::GetFlag(FLAGS_RELAX_TWS))
+      time_dimension.CumulVar(order)->SetRange(start, start + kTWDuration);
   }
 
   // Adding penalty costs to allow skipping orders.
@@ -165,6 +219,9 @@ int main(int argc, char** argv) {
 
   // Solve, returns a solution if any (owned by RoutingModel).
   RoutingSearchParameters parameters = DefaultRoutingSearchParameters();
+
+  parameters.mutable_time_limit()->set_seconds(10);
+
   CHECK(google::protobuf::TextFormat::MergeFromString(
       absl::GetFlag(FLAGS_routing_search_parameters), &parameters));
   const Assignment* solution = routing.SolveWithParameters(parameters);

Run

bazel run -c opt //examples/cpp:cvrptw -- --v 1 --stderrthreshold 0

I1009 17:03:01.236056  191173 cvrptw.cc:150] worst_case_transit_time: 19744
I1009 17:03:01.236080  191173 cvrptw.cc:153] max_break_distance = worst_case_transit_time: 19744
I1009 17:03:01.236082  191173 cvrptw.cc:156] min_break_time: 1
I1009 17:03:01.236086  191173 cvrptw.cc:159] n_breaks_needed_max: 4

I1009 17:03:11.240680  191173 constraint_solver.cc:2316] First solution statistics:
                  | Time (s)
PATH_CHEAPEST_ARC |  0.0048
Local search filter statistics (PATH_CHEAPEST_ARC):
                          |     Calls |   Rejects | Time (s) | Rejects/s
    DimensionFilter(Time) |       800 |       678 |    0.64  | 1.1e+03
     VariableDomainFilter |       125 |         0 |    0.14  |       0
    VehicleVariableFilter |       124 |         0 |    0.14  |       0
DimensionFilter(Capacity) |       123 |         0 |    0.14  |       0
    PathCumulFilter(Time) |       122 |         0 |    0.14  |       0
      VehicleBreaksFilter |       122 |         0 |    0.14  |       0
                    Total |      1416 |       678 |     1.3  | 5.1e+02

I1009 17:03:11.240817  191173 routing.cc:2658] Objective lower bound: 0
I1009 17:03:11.240863  191173 cvrptw_lib.h:344] Cost 1000000000
Dropped orders: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100

Run + relax vehicle-capacity + relax time-windows

bazel run -c opt //examples/cpp:cvrptw -- --v 1 --stderrthreshold 0 --RELAX_CAPACITIES --RELAX_TWS

I1009 17:04:21.237680  191983 constraint_solver.cc:2316] First solution statistics:
                  | Time (s)
PATH_CHEAPEST_ARC |  0.0065
Local search filter statistics (PATH_CHEAPEST_ARC):
                          |     Calls |   Rejects | Time (s) | Rejects/s
    DimensionFilter(Time) |       211 |        89 |    0.52  | 1.7e+02
     VariableDomainFilter |       125 |         0 |     0.3  |       0
    VehicleVariableFilter |       124 |         0 |     0.3  |       0
DimensionFilter(Capacity) |       123 |         0 |     0.3  |       0
    PathCumulFilter(Time) |       122 |         0 |     0.3  |       0
      VehicleBreaksFilter |       122 |         0 |     0.3  |       0
                    Total |       827 |        89 |       2  |      44

I1009 17:04:21.237773  191983 routing.cc:2658] Objective lower bound: 0
I1009 17:04:21.237805  191983 cvrptw_lib.h:344] Cost 1000000000
Dropped orders: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100

Run + relax SetBreakDistanceDurationOfVehicle

bazel run -c opt //examples/cpp:cvrptw -- --v 1 --stderrthreshold 0 --RELAX_BREAK_DISTANCE

I1009 17:06:10.591750  193120 constraint_solver.cc:2316] First solution statistics:
                  | Time (s)
PATH_CHEAPEST_ARC |  0.0032
Local search operator statistics:
                                          | Neighbors | Filtered | Accepted | Time (s)
                              Relocate<1> |     63633 |       78 |       78 |    0.98
                                    Cross |     27686 |       19 |       19 |     0.7
                                 Exchange |     24355 |        6 |        6 |    0.62
                   RelocateExpensiveChain |     11154 |        0 |        0 |    0.72
                                 OrOpt<1> |      2098 |        1 |        1 |    0.71
                                 OrOpt<2> |      1564 |        0 |        0 |    0.71
                                 OrOpt<3> |      1274 |        0 |        0 |    0.71
                                   TwoOpt |      1148 |        3 |        3 |    0.71
                MakeChainInactiveOperator |      1120 |        0 |        0 |    0.72
                     MakeInactiveOperator |       177 |        0 |        0 |    0.72
                             LinKernighan |         9 |        0 |        0 |     0.7
HeuristicPathLNS(GlobalCheapestInsertion) |         9 |        0 |        0 |    0.39
 HeuristicPathLNS(LocalCheapestInsertion) |         9 |        0 |        0 |    0.39
                             LinKernighan |         7 |        0 |        0 |     0.7
                                    Total |    134243 |      107 |      107 |     9.5
Local search filter statistics:
                          |     Calls |   Rejects | Time (s) | Rejects/s
       SumObjectiveFilter |    134243 |    128982 | 1.5e+03  |      85
    DimensionFilter(Time) |      6067 |      5382 | 1.3e+02  |      43
    DimensionFilter(Time) |      3842 |      3677 |      48  |      77
DimensionFilter(Capacity) |      2206 |      1522 |      47  |      32
     VariableDomainFilter |      1179 |      1060 |      18  |      59
DimensionFilter(Capacity) |       578 |       417 |     6.7  |      62
     VariableDomainFilter |       381 |         0 |     6.1  |       0
    VehicleVariableFilter |       379 |         0 |     6.1  |       0
    PathCumulFilter(Time) |       376 |         0 |     6.1  |       0
      VehicleBreaksFilter |       376 |         0 |     6.1  |       0
    NodeDisjunctionFilter |       112 |         0 |    0.72  |       0
    VehicleVariableFilter |       110 |         0 |    0.71  |       0
    PathCumulFilter(Time) |       107 |         0 |     0.7  |       0
      VehicleBreaksFilter |       107 |         0 |    0.71  |       0
                    Total |    150063 |    141040 | 1.8e+03  |      79

I1009 17:06:10.591798  193120 routing.cc:2658] Objective lower bound: 0
I1009 17:06:10.591835  193120 cvrptw_lib.h:344] Cost 2663958

no dropped orders

Remarks

It's really hard to make sense out of it.

• LS-Statistic don't even count vehicle-breaks filter rejections
  • I even have instances where there is no solution found and there isn't a single rejection counted
• Propagation profiling is not working: routing-solver / constraint-solver: profile_propagation crashes (on official example) #3912

With FLAGS_v=3, one sees a huge amount of:

I1009 17:15:31.252066 196860 constraint_solver.cc:103] Fail

but without instrumentalization of or-tools itself it's hard to find the origin of those: Callers of Solver::Fail()