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
27namespace 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.
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 }
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 }
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 }
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
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
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_
const RoutingDimension & dimension() const
bool PropagateCumulBounds(const std::function< int64(int64)> &next_accessor, int64 cumul_offset)
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
int AddReifiedLinearConstraint(int64 lower_bound, int64 upper_bound, const std::vector< std::pair< int, double > > &weighted_variables)
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
virtual int64 GetVariableLowerBound(int index) const =0
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
int AddLinearConstraint(int64 lower_bound, int64 upper_bound, const std::vector< std::pair< int, double > > &variable_coeffs)
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...