OR-Tools  8.2
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"
23 #include "ortools/sat/cp_model.h"
24 #include "ortools/sat/cp_model.pb.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;
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  }
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_
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
#define VLOG(verboselevel)
Definition: base/logging.h:978
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)
static int64 FastInt64Round(double x)
Definition: mathutil.h:138
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
This class represents a sorted list of disjoint, closed intervals.
Iterator FirstIntervalGreaterOrEqual(int64 value) const
Returns an iterator to either:
GlopParameters * GetMutableParameters()
Definition: lp_solver.cc:119
const DenseRow & variable_values() const
Definition: lp_solver.h:100
Fractional GetObjectiveValue() const
Definition: lp_solver.cc:476
ABSL_MUST_USE_RESULT ProblemStatus Solve(const LinearProgram &lp)
Definition: lp_solver.cc:121
void SetParameters(const GlopParameters &parameters)
Definition: lp_solver.cc:113
void SetVariableBounds(ColIndex col, Fractional lower_bound, Fractional upper_bound)
Definition: lp_data.cc:248
void SetCoefficient(RowIndex row, ColIndex col, Fractional value)
Definition: lp_data.cc:316
const DenseRow & variable_lower_bounds() const
Definition: lp_data.h:228
const DenseRow & objective_coefficients() const
Definition: lp_data.h:222
void SetConstraintBounds(RowIndex row, Fractional lower_bound, Fractional upper_bound)
Definition: lp_data.cc:308
bool SolutionIsInteger(const DenseRow &solution, Fractional absolute_tolerance) const
Definition: lp_data.cc:515
void SetObjectiveCoefficient(ColIndex col, Fractional value)
Definition: lp_data.cc:325
void SetMaximizationProblem(bool maximize)
Definition: lp_data.cc:342
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
This file implements a wrapper around the CP-SAT model proto.
SatParameters parameters
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
GRBmodel * model
static const int64 kint64max
int64_t int64
static const int64 kint64min
const double kInfinity
Definition: lp_types.h:83
std::function< SatParameters(Model *)> NewSatParameters(const std::string &params)
Creates parameters for the solver, which you can add to the model with.
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...
int64 CapSub(int64 x, int64 y)
int64 CapAdd(int64 x, int64 y)
int64 CapProd(int64 x, int64 y)
int index
Definition: pack.cc:508
int64 cost
int64 head
int64 coefficient