1 // Copyright 2010-2021 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 //     http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #include "ortools/constraint_solver/routing_parameters.h"
15 
16 #include <cstdint>
17 
18 #include "absl/strings/str_cat.h"
19 #include "absl/time/time.h"
20 #include "google/protobuf/descriptor.h"
21 #include "google/protobuf/duration.pb.h"
22 #include "google/protobuf/message.h"
23 #include "google/protobuf/text_format.h"
24 #include "ortools/base/logging.h"
25 #include "ortools/base/protoutil.h"
26 #include "ortools/constraint_solver/constraint_solver.h"
27 #include "ortools/constraint_solver/routing_enums.pb.h"
28 #include "ortools/constraint_solver/solver_parameters.pb.h"
29 #include "ortools/sat/sat_parameters.pb.h"
30 #include "ortools/util/optional_boolean.pb.h"
31 
32 namespace operations_research {
33 
DefaultRoutingModelParameters()34 RoutingModelParameters DefaultRoutingModelParameters() {
35   RoutingModelParameters parameters;
36   ConstraintSolverParameters* const solver_parameters =
37       parameters.mutable_solver_parameters();
38   *solver_parameters = Solver::DefaultSolverParameters();
39   solver_parameters->set_compress_trail(
40       ConstraintSolverParameters::COMPRESS_WITH_ZLIB);
41   solver_parameters->set_skip_locally_optimal_paths(true);
42   parameters.set_reduce_vehicle_cost_model(true);
43   return parameters;
44 }
45 
46 // static
DefaultRoutingSearchParameters()47 RoutingSearchParameters DefaultRoutingSearchParameters() {
48   static const char* const kSearchParameters =
49       "first_solution_strategy: AUTOMATIC "
50       "use_unfiltered_first_solution_strategy: false "
51       "savings_neighbors_ratio: 1 "
52       "savings_max_memory_usage_bytes: 6e9 "
53       "savings_add_reverse_arcs: false "
54       "savings_arc_coefficient: 1 "
55       "savings_parallel_routes: false "
56       "cheapest_insertion_farthest_seeds_ratio: 0 "
57       "cheapest_insertion_first_solution_neighbors_ratio: 1 "
58       "cheapest_insertion_first_solution_min_neighbors: 1 "
59       "cheapest_insertion_ls_operator_neighbors_ratio: 1 "
60       "cheapest_insertion_ls_operator_min_neighbors: 1 "
61       "cheapest_insertion_first_solution_use_neighbors_ratio_for_"
62       "initialization: false "
63       "cheapest_insertion_add_unperformed_entries: false "
64       "local_search_operators {"
65       "  use_relocate: BOOL_TRUE"
66       "  use_relocate_pair: BOOL_TRUE"
67       "  use_light_relocate_pair: BOOL_TRUE"
68       "  use_relocate_subtrip: BOOL_TRUE"
69       "  use_relocate_neighbors: BOOL_FALSE"
70       "  use_exchange: BOOL_TRUE"
71       "  use_exchange_pair: BOOL_TRUE"
72       "  use_exchange_subtrip: BOOL_TRUE"
73       "  use_cross: BOOL_TRUE"
74       "  use_cross_exchange: BOOL_FALSE"
75       "  use_relocate_expensive_chain: BOOL_TRUE"
76       "  use_two_opt: BOOL_TRUE"
77       "  use_or_opt: BOOL_TRUE"
78       "  use_lin_kernighan: BOOL_TRUE"
79       "  use_tsp_opt: BOOL_FALSE"
80       "  use_make_active: BOOL_TRUE"
81       "  use_relocate_and_make_active: BOOL_FALSE"  // costly if true by default
82       "  use_make_inactive: BOOL_TRUE"
83       "  use_make_chain_inactive: BOOL_FALSE"
84       "  use_swap_active: BOOL_TRUE"
85       "  use_extended_swap_active: BOOL_FALSE"
86       "  use_node_pair_swap_active: BOOL_TRUE"
87       "  use_path_lns: BOOL_FALSE"
88       "  use_full_path_lns: BOOL_FALSE"
89       "  use_tsp_lns: BOOL_FALSE"
90       "  use_inactive_lns: BOOL_FALSE"
91       "  use_global_cheapest_insertion_path_lns: BOOL_TRUE"
92       "  use_local_cheapest_insertion_path_lns: BOOL_TRUE"
93       "  use_relocate_path_global_cheapest_insertion_insert_unperformed: "
94       "BOOL_TRUE"
95       "  use_global_cheapest_insertion_expensive_chain_lns: BOOL_FALSE"
96       "  use_local_cheapest_insertion_expensive_chain_lns: BOOL_FALSE"
97       "  use_global_cheapest_insertion_close_nodes_lns: BOOL_FALSE"
98       "  use_local_cheapest_insertion_close_nodes_lns: BOOL_FALSE"
99       "}"
100       "use_multi_armed_bandit_concatenate_operators: false "
101       "multi_armed_bandit_compound_operator_memory_coefficient: 0.04 "
102       "multi_armed_bandit_compound_operator_exploration_coefficient: 1e12 "
103       "relocate_expensive_chain_num_arcs_to_consider: 4 "
104       "heuristic_expensive_chain_lns_num_arcs_to_consider: 4 "
105       "heuristic_close_nodes_lns_num_nodes: 5 "
106       "local_search_metaheuristic: AUTOMATIC "
107       "guided_local_search_lambda_coefficient: 0.1 "
108       "use_depth_first_search: false "
109       "use_cp: BOOL_TRUE "
110       "use_cp_sat: BOOL_FALSE "
111       "use_generalized_cp_sat: BOOL_FALSE "
112       "sat_parameters { linearization_level: 2 num_search_workers: 1 } "
113       "continuous_scheduling_solver: GLOP "
114       "mixed_integer_scheduling_solver: CP_SAT "
115       "optimization_step: 0.0 "
116       "number_of_solutions_to_collect: 1 "
117       // No "time_limit" by default.
118       "solution_limit: 0x7fffffffffffffff "             // kint64max
119       "lns_time_limit: { seconds:0 nanos:100000000 } "  // 0.1s
120       "use_full_propagation: false "
121       "log_search: false "
122       "log_cost_scaling_factor: 1.0 "
123       "log_cost_offset: 0.0";
124   RoutingSearchParameters parameters;
125   if (!google::protobuf::TextFormat::ParseFromString(kSearchParameters,
126                                                      &parameters)) {
127     LOG(DFATAL) << "Unsupported default search parameters: "
128                 << kSearchParameters;
129   }
130   const std::string error = FindErrorInRoutingSearchParameters(parameters);
131   LOG_IF(DFATAL, !error.empty())
132       << "The default search parameters aren't valid: " << error;
133   return parameters;
134 }
135 
136 namespace {
IsValidNonNegativeDuration(const google::protobuf::Duration & d)137 bool IsValidNonNegativeDuration(const google::protobuf::Duration& d) {
138   const auto status_or_duration = util_time::DecodeGoogleApiProto(d);
139   return status_or_duration.ok() &&
140          status_or_duration.value() >= absl::ZeroDuration();
141 }
142 }  // namespace
143 
FindErrorInRoutingSearchParameters(const RoutingSearchParameters & search_parameters)144 std::string FindErrorInRoutingSearchParameters(
145     const RoutingSearchParameters& search_parameters) {
146   using absl::StrCat;
147   // Check that all local search operators are set to either BOOL_TRUE or
148   // BOOL_FALSE (and not BOOL_UNSPECIFIED).
149   {
150     using Reflection = google::protobuf::Reflection;
151     using Descriptor = google::protobuf::Descriptor;
152     using FieldDescriptor = google::protobuf::FieldDescriptor;
153     const RoutingSearchParameters::LocalSearchNeighborhoodOperators& operators =
154         search_parameters.local_search_operators();
155     const Reflection* ls_reflection = operators.GetReflection();
156     const Descriptor* ls_descriptor = operators.GetDescriptor();
157     for (int /*this is NOT the field's tag number*/ field_index = 0;
158          field_index < ls_descriptor->field_count(); ++field_index) {
159       const FieldDescriptor* field = ls_descriptor->field(field_index);
160       if (field->type() != FieldDescriptor::TYPE_ENUM ||
161           field->enum_type() != OptionalBoolean_descriptor()) {
162         DLOG(FATAL)
163             << "In RoutingSearchParameters::LocalSearchNeighborhoodOperators,"
164             << " field '" << field->name() << "' is not an OptionalBoolean.";
165         return "The file 'routing_search_parameters.proto' itself is invalid!";
166       }
167       const int value = ls_reflection->GetEnum(operators, field)->number();
168       if (!OptionalBoolean_IsValid(value) || value == 0) {
169         return StrCat("local_search_neighborhood_operator.", field->name(),
170                       " should be set to BOOL_TRUE or BOOL_FALSE instead of ",
171                       OptionalBoolean_Name(static_cast<OptionalBoolean>(value)),
172                       " (value: ", value, ")");
173       }
174     }
175   }
176   {
177     const double ratio = search_parameters.savings_neighbors_ratio();
178     if (std::isnan(ratio) || ratio <= 0 || ratio > 1) {
179       return StrCat("Invalid savings_neighbors_ratio:", ratio);
180     }
181   }
182   {
183     const double max_memory =
184         search_parameters.savings_max_memory_usage_bytes();
185     if (std::isnan(max_memory) || max_memory <= 0 || max_memory > 1e10) {
186       return StrCat("Invalid savings_max_memory_usage_bytes: ", max_memory);
187     }
188   }
189   {
190     const double coefficient = search_parameters.savings_arc_coefficient();
191     if (std::isnan(coefficient) || coefficient <= 0 ||
192         std::isinf(coefficient)) {
193       return StrCat("Invalid savings_arc_coefficient:", coefficient);
194     }
195   }
196   {
197     const double ratio =
198         search_parameters.cheapest_insertion_farthest_seeds_ratio();
199     if (std::isnan(ratio) || ratio < 0 || ratio > 1) {
200       return StrCat("Invalid cheapest_insertion_farthest_seeds_ratio:", ratio);
201     }
202   }
203   {
204     const double ratio =
205         search_parameters.cheapest_insertion_first_solution_neighbors_ratio();
206     if (std::isnan(ratio) || ratio <= 0 || ratio > 1) {
207       return StrCat(
208           "Invalid cheapest_insertion_first_solution_neighbors_ratio: ", ratio);
209     }
210   }
211   {
212     const int32_t min_neighbors =
213         search_parameters.cheapest_insertion_first_solution_min_neighbors();
214     if (min_neighbors < 1) {
215       return StrCat("Invalid cheapest_insertion_first_solution_min_neighbors: ",
216                     min_neighbors, ". Must be greater or equal to 1.");
217     }
218   }
219   {
220     const double ratio =
221         search_parameters.cheapest_insertion_ls_operator_neighbors_ratio();
222     if (std::isnan(ratio) || ratio <= 0 || ratio > 1) {
223       return StrCat("Invalid cheapest_insertion_ls_operator_neighbors_ratio: ",
224                     ratio);
225     }
226   }
227   {
228     const int32_t min_neighbors =
229         search_parameters.cheapest_insertion_ls_operator_min_neighbors();
230     if (min_neighbors < 1) {
231       return StrCat("Invalid cheapest_insertion_ls_operator_min_neighbors: ",
232                     min_neighbors, ". Must be greater or equal to 1.");
233     }
234   }
235   {
236     const int32_t num_arcs =
237         search_parameters.relocate_expensive_chain_num_arcs_to_consider();
238     if (num_arcs < 2 || num_arcs > 1e6) {
239       return StrCat("Invalid relocate_expensive_chain_num_arcs_to_consider: ",
240                     num_arcs, ". Must be between 2 and 10^6 (included).");
241     }
242   }
243   {
244     const int32_t num_arcs =
245         search_parameters.heuristic_expensive_chain_lns_num_arcs_to_consider();
246     if (num_arcs < 2 || num_arcs > 1e6) {
247       return StrCat(
248           "Invalid heuristic_expensive_chain_lns_num_arcs_to_consider: ",
249           num_arcs, ". Must be between 2 and 10^6 (included).");
250     }
251   }
252   {
253     const int32_t num_nodes =
254         search_parameters.heuristic_close_nodes_lns_num_nodes();
255     if (num_nodes < 0 || num_nodes > 1e4) {
256       return StrCat("Invalid heuristic_close_nodes_lns_num_nodes: ", num_nodes,
257                     ". Must be between 0 and 10000 (included).");
258     }
259   }
260   {
261     const double gls_coefficient =
262         search_parameters.guided_local_search_lambda_coefficient();
263     if (std::isnan(gls_coefficient) || gls_coefficient < 0 ||
264         std::isinf(gls_coefficient)) {
265       return StrCat("Invalid guided_local_search_lambda_coefficient: ",
266                     gls_coefficient);
267     }
268   }
269   {
270     const double step = search_parameters.optimization_step();
271     if (std::isnan(step) || step < 0.0) {
272       return StrCat("Invalid optimization_step: ", step);
273     }
274   }
275   {
276     const int32_t num = search_parameters.number_of_solutions_to_collect();
277     if (num < 1) return StrCat("Invalid number_of_solutions_to_collect:", num);
278   }
279   {
280     const int64_t lim = search_parameters.solution_limit();
281     if (lim < 1) return StrCat("Invalid solution_limit:", lim);
282   }
283   if (!IsValidNonNegativeDuration(search_parameters.time_limit())) {
284     return "Invalid time_limit: " +
285            search_parameters.time_limit().ShortDebugString();
286   }
287   if (!IsValidNonNegativeDuration(search_parameters.lns_time_limit())) {
288     return "Invalid lns_time_limit: " +
289            search_parameters.lns_time_limit().ShortDebugString();
290   }
291   if (!FirstSolutionStrategy::Value_IsValid(
292           search_parameters.first_solution_strategy())) {
293     return StrCat("Invalid first_solution_strategy: ",
294                   search_parameters.first_solution_strategy());
295   }
296   if (!LocalSearchMetaheuristic::Value_IsValid(
297           search_parameters.local_search_metaheuristic())) {
298     return StrCat("Invalid metaheuristic: ",
299                   search_parameters.local_search_metaheuristic());
300   }
301 
302   const double scaling_factor = search_parameters.log_cost_scaling_factor();
303   if (scaling_factor == 0 || std::isnan(scaling_factor) ||
304       std::isinf(scaling_factor)) {
305     return StrCat("Invalid value for log_cost_scaling_factor: ",
306                   scaling_factor);
307   }
308   const double offset = search_parameters.log_cost_offset();
309   if (std::isnan(offset) || std::isinf(offset)) {
310     return StrCat("Invalid value for log_cost_offset: ", offset);
311   }
312   const RoutingSearchParameters::SchedulingSolver continuous_scheduling_solver =
313       search_parameters.continuous_scheduling_solver();
314   if (continuous_scheduling_solver == RoutingSearchParameters::UNSET ||
315       continuous_scheduling_solver == RoutingSearchParameters::CP_SAT) {
316     return StrCat("Invalid value for continuous_scheduling_solver: ",
317                   RoutingSearchParameters::SchedulingSolver_Name(
318                       continuous_scheduling_solver));
319   }
320   const RoutingSearchParameters::SchedulingSolver
321       mixed_integer_scheduling_solver =
322           search_parameters.mixed_integer_scheduling_solver();
323   if (mixed_integer_scheduling_solver == RoutingSearchParameters::UNSET) {
324     return StrCat("Invalid value for mixed_integer_scheduling_solver: ",
325                   RoutingSearchParameters::SchedulingSolver_Name(
326                       mixed_integer_scheduling_solver));
327   }
328 
329   if (search_parameters.has_improvement_limit_parameters()) {
330     const double improvement_rate_coefficient =
331         search_parameters.improvement_limit_parameters()
332             .improvement_rate_coefficient();
333     if (std::isnan(improvement_rate_coefficient) ||
334         improvement_rate_coefficient <= 0) {
335       return StrCat(
336           "Invalid value for "
337           "improvement_limit_parameters.improvement_rate_coefficient: ",
338           improvement_rate_coefficient);
339     }
340 
341     const int32_t improvement_rate_solutions_distance =
342         search_parameters.improvement_limit_parameters()
343             .improvement_rate_solutions_distance();
344     if (improvement_rate_solutions_distance <= 0) {
345       return StrCat(
346           "Invalid value for "
347           "improvement_limit_parameters.improvement_rate_solutions_distance: ",
348           improvement_rate_solutions_distance);
349     }
350   }
351 
352   {
353     const double memory_coefficient =
354         search_parameters
355             .multi_armed_bandit_compound_operator_memory_coefficient();
356     if (std::isnan(memory_coefficient) || memory_coefficient < 0 ||
357         memory_coefficient > 1) {
358       return StrCat(
359           "Invalid value for "
360           "multi_armed_bandit_compound_operator_memory_coefficient: ",
361           memory_coefficient);
362     }
363   }
364   {
365     const double exploration_coefficient =
366         search_parameters
367             .multi_armed_bandit_compound_operator_exploration_coefficient();
368     if (std::isnan(exploration_coefficient) || exploration_coefficient < 0) {
369       return StrCat(
370           "Invalid value for "
371           "multi_armed_bandit_compound_operator_exploration_coefficient: ",
372           exploration_coefficient);
373     }
374   }
375 
376   {
377     const sat::SatParameters& sat_parameters =
378         search_parameters.sat_parameters();
379     if (sat_parameters.enumerate_all_solutions() &&
380         (sat_parameters.num_search_workers() > 1 ||
381          sat_parameters.interleave_search())) {
382       return "sat_parameters.enumerate_all_solutions cannot be true in parallel"
383              " search";
384     }
385   }
386 
387   return "";  // = Valid (No error).
388 }
389 
390 }  // namespace operations_research
391