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 
15 #include "ortools/sat/cp_model.h"
16 
17 namespace operations_research {
18 namespace sat {
19 namespace {
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.
25 bool 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.
30 int 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).
39 int64 GetDepotFromModel(const RoutingModel& model) { return model.Start(0); }
40 
41 // Structure to keep track of arcs created.
42 struct 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 
62 using 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.
66 void 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 
108 std::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.
142 std::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 
181 void 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.
222 ArcVarMap 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.
377 ArcVarMap 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.
413 ArcVarMap 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.
422 bool 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 
454 void 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.
482 CpSolverResponse 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
void InsertOrDie(Collection *const collection, const typename Collection::value_type &value)
Definition: map_util.h:135
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
const Collection::value_type::second_type * FindOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:41
bool operator!=(const STLCountingAllocator< T, A > &a, const STLCountingAllocator< T, A > &b)
Definition: stl_util.h:985
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){....
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
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.
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 CapSub(int64 x, int64 y)
std::pair< int64, int64 > Arc
Definition: search.cc:3361
int64 CapAdd(int64 x, int64 y)
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