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 ¶meters)) {
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