C++ Reference

C++ Reference: Routing

routing_lp_scheduling.h
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 
14 #ifndef OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_LP_SCHEDULING_H_
15 #define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_LP_SCHEDULING_H_
16 
17 #include "absl/container/flat_hash_map.h"
18 #include "absl/memory/memory.h"
19 #include "ortools/base/mathutil.h"
21 #include "ortools/glop/lp_solver.h"
22 #include "ortools/lp_data/lp_types.h"
23 #include "ortools/sat/cp_model.h"
24 #include "ortools/sat/cp_model.pb.h"
25 #include "ortools/util/saturated_arithmetic.h"
26 
27 namespace operations_research {
28 
29 // Classes to solve dimension cumul placement (aka scheduling) problems using
30 // linear programming.
31 
32 // Utility class used in the core optimizer to tighten the cumul bounds as much
33 // as possible based on the model precedences.
35  public:
37 
38  // Tightens the cumul bounds starting from the current cumul var min/max,
39  // and propagating the precedences resulting from the next_accessor, and the
40  // dimension's precedence rules.
41  // Returns false iff the precedences are infeasible with the given routes.
42  // Otherwise, the user can call CumulMin() and CumulMax() to retrieve the new
43  // bounds of an index.
44  bool PropagateCumulBounds(const std::function<int64(int64)>& next_accessor,
45  int64 cumul_offset);
46 
47  int64 CumulMin(int index) const {
48  return propagated_bounds_[PositiveNode(index)];
49  }
50 
51  int64 CumulMax(int index) const {
52  const int64 negated_upper_bound = propagated_bounds_[NegativeNode(index)];
53  return negated_upper_bound == kint64min ? kint64max : -negated_upper_bound;
54  }
55 
56  const RoutingDimension& dimension() const { return dimension_; }
57 
58  private:
59  // An arc "tail --offset--> head" represents the relation
60  // tail + offset <= head.
61  // As arcs are stored by tail, we don't store it in the struct.
62  struct ArcInfo {
63  int head;
64  int64 offset;
65  };
66  static const int kNoParent;
67  static const int kParentToBePropagated;
68 
69  // Return the node corresponding to the lower bound of the cumul of index and
70  // -index respectively.
71  int PositiveNode(int index) const { return 2 * index; }
72  int NegativeNode(int index) const { return 2 * index + 1; }
73 
74  void AddNodeToQueue(int node) {
75  if (!node_in_queue_[node]) {
76  bf_queue_.push_back(node);
77  node_in_queue_[node] = true;
78  }
79  }
80 
81  // Adds the relation first_index + offset <= second_index, by adding arcs
82  // first_index --offset--> second_index and
83  // -second_index --offset--> -first_index.
84  void AddArcs(int first_index, int second_index, int64 offset);
85 
86  bool InitializeArcsAndBounds(const std::function<int64(int64)>& next_accessor,
87  int64 cumul_offset);
88 
89  bool UpdateCurrentLowerBoundOfNode(int node, int64 new_lb, int64 offset);
90 
91  bool DisassembleSubtree(int source, int target);
92 
93  bool CleanupAndReturnFalse() {
94  // We clean-up node_in_queue_ for future calls, and return false.
95  for (int node_to_cleanup : bf_queue_) {
96  node_in_queue_[node_to_cleanup] = false;
97  }
98  bf_queue_.clear();
99  return false;
100  }
101 
102  const RoutingDimension& dimension_;
103  const int64 num_nodes_;
104 
105  // TODO(user): Investigate if all arcs for a given tail can be created
106  // at the same time, in which case outgoing_arcs_ could point to an absl::Span
107  // for each tail index.
108  std::vector<std::vector<ArcInfo>> outgoing_arcs_;
109 
110  std::deque<int> bf_queue_;
111  std::vector<bool> node_in_queue_;
112  std::vector<int> tree_parent_node_of_;
113  // After calling PropagateCumulBounds(), for each node index n,
114  // propagated_bounds_[2*n] and -propagated_bounds_[2*n+1] respectively contain
115  // the propagated lower and upper bounds of n's cumul variable.
116  std::vector<int64> propagated_bounds_;
117 
118  // Vector used in DisassembleSubtree() to avoid memory reallocation.
119  std::vector<int> tmp_dfs_stack_;
120 
121  // Used to store the pickup/delivery pairs encountered on the routes.
122  std::vector<std::pair<int64, int64>>
123  visited_pickup_delivery_indices_for_pair_;
124 };
125 
127  // An optimal solution was found respecting all constraints.
128  OPTIMAL,
129  // An optimal solution was found, however constraints which were relaxed were
130  // violated.
132  // A solution could not be found.
133  INFEASIBLE
134 };
135 
137  public:
139  virtual void Clear() = 0;
140  virtual int CreateNewPositiveVariable() = 0;
141  virtual bool SetVariableBounds(int index, int64 lower_bound,
142  int64 upper_bound) = 0;
143  virtual void SetVariableDisjointBounds(int index,
144  const std::vector<int64>& starts,
145  const std::vector<int64>& ends) = 0;
146  virtual int64 GetVariableLowerBound(int index) const = 0;
147  virtual void SetObjectiveCoefficient(int index, double coefficient) = 0;
148  virtual double GetObjectiveCoefficient(int index) const = 0;
149  virtual void ClearObjective() = 0;
150  virtual int NumVariables() const = 0;
151  virtual int CreateNewConstraint(int64 lower_bound, int64 upper_bound) = 0;
152  virtual void SetCoefficient(int ct, int index, double coefficient) = 0;
153  virtual bool IsCPSATSolver() = 0;
154  virtual void AddMaximumConstraint(int max_var, std::vector<int> vars) = 0;
155  virtual void AddProductConstraint(int product_var, std::vector<int> vars) = 0;
156  virtual void SetEnforcementLiteral(int ct, int condition) = 0;
157  virtual DimensionSchedulingStatus Solve(absl::Duration duration_limit) = 0;
158  virtual int64 GetObjectiveValue() const = 0;
159  virtual double GetValue(int index) const = 0;
160  virtual bool SolutionIsInteger() const = 0;
161 
162  // Adds a variable with bounds [lower_bound, upper_bound].
163  int AddVariable(int64 lower_bound, int64 upper_bound) {
164  CHECK_LE(lower_bound, upper_bound);
165  const int variable = CreateNewPositiveVariable();
166  SetVariableBounds(variable, lower_bound, upper_bound);
167  return variable;
168  }
169  // Adds a linear constraint, enforcing
170  // lower_bound <= sum variable * coeff <= upper_bound,
171  // and returns the identifier of that constraint.
173  int64 lower_bound, int64 upper_bound,
174  const std::vector<std::pair<int, double>>& variable_coeffs) {
175  CHECK_LE(lower_bound, upper_bound);
176  const int ct = CreateNewConstraint(lower_bound, upper_bound);
177  for (const auto& variable_coeff : variable_coeffs) {
178  SetCoefficient(ct, variable_coeff.first, variable_coeff.second);
179  }
180  return ct;
181  }
182  // Adds a linear constraint and a 0/1 variable that is true iff
183  // lower_bound <= sum variable * coeff <= upper_bound,
184  // and returns the identifier of that variable.
186  int64 lower_bound, int64 upper_bound,
187  const std::vector<std::pair<int, double>>& weighted_variables) {
188  const int reification_ct = AddLinearConstraint(1, 1, {});
189  if (kint64min < lower_bound) {
190  const int under_lower_bound = AddVariable(0, 1);
191  SetCoefficient(reification_ct, under_lower_bound, 1);
192  const int under_lower_bound_ct =
193  AddLinearConstraint(kint64min, lower_bound - 1, weighted_variables);
194  SetEnforcementLiteral(under_lower_bound_ct, under_lower_bound);
195  }
196  if (upper_bound < kint64max) {
197  const int above_upper_bound = AddVariable(0, 1);
198  SetCoefficient(reification_ct, above_upper_bound, 1);
199  const int above_upper_bound_ct =
200  AddLinearConstraint(upper_bound + 1, kint64max, weighted_variables);
201  SetEnforcementLiteral(above_upper_bound_ct, above_upper_bound);
202  }
203  const int within_bounds = AddVariable(0, 1);
204  SetCoefficient(reification_ct, within_bounds, 1);
205  const int within_bounds_ct =
206  AddLinearConstraint(lower_bound, upper_bound, weighted_variables);
207  SetEnforcementLiteral(within_bounds_ct, within_bounds);
208  return within_bounds;
209  }
210 };
211 
213  public:
214  explicit RoutingGlopWrapper(const glop::GlopParameters& parameters) {
215  lp_solver_.SetParameters(parameters);
216  linear_program_.SetMaximizationProblem(false);
217  }
218  void Clear() override {
219  linear_program_.Clear();
220  linear_program_.SetMaximizationProblem(false);
221  allowed_intervals_.clear();
222  }
223  int CreateNewPositiveVariable() override {
224  return linear_program_.CreateNewVariable().value();
225  }
226  bool SetVariableBounds(int index, int64 lower_bound,
227  int64 upper_bound) override {
228  DCHECK_GE(lower_bound, 0);
229  // When variable upper bounds are greater than this threshold, precision
230  // issues arise in GLOP. In this case we are just going to suppose that
231  // these high bound values are infinite and not set the upper bound.
232  const int64 kMaxValue = 1e10;
233  const double lp_min = lower_bound;
234  const double lp_max =
235  (upper_bound > kMaxValue) ? glop::kInfinity : upper_bound;
236  if (lp_min <= lp_max) {
237  linear_program_.SetVariableBounds(glop::ColIndex(index), lp_min, lp_max);
238  return true;
239  }
240  // The linear_program would not be feasible, and it cannot handle the
241  // lp_min > lp_max case, so we must detect infeasibility here.
242  return false;
243  }
244  void SetVariableDisjointBounds(int index, const std::vector<int64>& starts,
245  const std::vector<int64>& ends) override {
246  // TODO(user): Investigate if we can avoid rebuilding the interval list
247  // each time (we could keep a reference to the forbidden interval list in
248  // RoutingDimension but we would need to store cumul offsets and use them
249  // when checking intervals).
250  allowed_intervals_[index] =
251  absl::make_unique<SortedDisjointIntervalList>(starts, ends);
252  }
253  int64 GetVariableLowerBound(int index) const override {
254  return linear_program_.variable_lower_bounds()[glop::ColIndex(index)];
255  }
256  void SetObjectiveCoefficient(int index, double coefficient) override {
257  linear_program_.SetObjectiveCoefficient(glop::ColIndex(index), coefficient);
258  }
259  double GetObjectiveCoefficient(int index) const override {
260  return linear_program_.objective_coefficients()[glop::ColIndex(index)];
261  }
262  void ClearObjective() override {
263  for (glop::ColIndex i(0); i < linear_program_.num_variables(); ++i) {
264  linear_program_.SetObjectiveCoefficient(i, 0);
265  }
266  }
267  int NumVariables() const override {
268  return linear_program_.num_variables().value();
269  }
270  int CreateNewConstraint(int64 lower_bound, int64 upper_bound) override {
271  const glop::RowIndex ct = linear_program_.CreateNewConstraint();
272  linear_program_.SetConstraintBounds(
273  ct, (lower_bound == kint64min) ? -glop::kInfinity : lower_bound,
274  (upper_bound == kint64max) ? glop::kInfinity : upper_bound);
275  return ct.value();
276  }
277  void SetCoefficient(int ct, int index, double coefficient) override {
278  linear_program_.SetCoefficient(glop::RowIndex(ct), glop::ColIndex(index),
279  coefficient);
280  }
281  bool IsCPSATSolver() override { return false; }
282  void AddMaximumConstraint(int max_var, std::vector<int> vars) override{};
283  void AddProductConstraint(int product_var, std::vector<int> vars) override{};
284  void SetEnforcementLiteral(int ct, int condition) override{};
285  DimensionSchedulingStatus Solve(absl::Duration duration_limit) override {
286  lp_solver_.GetMutableParameters()->set_max_time_in_seconds(
287  absl::ToDoubleSeconds(duration_limit));
288 
289  // Because we construct the lp one constraint at a time and we never call
290  // SetCoefficient() on the same variable twice for a constraint, we know
291  // that the columns do not contain duplicates and are already ordered by
292  // constraint so we do not need to call linear_program->CleanUp() which can
293  // be costly. Note that the assumptions are DCHECKed() in the call below.
294  linear_program_.NotifyThatColumnsAreClean();
295  VLOG(2) << linear_program_.Dump();
296  const glop::ProblemStatus status = lp_solver_.Solve(linear_program_);
297  if (status != glop::ProblemStatus::OPTIMAL &&
298  status != glop::ProblemStatus::IMPRECISE) {
299  linear_program_.Clear();
301  }
302  for (const auto& allowed_interval : allowed_intervals_) {
303  const double value_double = GetValue(allowed_interval.first);
304  const int64 value = (value_double >= kint64max)
305  ? kint64max
306  : MathUtil::FastInt64Round(value_double);
307  const SortedDisjointIntervalList* const interval_list =
308  allowed_interval.second.get();
309  const auto it = interval_list->FirstIntervalGreaterOrEqual(value);
310  if (it == interval_list->end() || value < it->start) {
312  }
313  }
315  }
316  int64 GetObjectiveValue() const override {
317  return MathUtil::FastInt64Round(lp_solver_.GetObjectiveValue());
318  }
319  double GetValue(int index) const override {
320  return lp_solver_.variable_values()[glop::ColIndex(index)];
321  }
322  bool SolutionIsInteger() const override {
323  return linear_program_.SolutionIsInteger(lp_solver_.variable_values(),
324  /*absolute_tolerance*/ 1e-3);
325  }
326 
327  private:
328  glop::LinearProgram linear_program_;
329  glop::LPSolver lp_solver_;
330  absl::flat_hash_map<int, std::unique_ptr<SortedDisjointIntervalList>>
331  allowed_intervals_;
332 };
333 
335  public:
336  RoutingCPSatWrapper() : objective_offset_(0), first_constraint_to_offset_(0) {
337  parameters_.set_num_search_workers(1);
338  // Keeping presolve but with 0 iterations; as of 11/2019 it is
339  // significantly faster than both full presolve and no presolve.
340  parameters_.set_cp_model_presolve(true);
341  parameters_.set_max_presolve_iterations(0);
342  parameters_.set_catch_sigint_signal(false);
343  parameters_.set_mip_max_bound(1e8);
344  parameters_.set_search_branching(sat::SatParameters::LP_SEARCH);
345  }
346  ~RoutingCPSatWrapper() override {}
347  void Clear() override {
348  model_.Clear();
349  response_.Clear();
350  objective_coefficients_.clear();
351  objective_offset_ = 0;
352  variable_offset_.clear();
353  constraint_offset_.clear();
354  first_constraint_to_offset_ = 0;
355  }
356  int CreateNewPositiveVariable() override {
357  const int index = model_.variables_size();
358  if (index >= variable_offset_.size()) {
359  variable_offset_.resize(index + 1, 0);
360  }
361  sat::IntegerVariableProto* const variable = model_.add_variables();
362  variable->add_domain(0);
363  variable->add_domain(static_cast<int64>(parameters_.mip_max_bound()));
364  return index;
365  }
366  bool SetVariableBounds(int index, int64 lower_bound,
367  int64 upper_bound) override {
368  DCHECK_GE(lower_bound, 0);
369  // TODO(user): Find whether there is a way to make the offsetting
370  // system work with other CP-SAT constraints than linear constraints.
371  // variable_offset_[index] = lower_bound;
372  variable_offset_[index] = 0;
373  const int64 offset_upper_bound =
374  std::min<int64>(CapSub(upper_bound, variable_offset_[index]),
375  parameters_.mip_max_bound());
376  const int64 offset_lower_bound =
377  CapSub(lower_bound, variable_offset_[index]);
378  if (offset_lower_bound > offset_upper_bound) return false;
379  sat::IntegerVariableProto* const variable = model_.mutable_variables(index);
380  variable->set_domain(0, offset_lower_bound);
381  variable->set_domain(1, offset_upper_bound);
382  return true;
383  }
384  void SetVariableDisjointBounds(int index, const std::vector<int64>& starts,
385  const std::vector<int64>& ends) override {
386  DCHECK_EQ(starts.size(), ends.size());
387  const int ct = CreateNewConstraint(1, 1);
388  for (int i = 0; i < starts.size(); ++i) {
389  const int variable = CreateNewPositiveVariable();
390  SetVariableBounds(variable, 0, 1);
391  SetCoefficient(ct, variable, 1);
392  const int window_ct = CreateNewConstraint(starts[i], ends[i]);
393  SetCoefficient(window_ct, index, 1);
394  model_.mutable_constraints(window_ct)->add_enforcement_literal(variable);
395  }
396  }
397  int64 GetVariableLowerBound(int index) const override {
398  return CapAdd(model_.variables(index).domain(0), variable_offset_[index]);
399  }
400  void SetObjectiveCoefficient(int index, double coefficient) override {
401  // TODO(user): Check variable bounds are never set after setting the
402  // objective coefficient.
403  if (index >= objective_coefficients_.size()) {
404  objective_coefficients_.resize(index + 1, 0);
405  }
406  objective_coefficients_[index] = coefficient;
407  sat::CpObjectiveProto* const objective = model_.mutable_objective();
408  objective->add_vars(index);
409  objective->add_coeffs(coefficient);
410  objective_offset_ += coefficient * variable_offset_[index];
411  }
412  double GetObjectiveCoefficient(int index) const override {
413  return (index < objective_coefficients_.size())
414  ? objective_coefficients_[index]
415  : 0;
416  }
417  void ClearObjective() override {
418  model_.mutable_objective()->Clear();
419  objective_offset_ = 0;
420  }
421  int NumVariables() const override { return model_.variables_size(); }
422  int CreateNewConstraint(int64 lower_bound, int64 upper_bound) override {
423  const int ct_index = model_.constraints_size();
424  if (ct_index >= constraint_offset_.size()) {
425  constraint_offset_.resize(ct_index + 1, 0);
426  }
427  sat::LinearConstraintProto* const ct =
428  model_.add_constraints()->mutable_linear();
429  ct->add_domain(lower_bound);
430  ct->add_domain(upper_bound);
431  return ct_index;
432  }
433  void SetCoefficient(int ct_index, int index, double coefficient) override {
434  // TODO(user): Check variable bounds are never set after setting the
435  // variable coefficient.
436  sat::LinearConstraintProto* const ct =
437  model_.mutable_constraints(ct_index)->mutable_linear();
438  ct->add_vars(index);
439  ct->add_coeffs(coefficient);
440  constraint_offset_[ct_index] =
441  CapAdd(constraint_offset_[ct_index],
442  CapProd(variable_offset_[index], coefficient));
443  }
444  bool IsCPSATSolver() override { return true; }
445  void AddMaximumConstraint(int max_var, std::vector<int> vars) override {
446  sat::LinearArgumentProto* const ct =
447  model_.add_constraints()->mutable_lin_max();
448  ct->mutable_target()->add_vars(max_var);
449  ct->mutable_target()->add_coeffs(1);
450  for (const int var : vars) {
451  sat::LinearExpressionProto* const expr = ct->add_exprs();
452  expr->add_vars(var);
453  expr->add_coeffs(1);
454  }
455  }
456  void AddProductConstraint(int product_var, std::vector<int> vars) override {
457  sat::IntegerArgumentProto* const ct =
458  model_.add_constraints()->mutable_int_prod();
459  ct->set_target(product_var);
460  for (const int var : vars) {
461  ct->add_vars(var);
462  }
463  }
464  void SetEnforcementLiteral(int ct, int condition) override {
465  DCHECK_LT(ct, constraint_offset_.size());
466  model_.mutable_constraints(ct)->add_enforcement_literal(condition);
467  }
468  DimensionSchedulingStatus Solve(absl::Duration duration_limit) override {
469  // Set constraint offsets
470  for (int ct_index = first_constraint_to_offset_;
471  ct_index < constraint_offset_.size(); ++ct_index) {
472  if (!model_.mutable_constraints(ct_index)->has_linear()) continue;
473  sat::LinearConstraintProto* const ct =
474  model_.mutable_constraints(ct_index)->mutable_linear();
475  ct->set_domain(0, CapSub(ct->domain(0), constraint_offset_[ct_index]));
476  ct->set_domain(1, CapSub(ct->domain(1), constraint_offset_[ct_index]));
477  }
478  first_constraint_to_offset_ = constraint_offset_.size();
479  parameters_.set_max_time_in_seconds(absl::ToDoubleSeconds(duration_limit));
480  VLOG(2) << model_.DebugString();
481  if (hint_.vars_size() == model_.variables_size()) {
482  *model_.mutable_solution_hint() = hint_;
483  }
484  sat::Model model;
485  model.Add(sat::NewSatParameters(parameters_));
486  response_ = sat::SolveCpModel(model_, &model);
487  VLOG(2) << response_.DebugString();
488  if (response_.status() == sat::CpSolverStatus::OPTIMAL ||
489  (response_.status() == sat::CpSolverStatus::FEASIBLE &&
490  !model_.has_objective())) {
491  hint_.Clear();
492  for (int i = 0; i < response_.solution_size(); ++i) {
493  hint_.add_vars(i);
494  hint_.add_values(response_.solution(i));
495  }
497  }
499  }
500  int64 GetObjectiveValue() const override {
501  return MathUtil::FastInt64Round(response_.objective_value() +
502  objective_offset_);
503  }
504  double GetValue(int index) const override {
505  return response_.solution(index) + variable_offset_[index];
506  }
507  bool SolutionIsInteger() const override { return true; }
508 
509  private:
510  sat::CpModelProto model_;
511  sat::CpSolverResponse response_;
512  sat::SatParameters parameters_;
513  std::vector<double> objective_coefficients_;
514  double objective_offset_;
515  std::vector<int64> variable_offset_;
516  std::vector<int64> constraint_offset_;
517  int first_constraint_to_offset_;
518  sat::PartialVariableAssignment hint_;
519 };
520 
521 // Utility class used in Local/GlobalDimensionCumulOptimizer to set the linear
522 // solver constraints and solve the problem.
524  public:
526  bool use_precedence_propagator);
527 
528  // In the OptimizeSingleRoute() and Optimize() methods, if both "cumul_values"
529  // and "cost" parameters are null, we don't optimize the cost and stop at the
530  // first feasible solution in the linear solver (since in this case only
531  // feasibility is of interest).
533  int vehicle, const std::function<int64(int64)>& next_accessor,
534  RoutingLinearSolverWrapper* solver, std::vector<int64>* cumul_values,
535  std::vector<int64>* break_values, int64* cost, int64* transit_cost,
536  bool clear_lp = true);
537 
538  bool Optimize(const std::function<int64(int64)>& next_accessor,
540  std::vector<int64>* cumul_values,
541  std::vector<int64>* break_values, int64* cost,
542  int64* transit_cost, bool clear_lp = true);
543 
544  bool OptimizeAndPack(const std::function<int64(int64)>& next_accessor,
546  std::vector<int64>* cumul_values,
547  std::vector<int64>* break_values);
548 
550  int vehicle, const std::function<int64(int64)>& next_accessor,
551  RoutingLinearSolverWrapper* solver, std::vector<int64>* cumul_values,
552  std::vector<int64>* break_values);
553 
554  const RoutingDimension* dimension() const { return dimension_; }
555 
556  private:
557  // Initializes the containers and given solver. Must be called prior to
558  // setting any contraints and solving.
559  void InitOptimizer(RoutingLinearSolverWrapper* solver);
560 
561  // Computes the minimum/maximum of cumuls for nodes on "route", and sets them
562  // in current_route_[min|max]_cumuls_ respectively.
563  // If the propagator_ is not null, uses the bounds tightened by the
564  // propagator.
565  // Otherwise, the bounds are computed by going over the nodes on the route
566  // using the CP bounds, and the fixed transits are used to tighten them.
567  bool ComputeRouteCumulBounds(const std::vector<int64>& route,
568  const std::vector<int64>& fixed_transits,
569  int64 cumul_offset);
570 
571  // Sets the constraints for all nodes on "vehicle"'s route according to
572  // "next_accessor". If optimize_costs is true, also sets the objective
573  // coefficients for the LP.
574  // Returns false if some infeasibility was detected, true otherwise.
575  bool SetRouteCumulConstraints(
576  int vehicle, const std::function<int64(int64)>& next_accessor,
577  int64 cumul_offset, bool optimize_costs,
578  RoutingLinearSolverWrapper* solver, int64* route_transit_cost,
579  int64* route_cost_offset);
580 
581  // Sets the global constraints on the dimension, and adds global objective
582  // cost coefficients if optimize_costs is true.
583  // NOTE: When called, the call to this function MUST come after
584  // SetRouteCumulConstraints() has been called on all routes, so that
585  // index_to_cumul_variable_ and min_start/max_end_cumul_ are correctly
586  // initialized.
587  void SetGlobalConstraints(bool optimize_costs,
589 
590  void SetValuesFromLP(const std::vector<int>& lp_variables, int64 offset,
592  std::vector<int64>* lp_values);
593 
594  // This function packs the routes of the given vehicles while keeping the cost
595  // of the LP lower than its current (supposed optimal) objective value.
596  // It does so by setting the current objective variables' coefficient to 0 and
597  // setting the coefficient of the route ends to 1, to first minimize the route
598  // ends' cumuls, and then maximizes the starts' cumuls without increasing the
599  // ends.
600  DimensionSchedulingStatus PackRoutes(std::vector<int> vehicles,
602 
603  std::unique_ptr<CumulBoundsPropagator> propagator_;
604  std::vector<int64> current_route_min_cumuls_;
605  std::vector<int64> current_route_max_cumuls_;
606  const RoutingDimension* const dimension_;
607  // Scheduler variables for current route cumuls and for all nodes cumuls.
608  std::vector<int> current_route_cumul_variables_;
609  std::vector<int> index_to_cumul_variable_;
610  // Scheduler variables for current route breaks and all vehicle breaks.
611  // There are two variables for each break: start and end.
612  // current_route_break_variables_ has variables corresponding to
613  // break[0] start, break[0] end, break[1] start, break[1] end, etc.
614  std::vector<int> current_route_break_variables_;
615  // Vector all_break_variables contains the break variables of all vehicles,
616  // in the same format as current_route_break_variables.
617  // It is the concatenation of break variables of vehicles in [0, #vehicles).
618  std::vector<int> all_break_variables_;
619  // Allows to retrieve break variables of a given vehicle: those go from
620  // all_break_variables_[vehicle_to_all_break_variables_offset_[vehicle]] to
621  // all_break_variables[vehicle_to_all_break_variables_offset_[vehicle+1]-1].
622  std::vector<int> vehicle_to_all_break_variables_offset_;
623 
624  int max_end_cumul_;
625  int min_start_cumul_;
626  std::vector<std::pair<int64, int64>>
627  visited_pickup_delivery_indices_for_pair_;
628 };
629 
630 // Class used to compute optimal values for dimension cumuls of routes,
631 // minimizing cumul soft lower and upper bound costs, and vehicle span costs of
632 // a route.
633 // In its methods, next_accessor is a callback returning the next node of a
634 // given node on a route.
636  public:
639  RoutingSearchParameters::SchedulingSolver solver_type);
640 
641  // If feasible, computes the optimal cost of the route performed by a vehicle,
642  // minimizing cumul soft lower and upper bound costs and vehicle span costs,
643  // and stores it in "optimal_cost" (if not null).
644  // Returns true iff the route respects all constraints.
646  int vehicle, const std::function<int64(int64)>& next_accessor,
647  int64* optimal_cost);
648 
649  // Same as ComputeRouteCumulCost, but the cost computed does not contain
650  // the part of the vehicle span cost due to fixed transits.
652  int vehicle, const std::function<int64(int64)>& next_accessor,
653  int64* optimal_cost_without_transits);
654 
655  // If feasible, computes the optimal values for cumul and break variables
656  // of the route performed by a vehicle, minimizing cumul soft lower, upper
657  // bound costs and vehicle span costs, stores them in "optimal_cumuls"
658  // (if not null), and optimal_breaks, and returns true.
659  // Returns false if the route is not feasible.
661  int vehicle, const std::function<int64(int64)>& next_accessor,
662  std::vector<int64>* optimal_cumuls, std::vector<int64>* optimal_breaks);
663 
664  // Similar to ComputeRouteCumuls, but also tries to pack the cumul values on
665  // the route, such that the cost remains the same, the cumul of route end is
666  // minimized, and then the cumul of the start of the route is maximized.
668  int vehicle, const std::function<int64(int64)>& next_accessor,
669  std::vector<int64>* packed_cumuls, std::vector<int64>* packed_breaks);
670 
671  const RoutingDimension* dimension() const {
672  return optimizer_core_.dimension();
673  }
674 
675  private:
676  std::vector<std::unique_ptr<RoutingLinearSolverWrapper>> solver_;
677  DimensionCumulOptimizerCore optimizer_core_;
678 };
679 
681  public:
683  // If feasible, computes the optimal cost of the entire model with regards to
684  // the optimizer_core_'s dimension costs, minimizing cumul soft lower/upper
685  // bound costs and vehicle/global span costs, and stores it in "optimal_cost"
686  // (if not null).
687  // Returns true iff all the constraints can be respected.
689  const std::function<int64(int64)>& next_accessor,
690  int64* optimal_cost_without_transits);
691  // If feasible, computes the optimal values for cumul and break variables,
692  // minimizing cumul soft lower/upper bound costs and vehicle/global span
693  // costs, stores them in "optimal_cumuls" (if not null) and optimal breaks,
694  // and returns true.
695  // Returns false if the routes are not feasible.
696  bool ComputeCumuls(const std::function<int64(int64)>& next_accessor,
697  std::vector<int64>* optimal_cumuls,
698  std::vector<int64>* optimal_breaks);
699 
700  // Returns true iff the routes resulting from the next_accessor are feasible
701  // wrt the constraints on the optimizer_core_.dimension()'s cumuls.
702  bool IsFeasible(const std::function<int64(int64)>& next_accessor);
703 
704  // Similar to ComputeCumuls, but also tries to pack the cumul values on all
705  // routes, such that the cost remains the same, the cumuls of route ends are
706  // minimized, and then the cumuls of the starts of the routes are maximized.
707  bool ComputePackedCumuls(const std::function<int64(int64)>& next_accessor,
708  std::vector<int64>* packed_cumuls,
709  std::vector<int64>* packed_breaks);
710 
711  const RoutingDimension* dimension() const {
712  return optimizer_core_.dimension();
713  }
714 
715  private:
716  std::unique_ptr<RoutingLinearSolverWrapper> solver_;
717  DimensionCumulOptimizerCore optimizer_core_;
718 };
719 
720 } // namespace operations_research
721 
722 #endif // OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_LP_SCHEDULING_H_
bool PropagateCumulBounds(const std::function< int64(int64)> &next_accessor, int64 cumul_offset)
const RoutingDimension & dimension() const
CumulBoundsPropagator(const RoutingDimension *dimension)
bool OptimizeAndPack(const std::function< int64(int64)> &next_accessor, RoutingLinearSolverWrapper *solver, std::vector< int64 > *cumul_values, std::vector< int64 > *break_values)
DimensionCumulOptimizerCore(const RoutingDimension *dimension, bool use_precedence_propagator)
bool Optimize(const std::function< int64(int64)> &next_accessor, RoutingLinearSolverWrapper *solver, std::vector< int64 > *cumul_values, std::vector< int64 > *break_values, int64 *cost, int64 *transit_cost, bool clear_lp=true)
DimensionSchedulingStatus OptimizeAndPackSingleRoute(int vehicle, const std::function< int64(int64)> &next_accessor, RoutingLinearSolverWrapper *solver, std::vector< int64 > *cumul_values, std::vector< int64 > *break_values)
DimensionSchedulingStatus OptimizeSingleRoute(int vehicle, const std::function< int64(int64)> &next_accessor, RoutingLinearSolverWrapper *solver, std::vector< int64 > *cumul_values, std::vector< int64 > *break_values, int64 *cost, int64 *transit_cost, bool clear_lp=true)
bool ComputeCumuls(const std::function< int64(int64)> &next_accessor, std::vector< int64 > *optimal_cumuls, std::vector< int64 > *optimal_breaks)
bool IsFeasible(const std::function< int64(int64)> &next_accessor)
GlobalDimensionCumulOptimizer(const RoutingDimension *dimension)
bool ComputeCumulCostWithoutFixedTransits(const std::function< int64(int64)> &next_accessor, int64 *optimal_cost_without_transits)
bool ComputePackedCumuls(const std::function< int64(int64)> &next_accessor, std::vector< int64 > *packed_cumuls, std::vector< int64 > *packed_breaks)
DimensionSchedulingStatus ComputePackedRouteCumuls(int vehicle, const std::function< int64(int64)> &next_accessor, std::vector< int64 > *packed_cumuls, std::vector< int64 > *packed_breaks)
LocalDimensionCumulOptimizer(const RoutingDimension *dimension, RoutingSearchParameters::SchedulingSolver solver_type)
DimensionSchedulingStatus ComputeRouteCumuls(int vehicle, const std::function< int64(int64)> &next_accessor, std::vector< int64 > *optimal_cumuls, std::vector< int64 > *optimal_breaks)
DimensionSchedulingStatus ComputeRouteCumulCost(int vehicle, const std::function< int64(int64)> &next_accessor, int64 *optimal_cost)
DimensionSchedulingStatus ComputeRouteCumulCostWithoutFixedTransits(int vehicle, const std::function< int64(int64)> &next_accessor, int64 *optimal_cost_without_transits)
void SetCoefficient(int ct_index, int index, double coefficient) override
void SetVariableDisjointBounds(int index, const std::vector< int64 > &starts, const std::vector< int64 > &ends) override
double GetValue(int index) const override
DimensionSchedulingStatus Solve(absl::Duration duration_limit) override
void AddMaximumConstraint(int max_var, std::vector< int > vars) override
void AddProductConstraint(int product_var, std::vector< int > vars) override
bool SetVariableBounds(int index, int64 lower_bound, int64 upper_bound) override
void SetEnforcementLiteral(int ct, int condition) override
double GetObjectiveCoefficient(int index) const override
int CreateNewConstraint(int64 lower_bound, int64 upper_bound) override
int64 GetVariableLowerBound(int index) const override
void SetObjectiveCoefficient(int index, double coefficient) override
Dimensions represent quantities accumulated at nodes along the routes.
Definition: routing.h:2368
void SetVariableDisjointBounds(int index, const std::vector< int64 > &starts, const std::vector< int64 > &ends) override
double GetValue(int index) const override
DimensionSchedulingStatus Solve(absl::Duration duration_limit) override
void SetCoefficient(int ct, int index, double coefficient) override
void AddMaximumConstraint(int max_var, std::vector< int > vars) override
void AddProductConstraint(int product_var, std::vector< int > vars) override
bool SetVariableBounds(int index, int64 lower_bound, int64 upper_bound) override
void SetEnforcementLiteral(int ct, int condition) override
double GetObjectiveCoefficient(int index) const override
RoutingGlopWrapper(const glop::GlopParameters &parameters)
int CreateNewConstraint(int64 lower_bound, int64 upper_bound) override
int64 GetVariableLowerBound(int index) const override
void SetObjectiveCoefficient(int index, double coefficient) override
virtual void SetCoefficient(int ct, int index, double coefficient)=0
virtual int CreateNewConstraint(int64 lower_bound, int64 upper_bound)=0
virtual void SetVariableDisjointBounds(int index, const std::vector< int64 > &starts, const std::vector< int64 > &ends)=0
virtual double GetObjectiveCoefficient(int index) const =0
virtual void AddProductConstraint(int product_var, std::vector< int > vars)=0
int AddReifiedLinearConstraint(int64 lower_bound, int64 upper_bound, const std::vector< std::pair< int, double >> &weighted_variables)
virtual int64 GetVariableLowerBound(int index) const =0
int AddLinearConstraint(int64 lower_bound, int64 upper_bound, const std::vector< std::pair< int, double >> &variable_coeffs)
virtual bool SetVariableBounds(int index, int64 lower_bound, int64 upper_bound)=0
virtual double GetValue(int index) const =0
virtual DimensionSchedulingStatus Solve(absl::Duration duration_limit)=0
virtual void SetObjectiveCoefficient(int index, double coefficient)=0
int AddVariable(int64 lower_bound, int64 upper_bound)
virtual void SetEnforcementLiteral(int ct, int condition)=0
virtual void AddMaximumConstraint(int max_var, std::vector< int > vars)=0
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...