OR-Tools  8.1
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 preformance 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  ct->add_vars(gtl::FindOrDie(arc_vars, {depot, node}));
265  ct->add_coeffs(1);
266  ct->add_vars(gtl::FindOrDie(arc_vars, {node, depot}));
267  ct->add_coeffs(-1);
268  }
269  }
270 
271  {
272  LinearConstraintProto* ct = cp_model->add_constraints()->mutable_linear();
273  ct->add_domain(0);
274  // Taking the min since as of 04/2020 fleet is homogeneous.
275  ct->add_domain(
276  std::min(model.vehicles(), model.GetMaximumNumberOfActiveVehicles()));
277  for (int node = 0; node < num_nodes; ++node) {
278  if (model.IsStart(node) || model.IsEnd(node)) continue;
279  ct->add_vars(gtl::FindOrDie(arc_vars, {depot, node}));
280  ct->add_coeffs(1);
281  }
282  }
283 
284  for (int tail = 0; tail < num_nodes; ++tail) {
285  if (model.IsStart(tail) || model.IsEnd(tail)) continue;
286  LinearConstraintProto* ct = cp_model->add_constraints()->mutable_linear();
287  ct->add_domain(1);
288  ct->add_domain(1);
289  std::unique_ptr<IntVarIterator> iter(
290  model.NextVar(tail)->MakeDomainIterator(false));
291  bool depot_added = false;
292  for (int head : InitAndGetValues(iter.get())) {
293  if (model.IsStart(head)) continue;
294  if (tail == head) continue;
295  if (model.IsEnd(head)) {
296  if (depot_added) continue;
297  head = depot;
298  depot_added = true;
299  }
300  ct->add_vars(gtl::FindOrDie(arc_vars, {tail, head}));
301  ct->add_coeffs(1);
302  }
303  }
304 
305  for (int head = 0; head < num_nodes; ++head) {
306  if (model.IsStart(head) || model.IsEnd(head)) continue;
307  LinearConstraintProto* ct = cp_model->add_constraints()->mutable_linear();
308  ct->add_domain(1);
309  ct->add_domain(1);
310  for (int tail = 0; tail < num_nodes; ++tail) {
311  if (model.IsEnd(head)) continue;
312  if (tail == head) continue;
313  if (model.IsStart(tail) && tail != depot) continue;
314  ct->add_vars(gtl::FindOrDie(arc_vars, {tail, head}));
315  ct->add_coeffs(1);
316  }
317  }
318 
319  AddPickupDeliveryConstraints(model, arc_vars, cp_model);
320 
321  AddDimensions(model, arc_vars, cp_model);
322 
323  // Create Routes constraint, ensuring circuits from and to the depot.
324  // This one is a bit tricky, because we need to remap the depot to zero.
325  // TODO(user): Make Routes constraints support optional nodes.
326  RoutesConstraintProto* routes_ct =
327  cp_model->add_constraints()->mutable_routes();
328  for (const auto arc_var : arc_vars) {
329  const int tail = arc_var.first.tail;
330  const int head = arc_var.first.head;
331  routes_ct->add_tails(tail == 0 ? depot : tail == depot ? 0 : tail);
332  routes_ct->add_heads(head == 0 ? depot : head == depot ? 0 : head);
333  routes_ct->add_literals(arc_var.second);
334  }
335 
336  // Add demands and capacities to improve the LP relaxation and cuts. These are
337  // based on the first "unary" dimension in the model if it exists.
338  // TODO(user): We might want to try to get demand lower bounds from
339  // non-unary dimensions if no unary exist.
340  const RoutingDimension* master_dimension = nullptr;
341  for (const RoutingDimension* dimension : model.GetDimensions()) {
342  // Only a single vehicle class is supported.
343  if (dimension->GetUnaryTransitEvaluator(0) != nullptr) {
344  master_dimension = dimension;
345  break;
346  }
347  }
348  if (master_dimension != nullptr) {
349  const RoutingModel::TransitCallback1& transit =
350  master_dimension->GetUnaryTransitEvaluator(0);
351  for (int node = 0; node < num_nodes; ++node) {
352  // Tricky: demand is added for all nodes in the sat model; this means
353  // start/end nodes other than the one used for the depot must be ignored.
354  if (!model.IsEnd(node) && (!model.IsStart(node) || node == depot)) {
355  routes_ct->add_demands(transit(node));
356  }
357  }
358  DCHECK_EQ(routes_ct->demands_size(), num_nodes + 1 - model.vehicles());
359  routes_ct->set_capacity(master_dimension->vehicle_capacities()[0]);
360  }
361  return arc_vars;
362 }
363 
364 // Converts a RoutingModel with a single vehicle to a CpModelProto.
365 // The mapping between CPModelProto arcs and their corresponding arc variables
366 // is returned.
367 ArcVarMap PopulateSingleRouteModelFromRoutingModel(const RoutingModel& model,
368  CpModelProto* cp_model) {
369  ArcVarMap arc_vars;
370  const int num_nodes = model.Nexts().size();
371  CircuitConstraintProto* circuit =
372  cp_model->add_constraints()->mutable_circuit();
373  for (int tail = 0; tail < num_nodes; ++tail) {
374  std::unique_ptr<IntVarIterator> iter(
375  model.NextVar(tail)->MakeDomainIterator(false));
376  for (int head : InitAndGetValues(iter.get())) {
377  // Vehicle start and end nodes are represented as a single node in the
378  // CP-SAT model. We choose the start index to represent both. We can also
379  // skip any head representing a vehicle start as the CP solver will reject
380  // those.
381  if (model.IsStart(head)) continue;
382  if (model.IsEnd(head)) head = model.Start(0);
383  const int64 cost = tail != head ? model.GetHomogeneousCost(tail, head)
384  : model.UnperformedPenalty(tail);
385  if (cost == kint64max) continue;
386  const int index = AddVariable(cp_model, 0, 1);
387  circuit->add_literals(index);
388  circuit->add_tails(tail);
389  circuit->add_heads(head);
390  cp_model->mutable_objective()->add_vars(index);
391  cp_model->mutable_objective()->add_coeffs(cost);
392  gtl::InsertOrDie(&arc_vars, {tail, head}, index);
393  }
394  }
395  AddPickupDeliveryConstraints(model, arc_vars, cp_model);
396  AddDimensions(model, arc_vars, cp_model);
397  return arc_vars;
398 }
399 
400 // Converts a RoutingModel to a CpModelProto.
401 // The mapping between CPModelProto arcs and their corresponding arc variables
402 // is returned.
403 ArcVarMap PopulateModelFromRoutingModel(const RoutingModel& model,
404  CpModelProto* cp_model) {
405  if (model.vehicles() == 1) {
406  return PopulateSingleRouteModelFromRoutingModel(model, cp_model);
407  }
408  return PopulateMultiRouteModelFromRoutingModel(model, cp_model);
409 }
410 
411 // Converts a CpSolverResponse to an Assignment containing next variables.
412 bool ConvertToSolution(const CpSolverResponse& response,
413  const RoutingModel& model, const ArcVarMap& arc_vars,
414  Assignment* solution) {
415  if (response.status() != CpSolverStatus::OPTIMAL &&
417  return false;
418  const int depot = GetDepotFromModel(model);
419  int vehicle = 0;
420  for (const auto& arc_var : arc_vars) {
421  if (response.solution(arc_var.second) != 0) {
422  const int tail = arc_var.first.tail;
423  const int head = arc_var.first.head;
424  if (head == depot) continue;
425  if (tail != depot) {
426  solution->Add(model.NextVar(tail))->SetValue(head);
427  } else {
428  solution->Add(model.NextVar(model.Start(vehicle)))->SetValue(head);
429  ++vehicle;
430  }
431  }
432  }
433  // Close open routes.
434  for (int v = 0; v < model.vehicles(); ++v) {
435  int current = model.Start(v);
436  while (solution->Contains(model.NextVar(current))) {
437  current = solution->Value(model.NextVar(current));
438  }
439  solution->Add(model.NextVar(current))->SetValue(model.End(v));
440  }
441  return true;
442 }
443 
444 void AddSolutionAsHintToModel(const Assignment* solution,
445  const RoutingModel& model,
446  const ArcVarMap& arc_vars,
447  CpModelProto* cp_model) {
448  if (solution == nullptr) return;
449  PartialVariableAssignment* const hint = cp_model->mutable_solution_hint();
450  hint->Clear();
451  const int depot = GetDepotFromModel(model);
452  const int num_nodes = model.Nexts().size();
453  for (int tail = 0; tail < num_nodes; ++tail) {
454  const int tail_index = model.IsStart(tail) ? depot : tail;
455  const int head = solution->Value(model.NextVar(tail));
456  const int head_index = model.IsEnd(head) ? depot : head;
457  if (tail_index == depot && head_index == depot) continue;
458  const int* const var_index =
459  gtl::FindOrNull(arc_vars, {tail_index, head_index});
460  // Arcs with a cost of kint64max are not added to the model (considered as
461  // infeasible). In some rare cases CP solutions might contain such arcs in
462  // which case they are skipped here and a partial solution is used as a
463  // hint.
464  if (var_index == nullptr) continue;
465  hint->add_vars(*var_index);
466  hint->add_values(1);
467  }
468 }
469 
470 // Configures a CP-SAT solver and solves the given (routing) model using it.
471 // Returns the response of the search.
472 CpSolverResponse SolveRoutingModel(
473  const CpModelProto& cp_model, absl::Duration remaining_time,
474  const std::function<void(const CpSolverResponse& response)>& observer) {
475  // TODO(user): Add CP-SAT parameters to routing parameters.
476  SatParameters parameters;
477  parameters.set_linearization_level(2);
478  parameters.set_max_time_in_seconds(absl::ToDoubleSeconds(remaining_time));
479  parameters.set_num_search_workers(1);
480  Model model;
482  if (observer != nullptr) {
483  model.Add(NewFeasibleSolutionObserver(observer));
484  }
485  // TODO(user): Add an option to dump the CP-SAT model or check if the
486  // cp_model_dump_file flag in cp_model_solver.cc is good enough.
487  return SolveCpModel(cp_model, &model);
488 }
489 
490 } // namespace
491 } // namespace sat
492 
493 // Solves a RoutingModel using the CP-SAT solver. Returns false if no solution
494 // was found.
496  const RoutingSearchParameters& search_parameters,
497  const Assignment* initial_solution,
498  Assignment* solution) {
499  if (!sat::RoutingModelCanBeSolvedBySat(model)) return false;
500  sat::CpModelProto cp_model;
501  cp_model.mutable_objective()->set_scaling_factor(
502  search_parameters.log_cost_scaling_factor());
503  cp_model.mutable_objective()->set_offset(search_parameters.log_cost_offset());
504  const sat::ArcVarMap arc_vars =
505  sat::PopulateModelFromRoutingModel(model, &cp_model);
506  sat::AddSolutionAsHintToModel(initial_solution, model, arc_vars, &cp_model);
507  return sat::ConvertToSolution(
508  sat::SolveRoutingModel(cp_model, model.RemainingTime(), nullptr), model,
509  arc_vars, solution);
510 }
511 
512 } // namespace operations_research
var
IntVar * var
Definition: expr_array.cc:1858
operations_research::RoutingModel::TransitCallback1
RoutingTransitCallback1 TransitCallback1
Definition: routing.h:241
gtl::operator!=
bool operator!=(const STLCountingAllocator< T, A > &a, const STLCountingAllocator< T, A > &b)
Definition: stl_util.h:985
response
SharedResponseManager * response
Definition: cp_model_solver.cc:2105
operations_research::SolveModelWithSat
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:495
operations_research::sat::FEASIBLE
@ FEASIBLE
Definition: cp_model.pb.h:225
min
int64 min
Definition: alldiff_cst.cc:138
operations_research::Arc
std::pair< int64, int64 > Arc
Definition: search.cc:3361
operations_research::CapSub
int64 CapSub(int64 x, int64 y)
Definition: saturated_arithmetic.h:154
max
int64 max
Definition: alldiff_cst.cc:139
operations_research::RoutingModel::TransitCallback2
RoutingTransitCallback2 TransitCallback2
Definition: routing.h:242
operations_research::operator==
LinearRange operator==(const LinearExpr &lhs, const LinearExpr &rhs)
Definition: linear_expr.cc:180
operations_research::sat::NewFeasibleSolutionObserver
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){....
Definition: cp_model_solver.cc:913
routing.h
operations_research::RoutingModel
Definition: routing.h:212
value
int64 value
Definition: demon_profiler.cc:43
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::sat::operator<<
std::ostream & operator<<(std::ostream &os, const BoolVar &var)
Definition: cp_model.cc:65
int64
int64_t int64
Definition: integral_types.h:34
index
int index
Definition: pack.cc:508
gtl::FindOrDie
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:176
cost
int64 cost
Definition: routing_flow.cc:130
a
int64 a
Definition: constraint_solver/table.cc:42
operations_research::Assignment
An Assignment is a variable -> domains mapping, used to report solutions to the user.
Definition: constraint_solver.h:5033
gtl::FindOrNull
const Collection::value_type::second_type * FindOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:41
operations_research::CapAdd
int64 CapAdd(int64 x, int64 y)
Definition: saturated_arithmetic.h:124
head
int head
Definition: routing_sat.cc:44
cp_model.h
This file implements a wrapper around the CP-SAT model proto.
operations_research::sat::kMaxIntegerValue
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
ct
const Constraint * ct
Definition: demon_profiler.cc:42
operations_research::sat::OPTIMAL
@ OPTIMAL
Definition: cp_model.pb.h:227
operations_research::sat::NewSatParameters
std::function< SatParameters(Model *)> NewSatParameters(const std::string &params)
Creates parameters for the solver, which you can add to the model with.
Definition: cp_model_solver.cc:922
model
GRBmodel * model
Definition: gurobi_interface.cc:269
operations_research::sat::SolveCpModel
CpSolverResponse SolveCpModel(const CpModelProto &model_proto, Model *model)
Solves the given CpModelProto.
Definition: cp_model_solver.cc:2878
operations_research::sat::kMinIntegerValue
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
gtl::InsertOrDie
void InsertOrDie(Collection *const collection, const typename Collection::value_type &value)
Definition: map_util.h:135
DCHECK_EQ
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
b
int64 b
Definition: constraint_solver/table.cc:43
parameters
SatParameters parameters
Definition: cp_model_fz_solver.cc:108
tail
int tail
Definition: routing_sat.cc:43
kint64max
static const int64 kint64max
Definition: integral_types.h:62
gtl::ContainsKey
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170