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 <algorithm>
15 #include <cstdint>
16 #include <functional>
17 #include <limits>
18 #include <map>
19 #include <memory>
20 #include <utility>
21 #include <vector>
22
23 #include "absl/container/flat_hash_map.h"
24 #include "absl/time/time.h"
25 #include "ortools/base/integral_types.h"
26 #include "ortools/base/logging.h"
27 #include "ortools/base/map_util.h"
28 #include "ortools/constraint_solver/constraint_solver.h"
29 #include "ortools/constraint_solver/routing.h"
30 #include "ortools/constraint_solver/routing_parameters.pb.h"
31 #include "ortools/constraint_solver/routing_types.h"
32 #include "ortools/sat/cp_model.pb.h"
33 #include "ortools/sat/cp_model_solver.h"
34 #include "ortools/sat/integer.h"
35 #include "ortools/sat/model.h"
36 #include "ortools/sat/sat_parameters.pb.h"
37 #include "ortools/util/optional_boolean.pb.h"
38 #include "ortools/util/saturated_arithmetic.h"
39
40 namespace operations_research {
41 namespace sat {
42 namespace {
43
44 // As of 07/2019, TSPs and VRPs with homogeneous fleets of vehicles are
45 // supported.
46 // TODO(user): Support any type of constraints.
47 // TODO(user): Make VRPs properly support optional nodes.
RoutingModelCanBeSolvedBySat(const RoutingModel & model)48 bool RoutingModelCanBeSolvedBySat(const RoutingModel& model) {
49 return model.GetVehicleClassesCount() == 1;
50 }
51
52 // Adds an integer variable to a CpModelProto, returning its index in the proto.
AddVariable(CpModelProto * cp_model,int64_t lb,int64_t ub)53 int AddVariable(CpModelProto* cp_model, int64_t lb, int64_t ub) {
54 const int index = cp_model->variables_size();
55 IntegerVariableProto* const var = cp_model->add_variables();
56 var->add_domain(lb);
57 var->add_domain(ub);
58 return index;
59 }
60
61 // Adds a linear constraint, enforcing
62 // enforcement_literals -> lower_bound <= sum variable * coeff <= upper_bound.
AddLinearConstraint(CpModelProto * cp_model,int64_t lower_bound,int64_t upper_bound,const std::vector<std::pair<int,double>> & variable_coeffs,const std::vector<int> & enforcement_literals)63 void AddLinearConstraint(
64 CpModelProto* cp_model, int64_t lower_bound, int64_t upper_bound,
65 const std::vector<std::pair<int, double>>& variable_coeffs,
66 const std::vector<int>& enforcement_literals) {
67 CHECK_LE(lower_bound, upper_bound);
68 ConstraintProto* ct = cp_model->add_constraints();
69 for (const int enforcement_literal : enforcement_literals) {
70 ct->add_enforcement_literal(enforcement_literal);
71 }
72 LinearConstraintProto* arg = ct->mutable_linear();
73 arg->add_domain(lower_bound);
74 arg->add_domain(upper_bound);
75 for (const auto [var, coeff] : variable_coeffs) {
76 arg->add_vars(var);
77 arg->add_coeffs(coeff);
78 }
79 }
80
81 // Adds a linear constraint, enforcing
82 // lower_bound <= sum variable * coeff <= upper_bound.
AddLinearConstraint(CpModelProto * cp_model,int64_t lower_bound,int64_t upper_bound,const std::vector<std::pair<int,double>> & variable_coeffs)83 void AddLinearConstraint(
84 CpModelProto* cp_model, int64_t lower_bound, int64_t upper_bound,
85 const std::vector<std::pair<int, double>>& variable_coeffs) {
86 AddLinearConstraint(cp_model, lower_bound, upper_bound, variable_coeffs, {});
87 }
88
89 // Returns the unique depot node used in the CP-SAT models (as of 01/2020).
GetDepotFromModel(const RoutingModel & model)90 int64_t GetDepotFromModel(const RoutingModel& model) { return model.Start(0); }
91
92 // Structure to keep track of arcs created.
93 struct Arc {
94 int tail;
95 int head;
96
operator ==(const Arc & a,const Arc & b)97 friend bool operator==(const Arc& a, const Arc& b) {
98 return a.tail == b.tail && a.head == b.head;
99 }
operator !=(const Arc & a,const Arc & b)100 friend bool operator!=(const Arc& a, const Arc& b) { return !(a == b); }
operator <(const Arc & a,const Arc & b)101 friend bool operator<(const Arc& a, const Arc& b) {
102 return a.tail == b.tail ? a.head < b.head : a.tail < b.tail;
103 }
operator <<(std::ostream & strm,const Arc & arc)104 friend std::ostream& operator<<(std::ostream& strm, const Arc& arc) {
105 return strm << "{" << arc.tail << ", " << arc.head << "}";
106 }
107 template <typename H>
AbslHashValue(H h,const Arc & a)108 friend H AbslHashValue(H h, const Arc& a) {
109 return H::combine(std::move(h), a.tail, a.head);
110 }
111 };
112
113 using ArcVarMap = std::map<Arc, int>; // needs to be stable when iterating
114
115 // Adds all dimensions to a CpModelProto. Only adds path cumul constraints and
116 // cumul bounds.
AddDimensions(const RoutingModel & model,const ArcVarMap & arc_vars,CpModelProto * cp_model)117 void AddDimensions(const RoutingModel& model, const ArcVarMap& arc_vars,
118 CpModelProto* cp_model) {
119 for (const RoutingDimension* dimension : model.GetDimensions()) {
120 // Only a single vehicle class.
121 const RoutingModel::TransitCallback2& transit =
122 dimension->transit_evaluator(0);
123 std::vector<int> cumuls(dimension->cumuls().size(), -1);
124 const int64_t min_start = dimension->cumuls()[model.Start(0)]->Min();
125 const int64_t max_end = std::min(dimension->cumuls()[model.End(0)]->Max(),
126 dimension->vehicle_capacities()[0]);
127 for (int i = 0; i < cumuls.size(); ++i) {
128 if (model.IsStart(i) || model.IsEnd(i)) continue;
129 // Reducing bounds supposing the triangular inequality.
130 const int64_t cumul_min =
131 std::max(sat::kMinIntegerValue.value(),
132 std::max(dimension->cumuls()[i]->Min(),
133 CapAdd(transit(model.Start(0), i), min_start)));
134 const int64_t cumul_max =
135 std::min(sat::kMaxIntegerValue.value(),
136 std::min(dimension->cumuls()[i]->Max(),
137 CapSub(max_end, transit(i, model.End(0)))));
138 cumuls[i] = AddVariable(cp_model, cumul_min, cumul_max);
139 }
140 for (const auto arc_var : arc_vars) {
141 const int tail = arc_var.first.tail;
142 const int head = arc_var.first.head;
143 if (tail == head || model.IsStart(tail) || model.IsStart(head)) continue;
144 // arc[tail][head] -> cumuls[head] >= cumuls[tail] + transit.
145 // This is a relaxation of the model as it does not consider slack max.
146 AddLinearConstraint(
147 cp_model, transit(tail, head), std::numeric_limits<int64_t>::max(),
148 {{cumuls[head], 1}, {cumuls[tail], -1}}, {arc_var.second});
149 }
150 }
151 }
152
CreateRanks(const RoutingModel & model,const ArcVarMap & arc_vars,CpModelProto * cp_model)153 std::vector<int> CreateRanks(const RoutingModel& model,
154 const ArcVarMap& arc_vars,
155 CpModelProto* cp_model) {
156 const int depot = GetDepotFromModel(model);
157 const int size = model.Size() + model.vehicles();
158 const int rank_size = model.Size() - model.vehicles();
159 std::vector<int> ranks(size, -1);
160 for (int i = 0; i < size; ++i) {
161 if (model.IsStart(i) || model.IsEnd(i)) continue;
162 ranks[i] = AddVariable(cp_model, 0, rank_size);
163 }
164 ranks[depot] = AddVariable(cp_model, 0, 0);
165 for (const auto arc_var : arc_vars) {
166 const int tail = arc_var.first.tail;
167 const int head = arc_var.first.head;
168 if (tail == head || head == depot) continue;
169 // arc[tail][head] -> ranks[head] == ranks[tail] + 1.
170 AddLinearConstraint(cp_model, 1, 1, {{ranks[head], 1}, {ranks[tail], -1}},
171 {arc_var.second});
172 }
173 return ranks;
174 }
175
176 // Vehicle variables do not actually represent the index of the vehicle
177 // performing a node, but we ensure that the values of two vehicle variables
178 // are the same if and only if the corresponding nodes are served by the same
179 // vehicle.
CreateVehicleVars(const RoutingModel & model,const ArcVarMap & arc_vars,CpModelProto * cp_model)180 std::vector<int> CreateVehicleVars(const RoutingModel& model,
181 const ArcVarMap& arc_vars,
182 CpModelProto* cp_model) {
183 const int depot = GetDepotFromModel(model);
184 const int size = model.Size() + model.vehicles();
185 std::vector<int> vehicles(size, -1);
186 for (int i = 0; i < size; ++i) {
187 if (model.IsStart(i) || model.IsEnd(i)) continue;
188 vehicles[i] = AddVariable(cp_model, 0, size - 1);
189 }
190 for (const auto arc_var : arc_vars) {
191 const int tail = arc_var.first.tail;
192 const int head = arc_var.first.head;
193 if (tail == head || head == depot) continue;
194 if (tail == depot) {
195 // arc[depot][head] -> vehicles[head] == head.
196 AddLinearConstraint(cp_model, head, head, {{vehicles[head], 1}},
197 {arc_var.second});
198 continue;
199 }
200 // arc[tail][head] -> vehicles[head] == vehicles[tail].
201 AddLinearConstraint(cp_model, 0, 0,
202 {{vehicles[head], 1}, {vehicles[tail], -1}},
203 {arc_var.second});
204 }
205 return vehicles;
206 }
207
AddPickupDeliveryConstraints(const RoutingModel & model,const ArcVarMap & arc_vars,CpModelProto * cp_model)208 void AddPickupDeliveryConstraints(const RoutingModel& model,
209 const ArcVarMap& arc_vars,
210 CpModelProto* cp_model) {
211 if (model.GetPickupAndDeliveryPairs().empty()) return;
212 const std::vector<int> ranks = CreateRanks(model, arc_vars, cp_model);
213 const std::vector<int> vehicles =
214 CreateVehicleVars(model, arc_vars, cp_model);
215 for (const auto& pairs : model.GetPickupAndDeliveryPairs()) {
216 const int64_t pickup = pairs.first[0];
217 const int64_t delivery = pairs.second[0];
218 // ranks[pickup] + 1 <= ranks[delivery].
219 AddLinearConstraint(cp_model, 1, std::numeric_limits<int64_t>::max(),
220 {{ranks[delivery], 1}, {ranks[pickup], -1}});
221 // vehicles[pickup] == vehicles[delivery]
222 AddLinearConstraint(cp_model, 0, 0,
223 {{vehicles[delivery], 1}, {vehicles[pickup], -1}});
224 }
225 }
226
227 // Converts a RoutingModel to CpModelProto for models with multiple vehicles.
228 // All non-start/end nodes have the same index in both models. Start/end nodes
229 // map to a single depot index; its value is arbitrarly the index of the start
230 // node of the first vehicle in the RoutingModel.
231 // The map between CPModelProto arcs and their corresponding arc variable is
232 // returned.
PopulateMultiRouteModelFromRoutingModel(const RoutingModel & model,CpModelProto * cp_model)233 ArcVarMap PopulateMultiRouteModelFromRoutingModel(const RoutingModel& model,
234 CpModelProto* cp_model) {
235 ArcVarMap arc_vars;
236 const int num_nodes = model.Nexts().size();
237 const int depot = GetDepotFromModel(model);
238
239 // Create "arc" variables and set their cost.
240 for (int tail = 0; tail < num_nodes; ++tail) {
241 const int tail_index = model.IsStart(tail) ? depot : tail;
242 std::unique_ptr<IntVarIterator> iter(
243 model.NextVar(tail)->MakeDomainIterator(false));
244 for (int head : InitAndGetValues(iter.get())) {
245 // Vehicle start and end nodes are represented as a single node in the
246 // CP-SAT model. We choose the start index of the first vehicle to
247 // represent both. We can also skip any head representing a vehicle start
248 // as the CP solver will reject those.
249 if (model.IsStart(head)) continue;
250 const int head_index = model.IsEnd(head) ? depot : head;
251 if (head_index == tail_index && head_index == depot) continue;
252 const int64_t cost = tail != head ? model.GetHomogeneousCost(tail, head)
253 : model.UnperformedPenalty(tail);
254 if (cost == std::numeric_limits<int64_t>::max()) continue;
255 const Arc arc = {tail_index, head_index};
256 if (gtl::ContainsKey(arc_vars, arc)) continue;
257 const int index = AddVariable(cp_model, 0, 1);
258 gtl::InsertOrDie(&arc_vars, arc, index);
259 cp_model->mutable_objective()->add_vars(index);
260 cp_model->mutable_objective()->add_coeffs(cost);
261 }
262 }
263
264 // Limit the number of routes to the maximum number of vehicles.
265 {
266 std::vector<std::pair<int, double>> variable_coeffs;
267 for (int node = 0; node < num_nodes; ++node) {
268 if (model.IsStart(node) || model.IsEnd(node)) continue;
269 int* const var = gtl::FindOrNull(arc_vars, {depot, node});
270 if (var == nullptr) continue;
271 variable_coeffs.push_back({*var, 1});
272 }
273 AddLinearConstraint(
274 cp_model, 0,
275 std::min(model.vehicles(), model.GetMaximumNumberOfActiveVehicles()),
276 variable_coeffs);
277 }
278
279 AddPickupDeliveryConstraints(model, arc_vars, cp_model);
280
281 AddDimensions(model, arc_vars, cp_model);
282
283 // Create Routes constraint, ensuring circuits from and to the depot.
284 // This one is a bit tricky, because we need to remap the depot to zero.
285 // TODO(user): Make Routes constraints support optional nodes.
286 RoutesConstraintProto* routes_ct =
287 cp_model->add_constraints()->mutable_routes();
288 for (const auto arc_var : arc_vars) {
289 const int tail = arc_var.first.tail;
290 const int head = arc_var.first.head;
291 routes_ct->add_tails(tail == 0 ? depot : tail == depot ? 0 : tail);
292 routes_ct->add_heads(head == 0 ? depot : head == depot ? 0 : head);
293 routes_ct->add_literals(arc_var.second);
294 }
295
296 // Add demands and capacities to improve the LP relaxation and cuts. These are
297 // based on the first "unary" dimension in the model if it exists.
298 // TODO(user): We might want to try to get demand lower bounds from
299 // non-unary dimensions if no unary exist.
300 const RoutingDimension* master_dimension = nullptr;
301 for (const RoutingDimension* dimension : model.GetDimensions()) {
302 // Only a single vehicle class is supported.
303 if (dimension->GetUnaryTransitEvaluator(0) != nullptr) {
304 master_dimension = dimension;
305 break;
306 }
307 }
308 if (master_dimension != nullptr) {
309 const RoutingModel::TransitCallback1& transit =
310 master_dimension->GetUnaryTransitEvaluator(0);
311 for (int node = 0; node < num_nodes; ++node) {
312 // Tricky: demand is added for all nodes in the sat model; this means
313 // start/end nodes other than the one used for the depot must be ignored.
314 if (!model.IsEnd(node) && (!model.IsStart(node) || node == depot)) {
315 routes_ct->add_demands(transit(node));
316 }
317 }
318 DCHECK_EQ(routes_ct->demands_size(), num_nodes + 1 - model.vehicles());
319 routes_ct->set_capacity(master_dimension->vehicle_capacities()[0]);
320 }
321 return arc_vars;
322 }
323
324 // Converts a RoutingModel with a single vehicle to a CpModelProto.
325 // The mapping between CPModelProto arcs and their corresponding arc variables
326 // is returned.
PopulateSingleRouteModelFromRoutingModel(const RoutingModel & model,CpModelProto * cp_model)327 ArcVarMap PopulateSingleRouteModelFromRoutingModel(const RoutingModel& model,
328 CpModelProto* cp_model) {
329 ArcVarMap arc_vars;
330 const int num_nodes = model.Nexts().size();
331 CircuitConstraintProto* circuit =
332 cp_model->add_constraints()->mutable_circuit();
333 for (int tail = 0; tail < num_nodes; ++tail) {
334 std::unique_ptr<IntVarIterator> iter(
335 model.NextVar(tail)->MakeDomainIterator(false));
336 for (int head : InitAndGetValues(iter.get())) {
337 // Vehicle start and end nodes are represented as a single node in the
338 // CP-SAT model. We choose the start index to represent both. We can also
339 // skip any head representing a vehicle start as the CP solver will reject
340 // those.
341 if (model.IsStart(head)) continue;
342 if (model.IsEnd(head)) head = model.Start(0);
343 const int64_t cost = tail != head ? model.GetHomogeneousCost(tail, head)
344 : model.UnperformedPenalty(tail);
345 if (cost == std::numeric_limits<int64_t>::max()) continue;
346 const int index = AddVariable(cp_model, 0, 1);
347 circuit->add_literals(index);
348 circuit->add_tails(tail);
349 circuit->add_heads(head);
350 cp_model->mutable_objective()->add_vars(index);
351 cp_model->mutable_objective()->add_coeffs(cost);
352 gtl::InsertOrDie(&arc_vars, {tail, head}, index);
353 }
354 }
355 AddPickupDeliveryConstraints(model, arc_vars, cp_model);
356 AddDimensions(model, arc_vars, cp_model);
357 return arc_vars;
358 }
359
360 // Converts a RoutingModel to a CpModelProto.
361 // The mapping between CPModelProto arcs and their corresponding arc variables
362 // is returned.
PopulateModelFromRoutingModel(const RoutingModel & model,CpModelProto * cp_model)363 ArcVarMap PopulateModelFromRoutingModel(const RoutingModel& model,
364 CpModelProto* cp_model) {
365 if (model.vehicles() == 1) {
366 return PopulateSingleRouteModelFromRoutingModel(model, cp_model);
367 }
368 return PopulateMultiRouteModelFromRoutingModel(model, cp_model);
369 }
370
371 // Converts a CpSolverResponse to an Assignment containing next variables.
ConvertToSolution(const CpSolverResponse & response,const RoutingModel & model,const ArcVarMap & arc_vars,Assignment * solution)372 bool ConvertToSolution(const CpSolverResponse& response,
373 const RoutingModel& model, const ArcVarMap& arc_vars,
374 Assignment* solution) {
375 if (response.status() != CpSolverStatus::OPTIMAL &&
376 response.status() != CpSolverStatus::FEASIBLE)
377 return false;
378 const int depot = GetDepotFromModel(model);
379 int vehicle = 0;
380 for (const auto& arc_var : arc_vars) {
381 if (response.solution(arc_var.second) != 0) {
382 const int tail = arc_var.first.tail;
383 const int head = arc_var.first.head;
384 if (head == depot) continue;
385 if (tail != depot) {
386 solution->Add(model.NextVar(tail))->SetValue(head);
387 } else {
388 solution->Add(model.NextVar(model.Start(vehicle)))->SetValue(head);
389 ++vehicle;
390 }
391 }
392 }
393 // Close open routes.
394 for (int v = 0; v < model.vehicles(); ++v) {
395 int current = model.Start(v);
396 while (solution->Contains(model.NextVar(current))) {
397 current = solution->Value(model.NextVar(current));
398 }
399 solution->Add(model.NextVar(current))->SetValue(model.End(v));
400 }
401 return true;
402 }
403
404 // Adds dimensions to a CpModelProto for heterogeneous fleet. Adds path
405 // cumul constraints and cumul bounds.
AddGeneralizedDimensions(const RoutingModel & model,const ArcVarMap & arc_vars,const std::vector<absl::flat_hash_map<int,int>> & vehicle_performs_node,const std::vector<absl::flat_hash_map<int,int>> & vehicle_class_performs_arc,CpModelProto * cp_model)406 void AddGeneralizedDimensions(
407 const RoutingModel& model, const ArcVarMap& arc_vars,
408 const std::vector<absl::flat_hash_map<int, int>>& vehicle_performs_node,
409 const std::vector<absl::flat_hash_map<int, int>>&
410 vehicle_class_performs_arc,
411 CpModelProto* cp_model) {
412 const int num_cp_nodes = model.Nexts().size() + model.vehicles() + 1;
413 for (const RoutingDimension* dimension : model.GetDimensions()) {
414 // Initialize cumuls.
415 std::vector<int> cumuls(num_cp_nodes, -1);
416 for (int cp_node = 1; cp_node < num_cp_nodes; ++cp_node) {
417 const int node = cp_node - 1;
418 int64_t cumul_min = dimension->cumuls()[node]->Min();
419 int64_t cumul_max = dimension->cumuls()[node]->Max();
420 if (model.IsStart(node) || model.IsEnd(node)) {
421 const int vehicle = model.VehicleIndex(node);
422 cumul_max =
423 std::min(cumul_max, dimension->vehicle_capacities()[vehicle]);
424 }
425 cumuls[cp_node] = AddVariable(cp_model, cumul_min, cumul_max);
426 }
427
428 // Constrain cumuls with vehicle capacities.
429 for (int vehicle = 0; vehicle < model.vehicles(); vehicle++) {
430 for (int cp_node = 1; cp_node < num_cp_nodes; cp_node++) {
431 if (!vehicle_performs_node[vehicle].contains(cp_node)) continue;
432 const int64_t vehicle_capacity =
433 dimension->vehicle_capacities()[vehicle];
434 AddLinearConstraint(cp_model, std::numeric_limits<int64_t>::min(),
435 vehicle_capacity, {{cumuls[cp_node], 1}},
436 {vehicle_performs_node[vehicle].at(cp_node)});
437 }
438 }
439
440 for (auto vehicle_class = RoutingVehicleClassIndex(0);
441 vehicle_class < model.GetVehicleClassesCount(); vehicle_class++) {
442 std::vector<int> slack(num_cp_nodes, -1);
443 const int64_t span_cost =
444 dimension->GetSpanCostCoefficientForVehicleClass(vehicle_class);
445 for (const auto [arc, arc_var] : arc_vars) {
446 const auto [cp_tail, cp_head] = arc;
447 if (cp_tail == cp_head || cp_tail == 0 || cp_head == 0) continue;
448 if (!vehicle_class_performs_arc[vehicle_class.value()].contains(
449 arc_var)) {
450 continue;
451 }
452 // Create slack variable and add span cost to the objective.
453 if (slack[cp_tail] == -1) {
454 const int64_t slack_max =
455 cp_tail - 1 < dimension->slacks().size()
456 ? dimension->slacks()[cp_tail - 1]->Max()
457 : 0;
458 slack[cp_tail] = AddVariable(cp_model, 0, slack_max);
459 if (slack_max > 0 && span_cost > 0) {
460 cp_model->mutable_objective()->add_vars(slack[cp_tail]);
461 cp_model->mutable_objective()->add_coeffs(span_cost);
462 }
463 }
464 const int64_t transit = dimension->class_transit_evaluator(
465 vehicle_class)(cp_tail - 1, cp_head - 1);
466 // vehicle_class_performs_arc[vehicle][arc_var] = 1 ->
467 // cumuls[cp_head] - cumuls[cp_tail] - slack[cp_tail] = transit
468 AddLinearConstraint(
469 cp_model, transit, transit,
470 {{cumuls[cp_head], 1}, {cumuls[cp_tail], -1}, {slack[cp_tail], -1}},
471 {vehicle_class_performs_arc[vehicle_class.value()].at(arc_var)});
472 }
473 }
474
475 // Constrain cumuls with span limits.
476 for (int vehicle = 0; vehicle < model.vehicles(); vehicle++) {
477 const int64_t span_limit =
478 dimension->vehicle_span_upper_bounds()[vehicle];
479 if (span_limit == std::numeric_limits<int64_t>::max()) continue;
480 int cp_start = model.Start(vehicle) + 1;
481 int cp_end = model.End(vehicle) + 1;
482 AddLinearConstraint(cp_model, std::numeric_limits<int64_t>::min(),
483 span_limit,
484 {{cumuls[cp_end], 1}, {cumuls[cp_start], -1}});
485 }
486
487 // Set soft span upper bound costs.
488 if (dimension->HasSoftSpanUpperBounds()) {
489 for (int vehicle = 0; vehicle < model.vehicles(); vehicle++) {
490 const auto [bound, cost] =
491 dimension->GetSoftSpanUpperBoundForVehicle(vehicle);
492 const int cp_start = model.Start(vehicle) + 1;
493 const int cp_end = model.End(vehicle) + 1;
494 const int extra =
495 AddVariable(cp_model, 0,
496 std::min(dimension->cumuls()[model.End(vehicle)]->Max(),
497 dimension->vehicle_capacities()[vehicle]));
498 // -inf <= cumuls[cp_end] - cumuls[cp_start] - extra <= bound
499 AddLinearConstraint(
500 cp_model, std::numeric_limits<int64_t>::min(), bound,
501 {{cumuls[cp_end], 1}, {cumuls[cp_start], -1}, {extra, -1}});
502 // Add extra * cost to objective.
503 cp_model->mutable_objective()->add_vars(extra);
504 cp_model->mutable_objective()->add_coeffs(cost);
505 }
506 }
507 }
508 }
509
CreateGeneralizedRanks(const RoutingModel & model,const ArcVarMap & arc_vars,const std::vector<int> & is_unperformed,CpModelProto * cp_model)510 std::vector<int> CreateGeneralizedRanks(const RoutingModel& model,
511 const ArcVarMap& arc_vars,
512 const std::vector<int>& is_unperformed,
513 CpModelProto* cp_model) {
514 const int depot = 0;
515 const int num_cp_nodes = model.Nexts().size() + model.vehicles() + 1;
516 // Maximum length of a single route (excluding the depot & vehicle end nodes).
517 const int max_rank = num_cp_nodes - 2 * model.vehicles();
518 std::vector<int> ranks(num_cp_nodes, -1);
519 ranks[depot] = AddVariable(cp_model, 0, 0);
520 for (int cp_node = 1; cp_node < num_cp_nodes; cp_node++) {
521 if (model.IsEnd(cp_node - 1)) continue;
522 ranks[cp_node] = AddVariable(cp_model, 0, max_rank);
523 // For unperformed nodes rank is 0.
524 AddLinearConstraint(cp_model, 0, 0, {{ranks[cp_node], 1}},
525 {is_unperformed[cp_node]});
526 }
527 for (const auto [arc, arc_var] : arc_vars) {
528 const auto [cp_tail, cp_head] = arc;
529 if (model.IsEnd(cp_head - 1)) continue;
530 if (cp_tail == cp_head || cp_head == depot) continue;
531 // arc[tail][head] -> ranks[head] == ranks[tail] + 1.
532 AddLinearConstraint(cp_model, 1, 1,
533 {{ranks[cp_head], 1}, {ranks[cp_tail], -1}}, {arc_var});
534 }
535 return ranks;
536 }
537
AddGeneralizedPickupDeliveryConstraints(const RoutingModel & model,const ArcVarMap & arc_vars,const std::vector<absl::flat_hash_map<int,int>> & vehicle_performs_node,const std::vector<int> & is_unperformed,CpModelProto * cp_model)538 void AddGeneralizedPickupDeliveryConstraints(
539 const RoutingModel& model, const ArcVarMap& arc_vars,
540 const std::vector<absl::flat_hash_map<int, int>>& vehicle_performs_node,
541 const std::vector<int>& is_unperformed, CpModelProto* cp_model) {
542 if (model.GetPickupAndDeliveryPairs().empty()) return;
543 const std::vector<int> ranks =
544 CreateGeneralizedRanks(model, arc_vars, is_unperformed, cp_model);
545 for (const auto& pairs : model.GetPickupAndDeliveryPairs()) {
546 for (const int delivery : pairs.second) {
547 const int cp_delivery = delivery + 1;
548 for (int vehicle = 0; vehicle < model.vehicles(); vehicle++) {
549 const Arc vehicle_start_delivery_arc = {
550 static_cast<int>(model.Start(vehicle) + 1), cp_delivery};
551 if (gtl::ContainsKey(arc_vars, vehicle_start_delivery_arc)) {
552 // Forbid vehicle_start -> delivery arc.
553 AddLinearConstraint(cp_model, 0, 0,
554 {{arc_vars.at(vehicle_start_delivery_arc), 1}});
555 }
556 }
557
558 for (const int pickup : pairs.first) {
559 const int cp_pickup = pickup + 1;
560 const Arc delivery_pickup_arc = {cp_delivery, cp_pickup};
561 if (gtl::ContainsKey(arc_vars, delivery_pickup_arc)) {
562 // Forbid delivery -> pickup arc.
563 AddLinearConstraint(cp_model, 0, 0,
564 {{arc_vars.at(delivery_pickup_arc), 1}});
565 }
566
567 DCHECK_GE(is_unperformed[cp_delivery], 0);
568 DCHECK_GE(is_unperformed[cp_pickup], 0);
569 // A negative index i refers to NOT the literal at index -i - 1.
570 // -i - 1 ~ NOT i, if value of i in [0, 1] (boolean).
571 const int delivery_performed = -is_unperformed[cp_delivery] - 1;
572 const int pickup_performed = -is_unperformed[cp_pickup] - 1;
573 // The same vehicle performs pickup and delivery.
574 for (int vehicle = 0; vehicle < model.vehicles(); vehicle++) {
575 // delivery_performed & pickup_performed ->
576 // vehicle_performs_node[vehicle][cp_delivery] -
577 // vehicle_performs_node[vehicle][cp_pickup] = 0
578 AddLinearConstraint(
579 cp_model, 0, 0,
580 {{vehicle_performs_node[vehicle].at(cp_delivery), 1},
581 {vehicle_performs_node[vehicle].at(cp_pickup), -1}},
582 {delivery_performed, pickup_performed});
583 }
584 }
585 }
586
587 std::vector<std::pair<int, double>> ranks_difference;
588 // -SUM(pickup)ranks[pickup].
589 for (const int pickup : pairs.first) {
590 const int cp_pickup = pickup + 1;
591 ranks_difference.push_back({ranks[cp_pickup], -1});
592 }
593 // SUM(delivery)ranks[delivery].
594 for (const int delivery : pairs.second) {
595 const int cp_delivery = delivery + 1;
596 ranks_difference.push_back({ranks[cp_delivery], 1});
597 }
598 // SUM(delivery)ranks[delivery] - SUM(pickup)ranks[pickup] >= 1
599 AddLinearConstraint(cp_model, 1, std::numeric_limits<int64_t>::max(),
600 ranks_difference);
601 }
602 }
603
604 // Converts a RoutingModel to CpModelProto for models with multiple
605 // vehicles. The node 0 is depot. All nodes in CpModel have index increased
606 // by 1 in comparison to the RoutingModel. Each start node has only 1
607 // incoming arc (from depot), each end node has only 1 outgoing arc (to
608 // depot). The mapping from CPModelProto arcs to their corresponding arc
609 // variable is returned.
PopulateGeneralizedRouteModelFromRoutingModel(const RoutingModel & model,CpModelProto * cp_model)610 ArcVarMap PopulateGeneralizedRouteModelFromRoutingModel(
611 const RoutingModel& model, CpModelProto* cp_model) {
612 ArcVarMap arc_vars;
613 const int depot = 0;
614 const int num_nodes = model.Nexts().size();
615 const int num_cp_nodes = num_nodes + model.vehicles() + 1;
616 // vehicle_performs_node[vehicle][node] equals to 1 if the vehicle performs
617 // the node, and 0 otherwise.
618 std::vector<absl::flat_hash_map<int, int>> vehicle_performs_node(
619 model.vehicles());
620 // Connect vehicles start and end nodes to depot.
621 for (int vehicle = 0; vehicle < model.vehicles(); vehicle++) {
622 const int cp_start = model.Start(vehicle) + 1;
623 const Arc start_arc = {depot, cp_start};
624 const int start_arc_var = AddVariable(cp_model, 1, 1);
625 DCHECK(!gtl::ContainsKey(arc_vars, start_arc));
626 arc_vars.insert({start_arc, start_arc_var});
627
628 const int cp_end = model.End(vehicle) + 1;
629 const Arc end_arc = {cp_end, depot};
630 const int end_arc_var = AddVariable(cp_model, 1, 1);
631 DCHECK(!gtl::ContainsKey(arc_vars, end_arc));
632 arc_vars.insert({end_arc, end_arc_var});
633
634 vehicle_performs_node[vehicle][cp_start] = start_arc_var;
635 vehicle_performs_node[vehicle][cp_end] = end_arc_var;
636 }
637
638 // is_unperformed[node] variable equals to 1 if visit is unperformed, and 0
639 // otherwise.
640 std::vector<int> is_unperformed(num_cp_nodes, -1);
641 // Initialize is_unperformed variables for nodes that must be performed.
642 for (int node = 0; node < num_nodes; node++) {
643 const int cp_node = node + 1;
644 // Forced active and nodes that are not involved in any disjunctions are
645 // always performed.
646 const std::vector<RoutingDisjunctionIndex>& disjunction_indices =
647 model.GetDisjunctionIndices(node);
648 if (disjunction_indices.empty() || model.ActiveVar(node)->Min() == 1) {
649 is_unperformed[cp_node] = AddVariable(cp_model, 0, 0);
650 continue;
651 }
652 // Check if the node is in a forced active disjunction.
653 for (RoutingDisjunctionIndex disjunction_index : disjunction_indices) {
654 const int num_nodes =
655 model.GetDisjunctionNodeIndices(disjunction_index).size();
656 const int64_t penalty = model.GetDisjunctionPenalty(disjunction_index);
657 const int64_t max_cardinality =
658 model.GetDisjunctionMaxCardinality(disjunction_index);
659 if (num_nodes == max_cardinality &&
660 (penalty < 0 || penalty == std::numeric_limits<int64_t>::max())) {
661 // Nodes in this disjunction are forced active.
662 is_unperformed[cp_node] = AddVariable(cp_model, 0, 0);
663 break;
664 }
665 }
666 }
667 // Add alternative visits. Create self-looped arc variables. Set penalty for
668 // not performing disjunctions.
669 for (RoutingDisjunctionIndex disjunction_index(0);
670 disjunction_index < model.GetNumberOfDisjunctions();
671 disjunction_index++) {
672 const std::vector<int64_t>& disjunction_indices =
673 model.GetDisjunctionNodeIndices(disjunction_index);
674 const int disjunction_size = disjunction_indices.size();
675 const int64_t penalty = model.GetDisjunctionPenalty(disjunction_index);
676 const int64_t max_cardinality =
677 model.GetDisjunctionMaxCardinality(disjunction_index);
678 // Case when disjunction involves only 1 node, the node is only present in
679 // this disjunction, and the node can be unperformed.
680 if (disjunction_size == 1 &&
681 model.GetDisjunctionIndices(disjunction_indices[0]).size() == 1 &&
682 is_unperformed[disjunction_indices[0] + 1] == -1) {
683 const int cp_node = disjunction_indices[0] + 1;
684 const Arc arc = {cp_node, cp_node};
685 DCHECK(!gtl::ContainsKey(arc_vars, arc));
686 is_unperformed[cp_node] = AddVariable(cp_model, 0, 1);
687 arc_vars.insert({arc, is_unperformed[cp_node]});
688 cp_model->mutable_objective()->add_vars(is_unperformed[cp_node]);
689 cp_model->mutable_objective()->add_coeffs(penalty);
690 continue;
691 }
692 // num_performed + SUM(node)is_unperformed[node] = disjunction_size
693 const int num_performed = AddVariable(cp_model, 0, max_cardinality);
694 std::vector<std::pair<int, double>> var_coeffs;
695 var_coeffs.push_back({num_performed, 1});
696 for (const int node : disjunction_indices) {
697 const int cp_node = node + 1;
698 // Node can be unperformed.
699 if (is_unperformed[cp_node] == -1) {
700 const Arc arc = {cp_node, cp_node};
701 DCHECK(!gtl::ContainsKey(arc_vars, arc));
702 is_unperformed[cp_node] = AddVariable(cp_model, 0, 1);
703 arc_vars.insert({arc, is_unperformed[cp_node]});
704 }
705 var_coeffs.push_back({is_unperformed[cp_node], 1});
706 }
707 AddLinearConstraint(cp_model, disjunction_size, disjunction_size,
708 var_coeffs);
709 // When penalty is negative or max int64_t (forced active), num_violated is
710 // 0.
711 if (penalty < 0 || penalty == std::numeric_limits<int64_t>::max()) {
712 AddLinearConstraint(cp_model, max_cardinality, max_cardinality,
713 {{num_performed, 1}});
714 continue;
715 }
716 // If number of active indices is less than max_cardinality, then for each
717 // violated index 'penalty' is paid.
718 const int num_violated = AddVariable(cp_model, 0, max_cardinality);
719 cp_model->mutable_objective()->add_vars(num_violated);
720 cp_model->mutable_objective()->add_coeffs(penalty);
721 // num_performed + num_violated = max_cardinality
722 AddLinearConstraint(cp_model, max_cardinality, max_cardinality,
723 {{num_performed, 1}, {num_violated, 1}});
724 }
725 // Create "arc" variables.
726 for (int tail = 0; tail < num_nodes; ++tail) {
727 const int cp_tail = tail + 1;
728 std::unique_ptr<IntVarIterator> iter(
729 model.NextVar(tail)->MakeDomainIterator(false));
730 for (int head : InitAndGetValues(iter.get())) {
731 const int cp_head = head + 1;
732 if (model.IsStart(head)) continue;
733 // Arcs for unperformed visits have already been created.
734 if (tail == head) continue;
735 // Direct arcs from start to end nodes should exist only if they are
736 // for the same vehicle.
737 if (model.IsStart(tail) && model.IsEnd(head) &&
738 model.VehicleIndex(tail) != model.VehicleIndex(head)) {
739 continue;
740 }
741
742 bool feasible = false;
743 for (int vehicle = 0; vehicle < model.vehicles(); vehicle++) {
744 if (model.GetArcCostForVehicle(tail, head, vehicle) !=
745 std::numeric_limits<int64_t>::max()) {
746 feasible = true;
747 break;
748 }
749 }
750 if (!feasible) continue;
751
752 const Arc arc = {cp_tail, cp_head};
753 DCHECK(!gtl::ContainsKey(arc_vars, arc));
754 const int arc_var = AddVariable(cp_model, 0, 1);
755 arc_vars.insert({arc, arc_var});
756 }
757 }
758
759 // Set literals for vehicle performing node.
760 for (int cp_node = 1; cp_node < num_cp_nodes; cp_node++) {
761 // For starts and ends nodes vehicle_performs_node variables already set.
762 if (model.IsStart(cp_node - 1) || model.IsEnd(cp_node - 1)) continue;
763 // Each node should be performed by 1 vehicle, or be unperformed.
764 // SUM(vehicle)(vehicle_performs_node[vehicle][cp_node]) + loop(cp_node) = 1
765 std::vector<std::pair<int, double>> var_coeffs;
766 for (int vehicle = 0; vehicle < model.vehicles(); vehicle++) {
767 vehicle_performs_node[vehicle][cp_node] = AddVariable(cp_model, 0, 1);
768 var_coeffs.push_back({vehicle_performs_node[vehicle][cp_node], 1});
769 }
770 var_coeffs.push_back({is_unperformed[cp_node], 1});
771 AddLinearConstraint(cp_model, 1, 1, var_coeffs);
772 }
773 const int num_vehicle_classes = model.GetVehicleClassesCount();
774 // vehicle_class_performs_node[vehicle_class][node] equals to 1 if the
775 // vehicle of vehicle_class performs the node, and 0 otherwise.
776 std::vector<absl::flat_hash_map<int, int>> vehicle_class_performs_node(
777 num_vehicle_classes);
778 for (int cp_node = 1; cp_node < num_cp_nodes; cp_node++) {
779 const int node = cp_node - 1;
780 for (int vehicle_class = 0; vehicle_class < num_vehicle_classes;
781 vehicle_class++) {
782 if (model.IsStart(node) || model.IsEnd(node)) {
783 const int vehicle = model.VehicleIndex(node);
784 vehicle_class_performs_node[vehicle_class][cp_node] =
785 vehicle_class ==
786 model.GetVehicleClassIndexOfVehicle(vehicle).value()
787 ? AddVariable(cp_model, 1, 1)
788 : AddVariable(cp_model, 0, 0);
789 continue;
790 }
791 vehicle_class_performs_node[vehicle_class][cp_node] =
792 AddVariable(cp_model, 0, 1);
793 std::vector<std::pair<int, double>> var_coeffs;
794 for (int vehicle = 0; vehicle < model.vehicles(); vehicle++) {
795 if (model.GetVehicleClassIndexOfVehicle(vehicle).value() ==
796 vehicle_class) {
797 var_coeffs.push_back({vehicle_performs_node[vehicle][cp_node], 1});
798 // vehicle_performs_node -> vehicle_class_performs_node
799 AddLinearConstraint(
800 cp_model, 1, 1,
801 {{vehicle_class_performs_node[vehicle_class][cp_node], 1}},
802 {vehicle_performs_node[vehicle][cp_node]});
803 }
804 }
805 // vehicle_class_performs_node -> exactly one vehicle from this class
806 // performs node.
807 AddLinearConstraint(
808 cp_model, 1, 1, var_coeffs,
809 {vehicle_class_performs_node[vehicle_class][cp_node]});
810 }
811 }
812 // vehicle_class_performs_arc[vehicle_class][arc_var] equals to 1 if the
813 // vehicle of vehicle_class performs the arc, and 0 otherwise.
814 std::vector<absl::flat_hash_map<int, int>> vehicle_class_performs_arc(
815 num_vehicle_classes);
816 // Set "arc" costs.
817 for (const auto [arc, arc_var] : arc_vars) {
818 const auto [cp_tail, cp_head] = arc;
819 if (cp_tail == depot || cp_head == depot) continue;
820 const int tail = cp_tail - 1;
821 const int head = cp_head - 1;
822 // Costs for unperformed arcs have already been set.
823 if (tail == head) continue;
824 for (int vehicle = 0; vehicle < model.vehicles(); vehicle++) {
825 // The arc can't be performed by the vehicle when vehicle can't perform
826 // arc nodes.
827 if (!vehicle_performs_node[vehicle].contains(cp_tail) ||
828 !vehicle_performs_node[vehicle].contains(cp_head)) {
829 continue;
830 }
831 int64_t cost = model.GetArcCostForVehicle(tail, head, vehicle);
832 // Arcs with int64_t's max cost are infeasible.
833 if (cost == std::numeric_limits<int64_t>::max()) continue;
834 const int vehicle_class =
835 model.GetVehicleClassIndexOfVehicle(vehicle).value();
836 if (!vehicle_class_performs_arc[vehicle_class].contains(arc_var)) {
837 vehicle_class_performs_arc[vehicle_class][arc_var] =
838 AddVariable(cp_model, 0, 1);
839 // Create constraints to set vehicle_class_performs_arc.
840 // vehicle_class_performs_arc ->
841 // vehicle_class_performs_tail & vehicle_class_performs_head &
842 // arc_is_performed
843 ConstraintProto* ct = cp_model->add_constraints();
844 ct->add_enforcement_literal(
845 vehicle_class_performs_arc[vehicle_class][arc_var]);
846 BoolArgumentProto* bool_and = ct->mutable_bool_and();
847 bool_and->add_literals(
848 vehicle_class_performs_node[vehicle_class][cp_tail]);
849 bool_and->add_literals(
850 vehicle_class_performs_node[vehicle_class][cp_head]);
851 bool_and->add_literals(arc_var);
852 // Don't add arcs with zero cost to the objective.
853 if (cost != 0) {
854 cp_model->mutable_objective()->add_vars(
855 vehicle_class_performs_arc[vehicle_class][arc_var]);
856 cp_model->mutable_objective()->add_coeffs(cost);
857 }
858 }
859 // (arc_is_performed & vehicle_performs_tail) ->
860 // (vehicle_class_performs_arc & vehicle_performs_head)
861 ConstraintProto* ct_arc_tail = cp_model->add_constraints();
862 ct_arc_tail->add_enforcement_literal(arc_var);
863 ct_arc_tail->add_enforcement_literal(
864 vehicle_performs_node[vehicle][cp_tail]);
865 ct_arc_tail->mutable_bool_and()->add_literals(
866 vehicle_class_performs_arc[vehicle_class][arc_var]);
867 ct_arc_tail->mutable_bool_and()->add_literals(
868 vehicle_performs_node[vehicle][cp_head]);
869 // (arc_is_performed & vehicle_performs_head) ->
870 // (vehicle_class_performs_arc & vehicle_performs_tail)
871 ConstraintProto* ct_arc_head = cp_model->add_constraints();
872 ct_arc_head->add_enforcement_literal(arc_var);
873 ct_arc_head->add_enforcement_literal(
874 vehicle_performs_node[vehicle][cp_head]);
875 ct_arc_head->mutable_bool_and()->add_literals(
876 vehicle_class_performs_arc[vehicle_class][arc_var]);
877 ct_arc_head->mutable_bool_and()->add_literals(
878 vehicle_performs_node[vehicle][cp_tail]);
879 }
880 }
881
882 AddGeneralizedPickupDeliveryConstraints(
883 model, arc_vars, vehicle_performs_node, is_unperformed, cp_model);
884
885 AddGeneralizedDimensions(model, arc_vars, vehicle_performs_node,
886 vehicle_class_performs_arc, cp_model);
887
888 // Create Routes constraint, ensuring circuits from and to the depot.
889 RoutesConstraintProto* routes_ct =
890 cp_model->add_constraints()->mutable_routes();
891 for (const auto [arc, arc_var] : arc_vars) {
892 const int tail = arc.tail;
893 const int head = arc.head;
894 routes_ct->add_tails(tail);
895 routes_ct->add_heads(head);
896 routes_ct->add_literals(arc_var);
897 }
898
899 // Add demands and capacities to improve the LP relaxation and cuts. These
900 // are based on the first "unary" dimension in the model if it exists.
901 // TODO(user): We might want to try to get demand lower bounds from
902 // non-unary dimensions if no unary exist.
903 const RoutingDimension* master_dimension = nullptr;
904 for (const RoutingDimension* dimension : model.GetDimensions()) {
905 bool is_unary = true;
906 for (int vehicle = 0; vehicle < model.vehicles(); vehicle++) {
907 if (dimension->GetUnaryTransitEvaluator(vehicle) == nullptr) {
908 is_unary = false;
909 break;
910 }
911 }
912 if (is_unary) {
913 master_dimension = dimension;
914 break;
915 }
916 }
917 if (master_dimension != nullptr) {
918 for (int cp_node = 0; cp_node < num_cp_nodes; ++cp_node) {
919 int64_t min_transit = std::numeric_limits<int64_t>::max();
920 if (cp_node != 0 && !model.IsEnd(cp_node - 1)) {
921 for (int vehicle = 0; vehicle < model.vehicles(); vehicle++) {
922 const RoutingModel::TransitCallback1& transit =
923 master_dimension->GetUnaryTransitEvaluator(vehicle);
924 min_transit = std::min(min_transit, transit(cp_node - 1));
925 }
926 } else {
927 min_transit = 0;
928 }
929 routes_ct->add_demands(min_transit);
930 }
931 DCHECK_EQ(routes_ct->demands_size(), num_cp_nodes);
932 int64_t max_capacity = std::numeric_limits<int64_t>::min();
933 for (int vehicle = 0; vehicle < model.vehicles(); vehicle++) {
934 max_capacity = std::max(max_capacity,
935 master_dimension->vehicle_capacities()[vehicle]);
936 }
937 routes_ct->set_capacity(max_capacity);
938 }
939 return arc_vars;
940 }
941
942 // Converts a CpSolverResponse to an Assignment containing next variables.
ConvertGeneralizedResponseToSolution(const CpSolverResponse & response,const RoutingModel & model,const ArcVarMap & arc_vars,Assignment * solution)943 bool ConvertGeneralizedResponseToSolution(const CpSolverResponse& response,
944 const RoutingModel& model,
945 const ArcVarMap& arc_vars,
946 Assignment* solution) {
947 if (response.status() != CpSolverStatus::OPTIMAL &&
948 response.status() != CpSolverStatus::FEASIBLE) {
949 return false;
950 }
951 const int depot = 0;
952 for (const auto [arc, arc_var] : arc_vars) {
953 if (response.solution(arc_var) == 0) continue;
954 const auto [tail, head] = arc;
955 if (head == depot || tail == depot) continue;
956 solution->Add(model.NextVar(tail - 1))->SetValue(head - 1);
957 }
958 return true;
959 }
960
961 // Uses CP solution as hint for CP-SAT.
AddSolutionAsHintToGeneralizedModel(const Assignment * solution,const RoutingModel & model,const ArcVarMap & arc_vars,CpModelProto * cp_model)962 void AddSolutionAsHintToGeneralizedModel(const Assignment* solution,
963 const RoutingModel& model,
964 const ArcVarMap& arc_vars,
965 CpModelProto* cp_model) {
966 if (solution == nullptr) return;
967 PartialVariableAssignment* const hint = cp_model->mutable_solution_hint();
968 hint->Clear();
969 const int num_nodes = model.Nexts().size();
970 for (int tail = 0; tail < num_nodes; ++tail) {
971 const int cp_tail = tail + 1;
972 const int cp_head = solution->Value(model.NextVar(tail)) + 1;
973 const int* const arc_var = gtl::FindOrNull(arc_vars, {cp_tail, cp_head});
974 // Arcs with a cost of max int64_t are not added to the model (considered as
975 // infeasible). In some rare cases CP solutions might contain such arcs in
976 // which case they are skipped here and a partial solution is used as a
977 // hint.
978 if (arc_var == nullptr) continue;
979 hint->add_vars(*arc_var);
980 hint->add_values(1);
981 }
982 }
983
AddSolutionAsHintToModel(const Assignment * solution,const RoutingModel & model,const ArcVarMap & arc_vars,CpModelProto * cp_model)984 void AddSolutionAsHintToModel(const Assignment* solution,
985 const RoutingModel& model,
986 const ArcVarMap& arc_vars,
987 CpModelProto* cp_model) {
988 if (solution == nullptr) return;
989 PartialVariableAssignment* const hint = cp_model->mutable_solution_hint();
990 hint->Clear();
991 const int depot = GetDepotFromModel(model);
992 const int num_nodes = model.Nexts().size();
993 for (int tail = 0; tail < num_nodes; ++tail) {
994 const int tail_index = model.IsStart(tail) ? depot : tail;
995 const int head = solution->Value(model.NextVar(tail));
996 const int head_index = model.IsEnd(head) ? depot : head;
997 if (tail_index == depot && head_index == depot) continue;
998 const int* const var_index =
999 gtl::FindOrNull(arc_vars, {tail_index, head_index});
1000 // Arcs with a cost of kint64max are not added to the model (considered as
1001 // infeasible). In some rare cases CP solutions might contain such arcs in
1002 // which case they are skipped here and a partial solution is used as a
1003 // hint.
1004 if (var_index == nullptr) continue;
1005 hint->add_vars(*var_index);
1006 hint->add_values(1);
1007 }
1008 }
1009
1010 // Configures a CP-SAT solver and solves the given (routing) model using it.
1011 // Returns the response of the search.
SolveRoutingModel(const CpModelProto & cp_model,absl::Duration remaining_time,const RoutingSearchParameters & search_parameters,const std::function<void (const CpSolverResponse & response)> & observer)1012 CpSolverResponse SolveRoutingModel(
1013 const CpModelProto& cp_model, absl::Duration remaining_time,
1014 const RoutingSearchParameters& search_parameters,
1015 const std::function<void(const CpSolverResponse& response)>& observer) {
1016 // Copying to set remaining time.
1017 SatParameters sat_parameters = search_parameters.sat_parameters();
1018 if (!sat_parameters.has_max_time_in_seconds()) {
1019 sat_parameters.set_max_time_in_seconds(
1020 absl::ToDoubleSeconds(remaining_time));
1021 } else {
1022 sat_parameters.set_max_time_in_seconds(
1023 std::min(absl::ToDoubleSeconds(remaining_time),
1024 sat_parameters.max_time_in_seconds()));
1025 }
1026 Model model;
1027 model.Add(NewSatParameters(sat_parameters));
1028 if (observer != nullptr) {
1029 model.Add(NewFeasibleSolutionObserver(observer));
1030 }
1031 // TODO(user): Add an option to dump the CP-SAT model or check if the
1032 // cp_model_dump_file flag in cp_model_solver.cc is good enough.
1033 return SolveCpModel(cp_model, &model);
1034 }
1035
1036 // Check if all the nodes are present in arcs. Otherwise, CP-SAT solver may
1037 // fail.
IsFeasibleArcVarMap(const ArcVarMap & arc_vars,int max_node_index)1038 bool IsFeasibleArcVarMap(const ArcVarMap& arc_vars, int max_node_index) {
1039 Bitset64<> present_in_arcs(max_node_index + 1);
1040 for (const auto [arc, _] : arc_vars) {
1041 present_in_arcs.Set(arc.head);
1042 present_in_arcs.Set(arc.tail);
1043 }
1044 for (int i = 0; i <= max_node_index; i++) {
1045 if (!present_in_arcs[i]) return false;
1046 }
1047 return true;
1048 }
1049
1050 } // namespace
1051 } // namespace sat
1052
1053 // Solves a RoutingModel using the CP-SAT solver. Returns false if no solution
1054 // was found.
SolveModelWithSat(const RoutingModel & model,const RoutingSearchParameters & search_parameters,const Assignment * initial_solution,Assignment * solution)1055 bool SolveModelWithSat(const RoutingModel& model,
1056 const RoutingSearchParameters& search_parameters,
1057 const Assignment* initial_solution,
1058 Assignment* solution) {
1059 sat::CpModelProto cp_model;
1060 cp_model.mutable_objective()->set_scaling_factor(
1061 search_parameters.log_cost_scaling_factor());
1062 cp_model.mutable_objective()->set_offset(search_parameters.log_cost_offset());
1063 if (search_parameters.use_generalized_cp_sat() == BOOL_TRUE) {
1064 const sat::ArcVarMap arc_vars =
1065 sat::PopulateGeneralizedRouteModelFromRoutingModel(model, &cp_model);
1066 const int max_node_index = model.Nexts().size() + model.vehicles();
1067 if (!sat::IsFeasibleArcVarMap(arc_vars, max_node_index)) return false;
1068 sat::AddSolutionAsHintToGeneralizedModel(initial_solution, model, arc_vars,
1069 &cp_model);
1070 return sat::ConvertGeneralizedResponseToSolution(
1071 sat::SolveRoutingModel(cp_model, model.RemainingTime(),
1072 search_parameters, nullptr),
1073 model, arc_vars, solution);
1074 }
1075 if (!sat::RoutingModelCanBeSolvedBySat(model)) return false;
1076 const sat::ArcVarMap arc_vars =
1077 sat::PopulateModelFromRoutingModel(model, &cp_model);
1078 sat::AddSolutionAsHintToModel(initial_solution, model, arc_vars, &cp_model);
1079 return sat::ConvertToSolution(
1080 sat::SolveRoutingModel(cp_model, model.RemainingTime(), search_parameters,
1081 nullptr),
1082 model, arc_vars, solution);
1083 }
1084
1085 } // namespace operations_research
1086