OR-Tools  8.2
routing_sat.cc
Go to the documentation of this file.
1// Copyright 2010-2018 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
16
17namespace operations_research {
18namespace sat {
19namespace {
20
21// As of 07/2019, TSPs and VRPs with homogeneous fleets of vehicles are
22// supported.
23// TODO(user): Support any type of constraints.
24// TODO(user): Make VRPs properly support optional nodes.
25bool RoutingModelCanBeSolvedBySat(const RoutingModel& model) {
26 return model.GetVehicleClassesCount() == 1;
27}
28
29// Adds an integer variable to a CpModelProto, returning its index in the proto.
30int AddVariable(CpModelProto* cp_model, int64 lb, int64 ub) {
31 const int index = cp_model->variables_size();
32 IntegerVariableProto* const var = cp_model->add_variables();
33 var->add_domain(lb);
34 var->add_domain(ub);
35 return index;
36}
37
38// Returns the unique depot node used in the CP-SAT models (as of 01/2020).
39int64 GetDepotFromModel(const RoutingModel& model) { return model.Start(0); }
40
41// Structure to keep track of arcs created.
42struct Arc {
43 int tail;
44 int head;
45
46 friend bool operator==(const Arc& a, const Arc& b) {
47 return a.tail == b.tail && a.head == b.head;
48 }
49 friend bool operator!=(const Arc& a, const Arc& b) { return !(a == b); }
50 friend bool operator<(const Arc& a, const Arc& b) {
51 return a.tail == b.tail ? a.head < b.head : a.tail < b.tail;
52 }
53 friend std::ostream& operator<<(std::ostream& strm, const Arc& arc) {
54 return strm << "{" << arc.tail << ", " << arc.head << "}";
55 }
56 template <typename H>
57 friend H AbslHashValue(H h, const Arc& a) {
58 return H::combine(std::move(h), a.tail, a.head);
59 }
60};
61
62using ArcVarMap = std::map<Arc, int>; // needs to be stable when iterating
63
64// Adds all dimensions to a CpModelProto. Only adds path cumul constraints and
65// cumul bounds.
66void AddDimensions(const RoutingModel& model, const ArcVarMap& arc_vars,
67 CpModelProto* cp_model) {
68 for (const RoutingDimension* dimension : model.GetDimensions()) {
69 // Only a single vehicle class.
70 const RoutingModel::TransitCallback2& transit =
71 dimension->transit_evaluator(0);
72 std::vector<int> cumuls(dimension->cumuls().size(), -1);
73 const int64 min_start = dimension->cumuls()[model.Start(0)]->Min();
74 const int64 max_end = std::min(dimension->cumuls()[model.End(0)]->Max(),
75 dimension->vehicle_capacities()[0]);
76 for (int i = 0; i < cumuls.size(); ++i) {
77 if (model.IsStart(i) || model.IsEnd(i)) continue;
78 // Reducing bounds supposing the triangular inequality.
79 const int64 cumul_min =
81 std::max(dimension->cumuls()[i]->Min(),
82 CapAdd(transit(model.Start(0), i), min_start)));
83 const int64 cumul_max =
85 std::min(dimension->cumuls()[i]->Max(),
86 CapSub(max_end, transit(i, model.End(0)))));
87 cumuls[i] = AddVariable(cp_model, cumul_min, cumul_max);
88 }
89 for (const auto arc_var : arc_vars) {
90 const int tail = arc_var.first.tail;
91 const int head = arc_var.first.head;
92 if (tail == head || model.IsStart(tail) || model.IsStart(head)) continue;
93 // arc[tail][head] -> cumuls[head] >= cumuls[tail] + transit.
94 // This is a relaxation of the model as it does not consider slack max.
95 ConstraintProto* ct = cp_model->add_constraints();
96 ct->add_enforcement_literal(arc_var.second);
97 LinearConstraintProto* arg = ct->mutable_linear();
98 arg->add_domain(transit(tail, head));
99 arg->add_domain(kint64max);
100 arg->add_vars(cumuls[tail]);
101 arg->add_coeffs(-1);
102 arg->add_vars(cumuls[head]);
103 arg->add_coeffs(1);
104 }
105 }
106}
107
108std::vector<int> CreateRanks(const RoutingModel& model,
109 const ArcVarMap& arc_vars,
110 CpModelProto* cp_model) {
111 const int depot = GetDepotFromModel(model);
112 const int size = model.Size() + model.vehicles();
113 const int rank_size = model.Size() - model.vehicles();
114 std::vector<int> ranks(size, -1);
115 for (int i = 0; i < size; ++i) {
116 if (model.IsStart(i) || model.IsEnd(i)) continue;
117 ranks[i] = AddVariable(cp_model, 0, rank_size);
118 }
119 ranks[depot] = AddVariable(cp_model, 0, 0);
120 for (const auto arc_var : arc_vars) {
121 const int tail = arc_var.first.tail;
122 const int head = arc_var.first.head;
123 if (tail == head || head == depot) continue;
124 // arc[tail][head] -> ranks[head] == ranks[tail] + 1.
125 ConstraintProto* ct = cp_model->add_constraints();
126 ct->add_enforcement_literal(arc_var.second);
127 LinearConstraintProto* arg = ct->mutable_linear();
128 arg->add_domain(1);
129 arg->add_domain(1);
130 arg->add_vars(ranks[tail]);
131 arg->add_coeffs(-1);
132 arg->add_vars(ranks[head]);
133 arg->add_coeffs(1);
134 }
135 return ranks;
136}
137
138// Vehicle variables do not actually represent the index of the vehicle
139// performing a node, but we ensure that the values of two vehicle variables
140// are the same if and only if the corresponding nodes are served by the same
141// vehicle.
142std::vector<int> CreateVehicleVars(const RoutingModel& model,
143 const ArcVarMap& arc_vars,
144 CpModelProto* cp_model) {
145 const int depot = GetDepotFromModel(model);
146 const int size = model.Size() + model.vehicles();
147 std::vector<int> vehicles(size, -1);
148 for (int i = 0; i < size; ++i) {
149 if (model.IsStart(i) || model.IsEnd(i)) continue;
150 vehicles[i] = AddVariable(cp_model, 0, size - 1);
151 }
152 for (const auto arc_var : arc_vars) {
153 const int tail = arc_var.first.tail;
154 const int head = arc_var.first.head;
155 if (tail == head || head == depot) continue;
156 if (tail == depot) {
157 // arc[depot][head] -> vehicles[head] == head.
158 ConstraintProto* ct = cp_model->add_constraints();
159 ct->add_enforcement_literal(arc_var.second);
160 LinearConstraintProto* arg = ct->mutable_linear();
161 arg->add_domain(head);
162 arg->add_domain(head);
163 arg->add_vars(vehicles[head]);
164 arg->add_coeffs(1);
165 continue;
166 }
167 // arc[tail][head] -> vehicles[head] == vehicles[tail].
168 ConstraintProto* ct = cp_model->add_constraints();
169 ct->add_enforcement_literal(arc_var.second);
170 LinearConstraintProto* arg = ct->mutable_linear();
171 arg->add_domain(0);
172 arg->add_domain(0);
173 arg->add_vars(vehicles[tail]);
174 arg->add_coeffs(-1);
175 arg->add_vars(vehicles[head]);
176 arg->add_coeffs(1);
177 }
178 return vehicles;
179}
180
181void AddPickupDeliveryConstraints(const RoutingModel& model,
182 const ArcVarMap& arc_vars,
183 CpModelProto* cp_model) {
184 if (model.GetPickupAndDeliveryPairs().empty()) return;
185 const std::vector<int> ranks = CreateRanks(model, arc_vars, cp_model);
186 const std::vector<int> vehicles =
187 CreateVehicleVars(model, arc_vars, cp_model);
188 for (const auto& pairs : model.GetPickupAndDeliveryPairs()) {
189 const int64 pickup = pairs.first[0];
190 const int64 delivery = pairs.second[0];
191 {
192 // ranks[pickup] + 1 <= ranks[delivery].
193 ConstraintProto* ct = cp_model->add_constraints();
194 LinearConstraintProto* arg = ct->mutable_linear();
195 arg->add_domain(1);
196 arg->add_domain(kint64max);
197 arg->add_vars(ranks[delivery]);
198 arg->add_coeffs(1);
199 arg->add_vars(ranks[pickup]);
200 arg->add_coeffs(-1);
201 }
202 {
203 // vehicles[pickup] == vehicles[delivery]
204 ConstraintProto* ct = cp_model->add_constraints();
205 LinearConstraintProto* arg = ct->mutable_linear();
206 arg->add_domain(0);
207 arg->add_domain(0);
208 arg->add_vars(vehicles[delivery]);
209 arg->add_coeffs(1);
210 arg->add_vars(vehicles[pickup]);
211 arg->add_coeffs(-1);
212 }
213 }
214}
215
216// Converts a RoutingModel to CpModelProto for models with multiple vehicles.
217// All non-start/end nodes have the same index in both models. Start/end nodes
218// map to a single depot index; its value is arbitrarly the index of the start
219// node of the first vehicle in the RoutingModel.
220// The map between CPModelProto arcs and their corresponding arc variable is
221// returned.
222ArcVarMap PopulateMultiRouteModelFromRoutingModel(const RoutingModel& model,
223 CpModelProto* cp_model) {
224 ArcVarMap arc_vars;
225 const int num_nodes = model.Nexts().size();
226 const int depot = GetDepotFromModel(model);
227
228 // Create "arc" variables and set their cost.
229 for (int tail = 0; tail < num_nodes; ++tail) {
230 const int tail_index = model.IsStart(tail) ? depot : tail;
231 std::unique_ptr<IntVarIterator> iter(
232 model.NextVar(tail)->MakeDomainIterator(false));
233 for (int head : InitAndGetValues(iter.get())) {
234 // Vehicle start and end nodes are represented as a single node in the
235 // CP-SAT model. We choose the start index of the first vehicle to
236 // represent both. We can also skip any head representing a vehicle start
237 // as the CP solver will reject those.
238 if (model.IsStart(head)) continue;
239 const int head_index = model.IsEnd(head) ? depot : head;
240 if (head_index == tail_index) continue;
241 const int64 cost = tail != head ? model.GetHomogeneousCost(tail, head)
242 : model.UnperformedPenalty(tail);
243 if (cost == kint64max) continue;
244 const Arc arc = {tail_index, head_index};
245 if (gtl::ContainsKey(arc_vars, arc)) continue;
246 const int index = AddVariable(cp_model, 0, 1);
247 gtl::InsertOrDie(&arc_vars, arc, index);
248 cp_model->mutable_objective()->add_vars(index);
249 cp_model->mutable_objective()->add_coeffs(cost);
250 }
251 }
252
253 // The following flow constraints seem to be necessary with the Route
254 // constraint, greatly improving performance due to stronger LP relaxation
255 // (supposedly).
256 // TODO(user): Remove these constraints when the Route constraint handles
257 // LP relaxations properly.
258 {
259 LinearConstraintProto* ct = cp_model->add_constraints()->mutable_linear();
260 ct->add_domain(0);
261 ct->add_domain(0);
262 for (int node = 0; node < num_nodes; ++node) {
263 if (model.IsStart(node) || model.IsEnd(node)) continue;
264 int* const depot_node_var = gtl::FindOrNull(arc_vars, {depot, node});
265 if (depot_node_var == nullptr) continue;
266 ct->add_vars(*depot_node_var);
267 ct->add_coeffs(1);
268 int* const node_depot_var = gtl::FindOrNull(arc_vars, {node, depot});
269 if (node_depot_var == nullptr) continue;
270 ct->add_vars(*node_depot_var);
271 ct->add_coeffs(-1);
272 }
273 }
274
275 {
276 LinearConstraintProto* ct = cp_model->add_constraints()->mutable_linear();
277 ct->add_domain(0);
278 // Taking the min since as of 04/2020 fleet is homogeneous.
279 ct->add_domain(
280 std::min(model.vehicles(), model.GetMaximumNumberOfActiveVehicles()));
281 for (int node = 0; node < num_nodes; ++node) {
282 if (model.IsStart(node) || model.IsEnd(node)) continue;
283 int* const var = gtl::FindOrNull(arc_vars, {depot, node});
284 if (var == nullptr) continue;
285 ct->add_vars(*var);
286 ct->add_coeffs(1);
287 }
288 }
289
290 for (int tail = 0; tail < num_nodes; ++tail) {
291 if (model.IsStart(tail) || model.IsEnd(tail)) continue;
292 LinearConstraintProto* ct = cp_model->add_constraints()->mutable_linear();
293 ct->add_domain(1);
294 ct->add_domain(1);
295 std::unique_ptr<IntVarIterator> iter(
296 model.NextVar(tail)->MakeDomainIterator(false));
297 bool depot_added = false;
298 for (int head : InitAndGetValues(iter.get())) {
299 if (model.IsStart(head)) continue;
300 if (tail == head) continue;
301 if (model.IsEnd(head)) {
302 if (depot_added) continue;
303 head = depot;
304 depot_added = true;
305 }
306 int* const var = gtl::FindOrNull(arc_vars, {tail, head});
307 if (var == nullptr) continue;
308 ct->add_vars(*var);
309 ct->add_coeffs(1);
310 }
311 }
312
313 for (int head = 0; head < num_nodes; ++head) {
314 if (model.IsStart(head) || model.IsEnd(head)) continue;
315 LinearConstraintProto* ct = cp_model->add_constraints()->mutable_linear();
316 ct->add_domain(1);
317 ct->add_domain(1);
318 for (int tail = 0; tail < num_nodes; ++tail) {
319 if (model.IsEnd(head)) continue;
320 if (tail == head) continue;
321 if (model.IsStart(tail) && tail != depot) continue;
322 int* const var = gtl::FindOrNull(arc_vars, {tail, head});
323 if (var == nullptr) continue;
324 ct->add_vars(*var);
325 ct->add_coeffs(1);
326 }
327 }
328
329 AddPickupDeliveryConstraints(model, arc_vars, cp_model);
330
331 AddDimensions(model, arc_vars, cp_model);
332
333 // Create Routes constraint, ensuring circuits from and to the depot.
334 // This one is a bit tricky, because we need to remap the depot to zero.
335 // TODO(user): Make Routes constraints support optional nodes.
336 RoutesConstraintProto* routes_ct =
337 cp_model->add_constraints()->mutable_routes();
338 for (const auto arc_var : arc_vars) {
339 const int tail = arc_var.first.tail;
340 const int head = arc_var.first.head;
341 routes_ct->add_tails(tail == 0 ? depot : tail == depot ? 0 : tail);
342 routes_ct->add_heads(head == 0 ? depot : head == depot ? 0 : head);
343 routes_ct->add_literals(arc_var.second);
344 }
345
346 // Add demands and capacities to improve the LP relaxation and cuts. These are
347 // based on the first "unary" dimension in the model if it exists.
348 // TODO(user): We might want to try to get demand lower bounds from
349 // non-unary dimensions if no unary exist.
350 const RoutingDimension* master_dimension = nullptr;
351 for (const RoutingDimension* dimension : model.GetDimensions()) {
352 // Only a single vehicle class is supported.
353 if (dimension->GetUnaryTransitEvaluator(0) != nullptr) {
354 master_dimension = dimension;
355 break;
356 }
357 }
358 if (master_dimension != nullptr) {
359 const RoutingModel::TransitCallback1& transit =
360 master_dimension->GetUnaryTransitEvaluator(0);
361 for (int node = 0; node < num_nodes; ++node) {
362 // Tricky: demand is added for all nodes in the sat model; this means
363 // start/end nodes other than the one used for the depot must be ignored.
364 if (!model.IsEnd(node) && (!model.IsStart(node) || node == depot)) {
365 routes_ct->add_demands(transit(node));
366 }
367 }
368 DCHECK_EQ(routes_ct->demands_size(), num_nodes + 1 - model.vehicles());
369 routes_ct->set_capacity(master_dimension->vehicle_capacities()[0]);
370 }
371 return arc_vars;
372}
373
374// Converts a RoutingModel with a single vehicle to a CpModelProto.
375// The mapping between CPModelProto arcs and their corresponding arc variables
376// is returned.
377ArcVarMap PopulateSingleRouteModelFromRoutingModel(const RoutingModel& model,
378 CpModelProto* cp_model) {
379 ArcVarMap arc_vars;
380 const int num_nodes = model.Nexts().size();
381 CircuitConstraintProto* circuit =
382 cp_model->add_constraints()->mutable_circuit();
383 for (int tail = 0; tail < num_nodes; ++tail) {
384 std::unique_ptr<IntVarIterator> iter(
385 model.NextVar(tail)->MakeDomainIterator(false));
386 for (int head : InitAndGetValues(iter.get())) {
387 // Vehicle start and end nodes are represented as a single node in the
388 // CP-SAT model. We choose the start index to represent both. We can also
389 // skip any head representing a vehicle start as the CP solver will reject
390 // those.
391 if (model.IsStart(head)) continue;
392 if (model.IsEnd(head)) head = model.Start(0);
393 const int64 cost = tail != head ? model.GetHomogeneousCost(tail, head)
394 : model.UnperformedPenalty(tail);
395 if (cost == kint64max) continue;
396 const int index = AddVariable(cp_model, 0, 1);
397 circuit->add_literals(index);
398 circuit->add_tails(tail);
399 circuit->add_heads(head);
400 cp_model->mutable_objective()->add_vars(index);
401 cp_model->mutable_objective()->add_coeffs(cost);
402 gtl::InsertOrDie(&arc_vars, {tail, head}, index);
403 }
404 }
405 AddPickupDeliveryConstraints(model, arc_vars, cp_model);
406 AddDimensions(model, arc_vars, cp_model);
407 return arc_vars;
408}
409
410// Converts a RoutingModel to a CpModelProto.
411// The mapping between CPModelProto arcs and their corresponding arc variables
412// is returned.
413ArcVarMap PopulateModelFromRoutingModel(const RoutingModel& model,
414 CpModelProto* cp_model) {
415 if (model.vehicles() == 1) {
416 return PopulateSingleRouteModelFromRoutingModel(model, cp_model);
417 }
418 return PopulateMultiRouteModelFromRoutingModel(model, cp_model);
419}
420
421// Converts a CpSolverResponse to an Assignment containing next variables.
422bool ConvertToSolution(const CpSolverResponse& response,
423 const RoutingModel& model, const ArcVarMap& arc_vars,
424 Assignment* solution) {
425 if (response.status() != CpSolverStatus::OPTIMAL &&
426 response.status() != CpSolverStatus::FEASIBLE)
427 return false;
428 const int depot = GetDepotFromModel(model);
429 int vehicle = 0;
430 for (const auto& arc_var : arc_vars) {
431 if (response.solution(arc_var.second) != 0) {
432 const int tail = arc_var.first.tail;
433 const int head = arc_var.first.head;
434 if (head == depot) continue;
435 if (tail != depot) {
436 solution->Add(model.NextVar(tail))->SetValue(head);
437 } else {
438 solution->Add(model.NextVar(model.Start(vehicle)))->SetValue(head);
439 ++vehicle;
440 }
441 }
442 }
443 // Close open routes.
444 for (int v = 0; v < model.vehicles(); ++v) {
445 int current = model.Start(v);
446 while (solution->Contains(model.NextVar(current))) {
447 current = solution->Value(model.NextVar(current));
448 }
449 solution->Add(model.NextVar(current))->SetValue(model.End(v));
450 }
451 return true;
452}
453
454void AddSolutionAsHintToModel(const Assignment* solution,
455 const RoutingModel& model,
456 const ArcVarMap& arc_vars,
457 CpModelProto* cp_model) {
458 if (solution == nullptr) return;
459 PartialVariableAssignment* const hint = cp_model->mutable_solution_hint();
460 hint->Clear();
461 const int depot = GetDepotFromModel(model);
462 const int num_nodes = model.Nexts().size();
463 for (int tail = 0; tail < num_nodes; ++tail) {
464 const int tail_index = model.IsStart(tail) ? depot : tail;
465 const int head = solution->Value(model.NextVar(tail));
466 const int head_index = model.IsEnd(head) ? depot : head;
467 if (tail_index == depot && head_index == depot) continue;
468 const int* const var_index =
469 gtl::FindOrNull(arc_vars, {tail_index, head_index});
470 // Arcs with a cost of kint64max are not added to the model (considered as
471 // infeasible). In some rare cases CP solutions might contain such arcs in
472 // which case they are skipped here and a partial solution is used as a
473 // hint.
474 if (var_index == nullptr) continue;
475 hint->add_vars(*var_index);
476 hint->add_values(1);
477 }
478}
479
480// Configures a CP-SAT solver and solves the given (routing) model using it.
481// Returns the response of the search.
482CpSolverResponse SolveRoutingModel(
483 const CpModelProto& cp_model, absl::Duration remaining_time,
484 const std::function<void(const CpSolverResponse& response)>& observer) {
485 // TODO(user): Add CP-SAT parameters to routing parameters.
486 SatParameters parameters;
487 parameters.set_linearization_level(2);
488 parameters.set_max_time_in_seconds(absl::ToDoubleSeconds(remaining_time));
489 parameters.set_num_search_workers(1);
490 Model model;
492 if (observer != nullptr) {
493 model.Add(NewFeasibleSolutionObserver(observer));
494 }
495 // TODO(user): Add an option to dump the CP-SAT model or check if the
496 // cp_model_dump_file flag in cp_model_solver.cc is good enough.
497 return SolveCpModel(cp_model, &model);
498}
499
500} // namespace
501} // namespace sat
502
503// Solves a RoutingModel using the CP-SAT solver. Returns false if no solution
504// was found.
506 const RoutingSearchParameters& search_parameters,
507 const Assignment* initial_solution,
508 Assignment* solution) {
509 if (!sat::RoutingModelCanBeSolvedBySat(model)) return false;
510 sat::CpModelProto cp_model;
511 cp_model.mutable_objective()->set_scaling_factor(
512 search_parameters.log_cost_scaling_factor());
513 cp_model.mutable_objective()->set_offset(search_parameters.log_cost_offset());
514 const sat::ArcVarMap arc_vars =
515 sat::PopulateModelFromRoutingModel(model, &cp_model);
516 sat::AddSolutionAsHintToModel(initial_solution, model, arc_vars, &cp_model);
517 return sat::ConvertToSolution(
518 sat::SolveRoutingModel(cp_model, model.RemainingTime(), nullptr), model,
519 arc_vars, solution);
520}
521
522} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
An Assignment is a variable -> domains mapping, used to report solutions to the user.
RoutingTransitCallback1 TransitCallback1
Definition: routing.h:242
RoutingTransitCallback2 TransitCallback2
Definition: routing.h:243
This file implements a wrapper around the CP-SAT model proto.
SatParameters parameters
SharedResponseManager * response
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
GRBmodel * model
static const int64 kint64max
int64_t int64
bool operator!=(const STLCountingAllocator< T, A > &a, const STLCountingAllocator< T, A > &b)
Definition: stl_util.h:985
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
void InsertOrDie(Collection *const collection, const typename Collection::value_type &value)
Definition: map_util.h:135
const Collection::value_type::second_type * FindOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:41
std::function< void(Model *)> NewFeasibleSolutionObserver(const std::function< void(const CpSolverResponse &response)> &observer)
Creates a solution observer with the model with model.Add(NewFeasibleSolutionObserver([](response){....
std::ostream & operator<<(std::ostream &os, const BoolVar &var)
Definition: cp_model.cc:65
std::function< SatParameters(Model *)> NewSatParameters(const std::string &params)
Creates parameters for the solver, which you can add to the model with.
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
CpSolverResponse SolveCpModel(const CpModelProto &model_proto, Model *model)
Solves the given CpModelProto.
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool SolveModelWithSat(const RoutingModel &model, const RoutingSearchParameters &search_parameters, const Assignment *initial_solution, Assignment *solution)
Attempts to solve the model using the cp-sat solver.
Definition: routing_sat.cc:505
int64 CapAdd(int64 x, int64 y)
int64 CapSub(int64 x, int64 y)
std::pair< int64, int64 > Arc
Definition: search.cc:3361
LinearRange operator==(const LinearExpr &lhs, const LinearExpr &rhs)
Definition: linear_expr.cc:180
int index
Definition: pack.cc:508
int64 cost
int head
Definition: routing_sat.cc:44
int tail
Definition: routing_sat.cc:43