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"
24#include "ortools/sat/cp_model.pb.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;
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),
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 &&
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 }
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_
#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
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)
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
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
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
Fractional GetObjectiveValue() const
Definition: lp_solver.cc:476
const DenseRow & variable_values() const
Definition: lp_solver.h:100
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
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
const DenseRow & objective_coefficients() const
Definition: lp_data.h:222
void SetObjectiveCoefficient(ColIndex col, Fractional value)
Definition: lp_data.cc:325
const DenseRow & variable_lower_bounds() const
Definition: lp_data.h:228
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 CapAdd(int64 x, int64 y)
int64 CapProd(int64 x, int64 y)
int64 CapSub(int64 x, int64 y)
int index
Definition: pack.cc:508
int64 cost
int64 head
int64 coefficient