OR-Tools  8.2
synchronization.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
15
16#if !defined(__PORTABLE_PLATFORM__)
17#include "ortools/base/file.h"
19#endif // __PORTABLE_PLATFORM__
20
21#include "absl/container/flat_hash_set.h"
22#include "absl/random/random.h"
25#include "ortools/sat/cp_model.pb.h"
27#include "ortools/sat/integer.h"
29#include "ortools/sat/model.h"
32
33ABSL_FLAG(bool, cp_model_dump_solutions, false,
34 "DEBUG ONLY. If true, all the intermediate solution will be dumped "
35 "under '\"FLAGS_cp_model_dump_prefix\" + \"solution_xxx.pb.txt\"'.");
36
38 std::string, cp_model_load_debug_solution, "",
39 "DEBUG ONLY. When this is set to a non-empty file name, "
40 "we will interpret this as an internal solution which can be used for "
41 "debugging. For instance we use it to identify wrong cuts/reasons.");
42
43namespace operations_research {
44namespace sat {
45
47 const CpSolverResponse& response) {
48 // Note that the Add() method already applies mutex lock. So we don't need it
49 // here.
50 if (response.solution().empty()) return;
51
52 // Add this solution to the pool.
54 solution.variable_values.assign(response.solution().begin(),
55 response.solution().end());
56 // For now we use the negated lower bound as the "internal objective" to
57 // prefer solution with an higher bound.
58 //
59 // Note: If the model doesn't have objective, the best_objective_bound is set
60 // to default value 0.
61 solution.rank = -response.best_objective_bound();
62
63 Add(solution);
64}
65
67 std::vector<double> lp_solution) {
68 if (lp_solution.empty()) return;
69
70 // Add this solution to the pool.
72 solution.variable_values = std::move(lp_solution);
73
74 // We always prefer to keep the solution from the last synchronize batch.
75 absl::MutexLock mutex_lock(&mutex_);
76 solution.rank = -num_synchronization_;
77 AddInternal(solution);
78}
79
81 absl::MutexLock mutex_lock(&mutex_);
82 return !solutions_.empty();
83}
84
86 absl::MutexLock mutex_lock(&mutex_);
87 std::vector<double> solution;
88 if (solutions_.empty()) return solution;
89
90 solution = std::move(solutions_.back());
91 solutions_.pop_back();
92 return solution;
93}
94
96 const std::vector<double>& lp_solution) {
97 absl::MutexLock mutex_lock(&mutex_);
98 solutions_.push_back(lp_solution);
99}
100
101// TODO(user): Experiments and play with the num_solutions_to_keep parameter.
103 bool enumerate_all_solutions,
104 const CpModelProto* proto,
105 const WallTimer* wall_timer,
106 SharedTimeLimit* shared_time_limit)
107 : log_updates_(log_updates),
108 enumerate_all_solutions_(enumerate_all_solutions),
109 model_proto_(*proto),
110 wall_timer_(*wall_timer),
111 shared_time_limit_(shared_time_limit),
112 solutions_(/*num_solutions_to_keep=*/3) {}
113
114namespace {
115
116void LogProgress(const std::string& event_or_solution_count,
117 double time_in_seconds, double obj_best, double obj_lb,
118 double obj_ub, const std::string& solution_info) {
119 const std::string obj_next =
120 absl::StrFormat("next:[%.9g,%.9g]", obj_lb, obj_ub);
121 LOG(INFO) << absl::StrFormat("#%-5s %6.2fs best:%-5.9g %-15s %s",
122 event_or_solution_count, time_in_seconds,
123 obj_best, obj_next, solution_info);
124}
125
126void LogSatProgress(const std::string& event_or_solution_count,
127 double time_in_seconds, const std::string& solution_info) {
128 LOG(INFO) << absl::StrFormat("#%-5s %6.2fs %s", event_or_solution_count,
129 time_in_seconds, solution_info);
130}
131
132} // namespace
133
135 absl::MutexLock mutex_lock(&mutex_);
136 update_integral_on_each_change_ = set;
137}
138
140 absl::MutexLock mutex_lock(&mutex_);
141 UpdatePrimalIntegralInternal();
142}
143
144void SharedResponseManager::UpdatePrimalIntegralInternal() {
145 if (!model_proto_.has_objective()) return;
146
147 const double current_time = shared_time_limit_->GetElapsedDeterministicTime();
148 const double time_delta = current_time - last_primal_integral_time_stamp_;
149
150 // We use the log of the absolute objective gap.
151 //
152 // Using the log should count no solution as just log(2*64) = 18, and
153 // otherwise just compare order of magnitude which seems nice. Also, It is
154 // more easy to compare the primal integral with the total time.
155 const CpObjectiveProto& obj = model_proto_.objective();
156 const double factor =
157 obj.scaling_factor() != 0.0 ? std::abs(obj.scaling_factor()) : 1.0;
158 const double bounds_delta = std::log(1 + factor * last_absolute_gap_);
159 primal_integral_ += time_delta * bounds_delta;
160
161 // Update with new value.
162 last_primal_integral_time_stamp_ = current_time;
163 last_absolute_gap_ =
164 std::max(0.0, static_cast<double>(inner_objective_upper_bound_) -
165 static_cast<double>(inner_objective_lower_bound_));
166}
167
169 const SatParameters& parameters) {
170 absl::MutexLock mutex_lock(&mutex_);
171 if (!model_proto_.has_objective()) return;
172 absolute_gap_limit_ = parameters.absolute_gap_limit();
173 relative_gap_limit_ = parameters.relative_gap_limit();
174}
175
176void SharedResponseManager::TestGapLimitsIfNeeded() {
177 // This is called on each internal limit change, so it is a good place to
178 // update the integral. Note that this is not called at the end of the search
179 // though.
180 if (update_integral_on_each_change_) UpdatePrimalIntegralInternal();
181
182 if (absolute_gap_limit_ == 0 && relative_gap_limit_ == 0) return;
183 if (best_solution_objective_value_ >= kMaxIntegerValue) return;
184 if (inner_objective_lower_bound_ <= kMinIntegerValue) return;
185
186 const CpObjectiveProto& obj = model_proto_.objective();
187 const double user_best =
188 ScaleObjectiveValue(obj, best_solution_objective_value_);
189 const double user_bound =
190 ScaleObjectiveValue(obj, inner_objective_lower_bound_);
191 const double gap = std::abs(user_best - user_bound);
192 if (gap <= absolute_gap_limit_) {
193 LOG_IF(INFO, log_updates_)
194 << "Absolute gap limit of " << absolute_gap_limit_ << " reached.";
195 best_response_.set_status(CpSolverStatus::OPTIMAL);
196
197 // Note(user): Some code path in single-thread assumes that the problem
198 // can only be solved when they have proven infeasibility and do not check
199 // the ProblemIsSolved() method. So we force a stop here.
200 shared_time_limit_->Stop();
201 }
202 if (gap / std::max(1.0, std::abs(user_best)) < relative_gap_limit_) {
203 LOG_IF(INFO, log_updates_)
204 << "Relative gap limit of " << relative_gap_limit_ << " reached.";
205 best_response_.set_status(CpSolverStatus::OPTIMAL);
206
207 // Same as above.
208 shared_time_limit_->Stop();
209 }
210}
211
213 const std::string& update_info, IntegerValue lb, IntegerValue ub) {
214 absl::MutexLock mutex_lock(&mutex_);
215 CHECK(model_proto_.has_objective());
216
217 // The problem is already solved!
218 //
219 // TODO(user): A thread might not be notified right away that the new bounds
220 // that it is pushing make the problem infeasible. Fix that. For now we just
221 // abort early here to avoid logging the "#Done" message multiple times.
222 if (inner_objective_lower_bound_ > inner_objective_upper_bound_) {
223 return;
224 }
225
226 const bool change =
227 (lb > inner_objective_lower_bound_ || ub < inner_objective_upper_bound_);
228 if (lb > inner_objective_lower_bound_) {
229 // When the improving problem is infeasible, it is possible to report
230 // arbitrary high inner_objective_lower_bound_. We make sure it never cross
231 // the current best solution, so that we always report globablly valid lower
232 // bound.
233 DCHECK_LE(inner_objective_upper_bound_, best_solution_objective_value_);
234 inner_objective_lower_bound_ =
235 std::min(best_solution_objective_value_, lb.value());
236 }
237 if (ub < inner_objective_upper_bound_) {
238 inner_objective_upper_bound_ = ub.value();
239 }
240 if (inner_objective_lower_bound_ > inner_objective_upper_bound_) {
241 if (best_response_.status() == CpSolverStatus::FEASIBLE ||
242 best_response_.status() == CpSolverStatus::OPTIMAL) {
243 best_response_.set_status(CpSolverStatus::OPTIMAL);
244 } else {
245 best_response_.set_status(CpSolverStatus::INFEASIBLE);
246 }
247 if (update_integral_on_each_change_) UpdatePrimalIntegralInternal();
248 if (log_updates_) LogSatProgress("Done", wall_timer_.Get(), update_info);
249 return;
250 }
251 if (log_updates_ && change) {
252 const CpObjectiveProto& obj = model_proto_.objective();
253 const double best =
254 ScaleObjectiveValue(obj, best_solution_objective_value_);
255 double new_lb = ScaleObjectiveValue(obj, inner_objective_lower_bound_);
256 double new_ub = ScaleObjectiveValue(obj, inner_objective_upper_bound_);
257 if (model_proto_.objective().scaling_factor() < 0) {
258 std::swap(new_lb, new_ub);
259 }
260 RegisterObjectiveBoundImprovement(update_info);
261 LogProgress("Bound", wall_timer_.Get(), best, new_lb, new_ub, update_info);
262 }
263 if (change) TestGapLimitsIfNeeded();
264}
265
266// Invariant: the status always start at UNKNOWN and can only evolve as follow:
267// UNKNOWN -> FEASIBLE -> OPTIMAL
268// UNKNOWN -> INFEASIBLE
270 const std::string& worker_info) {
271 absl::MutexLock mutex_lock(&mutex_);
272 if (best_response_.status() == CpSolverStatus::FEASIBLE ||
273 best_response_.status() == CpSolverStatus::OPTIMAL) {
274 // We also use this status to indicate that we enumerated all solutions to
275 // a feasible problem.
276 best_response_.set_status(CpSolverStatus::OPTIMAL);
277 if (!model_proto_.has_objective()) {
278 best_response_.set_all_solutions_were_found(true);
279 }
280
281 // We just proved that the best solution cannot be improved uppon, so we
282 // have a new lower bound.
283 inner_objective_lower_bound_ = best_solution_objective_value_;
284 if (update_integral_on_each_change_) UpdatePrimalIntegralInternal();
285 } else {
286 CHECK_EQ(num_solutions_, 0);
287 best_response_.set_status(CpSolverStatus::INFEASIBLE);
288 }
289 if (log_updates_) LogSatProgress("Done", wall_timer_.Get(), worker_info);
290}
291
292void SharedResponseManager::AddUnsatCore(const std::vector<int>& core) {
293 absl::MutexLock mutex_lock(&mutex_);
294 best_response_.clear_sufficient_assumptions_for_infeasibility();
295 for (const int ref : core) {
296 best_response_.add_sufficient_assumptions_for_infeasibility(ref);
297 }
298}
299
301 absl::MutexLock mutex_lock(&mutex_);
302 return IntegerValue(inner_objective_lower_bound_);
303}
304
306 absl::MutexLock mutex_lock(&mutex_);
307 return IntegerValue(inner_objective_upper_bound_);
308}
309
311 absl::MutexLock mutex_lock(&mutex_);
312 synchronized_inner_objective_lower_bound_ =
313 IntegerValue(inner_objective_lower_bound_);
314 synchronized_inner_objective_upper_bound_ =
315 IntegerValue(inner_objective_upper_bound_);
316}
317
319 absl::MutexLock mutex_lock(&mutex_);
320 return synchronized_inner_objective_lower_bound_;
321}
322
324 absl::MutexLock mutex_lock(&mutex_);
325 return synchronized_inner_objective_upper_bound_;
326}
327
329 absl::MutexLock mutex_lock(&mutex_);
330 return IntegerValue(best_solution_objective_value_);
331}
332
334 absl::MutexLock mutex_lock(&mutex_);
335 return primal_integral_;
336}
337
339 std::function<void(const CpSolverResponse&)> callback) {
340 absl::MutexLock mutex_lock(&mutex_);
341 const int id = next_callback_id_++;
342 callbacks_.emplace_back(id, std::move(callback));
343 return id;
344}
345
347 absl::MutexLock mutex_lock(&mutex_);
348 for (int i = 0; i < callbacks_.size(); ++i) {
349 if (callbacks_[i].first == callback_id) {
350 callbacks_.erase(callbacks_.begin() + i);
351 return;
352 }
353 }
354 LOG(DFATAL) << "Callback id " << callback_id << " not registered.";
355}
356
358 absl::MutexLock mutex_lock(&mutex_);
359 FillObjectiveValuesInBestResponse();
360 return best_response_;
361}
362
363void SharedResponseManager::FillObjectiveValuesInBestResponse() {
364 if (!model_proto_.has_objective()) return;
365 const CpObjectiveProto& obj = model_proto_.objective();
366
367 if (best_response_.status() == CpSolverStatus::INFEASIBLE) {
368 best_response_.clear_objective_value();
369 best_response_.clear_best_objective_bound();
370 return;
371 }
372
373 // Set the objective value.
374 // If we don't have any solution, we use our inner bound.
375 if (best_response_.status() == CpSolverStatus::UNKNOWN) {
376 best_response_.set_objective_value(
377 ScaleObjectiveValue(obj, inner_objective_upper_bound_));
378 } else {
379 best_response_.set_objective_value(
380 ScaleObjectiveValue(obj, best_solution_objective_value_));
381 }
382
383 // Update the best bound in the response.
384 best_response_.set_best_objective_bound(
385 ScaleObjectiveValue(obj, inner_objective_lower_bound_));
386
387 // Update the primal integral.
388 best_response_.set_primal_integral(primal_integral_);
389}
390
391void SharedResponseManager::NewSolution(const CpSolverResponse& response,
392 Model* model) {
393 absl::MutexLock mutex_lock(&mutex_);
394
395 if (model_proto_.has_objective()) {
396 const int64 objective_value =
397 ComputeInnerObjective(model_proto_.objective(), response);
398
399 // Add this solution to the pool, even if it is not improving.
400 if (!response.solution().empty()) {
402 solution.variable_values.assign(response.solution().begin(),
403 response.solution().end());
404 solution.rank = objective_value;
405 solutions_.Add(solution);
406 }
407
408 // Ignore any non-strictly improving solution.
409 if (objective_value > inner_objective_upper_bound_) return;
410
411 // Our inner_objective_lower_bound_ should be a globaly valid bound, until
412 // the problem become infeasible (i.e the lb > ub) in which case the bound
413 // is no longer globally valid. Here, because we have a strictly improving
414 // solution, we shouldn't be in the infeasible setting yet.
415 DCHECK_GE(objective_value, inner_objective_lower_bound_);
416
417 DCHECK_LT(objective_value, best_solution_objective_value_);
418 best_solution_objective_value_ = objective_value;
419
420 // Update the new bound.
421 inner_objective_upper_bound_ = objective_value - 1;
422 }
423
424 // Note that the objective will be filled by
425 // FillObjectiveValuesInBestResponse().
426 if (!model_proto_.has_objective() && !enumerate_all_solutions_) {
427 best_response_.set_status(CpSolverStatus::OPTIMAL);
428 } else {
429 best_response_.set_status(CpSolverStatus::FEASIBLE);
430 }
431
432 best_response_.set_solution_info(response.solution_info());
433 *best_response_.mutable_solution() = response.solution();
434 *best_response_.mutable_solution_lower_bounds() =
435 response.solution_lower_bounds();
436 *best_response_.mutable_solution_upper_bounds() =
437 response.solution_upper_bounds();
438
439 // Mark model as OPTIMAL if the inner bound crossed.
440 if (model_proto_.has_objective() &&
441 inner_objective_lower_bound_ > inner_objective_upper_bound_) {
442 best_response_.set_status(CpSolverStatus::OPTIMAL);
443 }
444
445 // Logging.
446 ++num_solutions_;
447 if (log_updates_) {
448 std::string solution_info = response.solution_info();
449 if (model != nullptr) {
450 const int64 num_bool = model->Get<Trail>()->NumVariables();
451 const int64 num_fixed = model->Get<SatSolver>()->NumFixedVariables();
452 absl::StrAppend(&solution_info, " fixed_bools:", num_fixed, "/",
453 num_bool);
454 }
455
456 if (model_proto_.has_objective()) {
457 const CpObjectiveProto& obj = model_proto_.objective();
458 const double best =
459 ScaleObjectiveValue(obj, best_solution_objective_value_);
460 double lb = ScaleObjectiveValue(obj, inner_objective_lower_bound_);
461 double ub = ScaleObjectiveValue(obj, inner_objective_upper_bound_);
462 if (model_proto_.objective().scaling_factor() < 0) {
463 std::swap(lb, ub);
464 }
465 RegisterSolutionFound(solution_info);
466 LogProgress(absl::StrCat(num_solutions_), wall_timer_.Get(), best, lb, ub,
467 solution_info);
468 } else {
469 LogSatProgress(absl::StrCat(num_solutions_), wall_timer_.Get(),
470 solution_info);
471 }
472 }
473
474 // Call callbacks.
475 // Note that we cannot call function that try to get the mutex_ here.
476 TestGapLimitsIfNeeded();
477 if (!callbacks_.empty()) {
478 FillObjectiveValuesInBestResponse();
479 SetStatsFromModelInternal(model);
480 for (const auto& pair : callbacks_) {
481 pair.second(best_response_);
482 }
483 }
484
485#if !defined(__PORTABLE_PLATFORM__)
486 // We protect solution dumping with log_updates as LNS subsolvers share
487 // another solution manager, and we do not want to dump those.
488 if (absl::GetFlag(FLAGS_cp_model_dump_solutions) && log_updates_) {
489 const std::string file =
490 absl::StrCat(dump_prefix_, "solution_", num_solutions_, ".pbtxt");
491 LOG(INFO) << "Dumping solution to '" << file << "'.";
492 CHECK_OK(file::SetTextProto(file, best_response_, file::Defaults()));
493 }
494#endif // __PORTABLE_PLATFORM__
495}
496
498#if !defined(__PORTABLE_PLATFORM__)
499 if (absl::GetFlag(FLAGS_cp_model_load_debug_solution).empty()) return;
500 if (model->Get<DebugSolution>() != nullptr) return; // Already loaded.
501
502 CpSolverResponse response;
503 LOG(INFO) << "Reading solution from '"
504 << absl::GetFlag(FLAGS_cp_model_load_debug_solution) << "'.";
505 CHECK_OK(file::GetTextProto(absl::GetFlag(FLAGS_cp_model_load_debug_solution),
507
508 const auto& mapping = *model->GetOrCreate<CpModelMapping>();
509 auto& debug_solution = *model->GetOrCreate<DebugSolution>();
510 debug_solution.resize(
511 model->GetOrCreate<IntegerTrail>()->NumIntegerVariables().value());
512 for (int i = 0; i < response.solution().size(); ++i) {
513 if (!mapping.IsInteger(i)) continue;
514 const IntegerVariable var = mapping.Integer(i);
515 debug_solution[var] = response.solution(i);
516 debug_solution[NegationOf(var)] = -response.solution(i);
517 }
518
519 // The objective variable is usually not part of the proto, but it is still
520 // nice to have it, so we recompute it here.
521 auto* objective_def = model->Get<ObjectiveDefinition>();
522 if (objective_def == nullptr) return;
523
524 const IntegerVariable objective_var = objective_def->objective_var;
525 const int64 objective_value =
526 ComputeInnerObjective(model_proto_.objective(), response);
527 debug_solution[objective_var] = objective_value;
528 debug_solution[NegationOf(objective_var)] = -objective_value;
529#endif // __PORTABLE_PLATFORM__
530}
531
533 absl::MutexLock mutex_lock(&mutex_);
534 SetStatsFromModelInternal(model);
535}
536
537void SharedResponseManager::SetStatsFromModelInternal(Model* model) {
538 if (model == nullptr) return;
539 auto* sat_solver = model->GetOrCreate<SatSolver>();
540 auto* integer_trail = model->Get<IntegerTrail>();
541 best_response_.set_num_booleans(sat_solver->NumVariables());
542 best_response_.set_num_branches(sat_solver->num_branches());
543 best_response_.set_num_conflicts(sat_solver->num_failures());
544 best_response_.set_num_binary_propagations(sat_solver->num_propagations());
545 best_response_.set_num_restarts(sat_solver->num_restarts());
546 best_response_.set_num_integer_propagations(
547 integer_trail == nullptr ? 0 : integer_trail->num_enqueues());
548 auto* time_limit = model->Get<TimeLimit>();
549 best_response_.set_wall_time(time_limit->GetElapsedTime());
550 best_response_.set_deterministic_time(
551 time_limit->GetElapsedDeterministicTime());
552
553 int64 num_lp_iters = 0;
554 for (const LinearProgrammingConstraint* lp :
556 num_lp_iters += lp->total_num_simplex_iterations();
557 }
558 best_response_.set_num_lp_iterations(num_lp_iters);
559}
560
562 absl::MutexLock mutex_lock(&mutex_);
563 return best_response_.status() == CpSolverStatus::OPTIMAL ||
564 best_response_.status() == CpSolverStatus::INFEASIBLE;
565}
566
567std::string ExtractWorkerName(const std::string& improvement_info) {
568 if (improvement_info.empty()) return "";
569
570 std::string worker_name = improvement_info;
571
572 // Remove ' [hint]' suffix.
573 const auto& hint_suffix = worker_name.find(" [");
574 if (hint_suffix != std::string::npos) {
575 worker_name.erase(hint_suffix);
576 }
577
578 // Remove lns info suffix.
579 const auto& lns_suffix = worker_name.find('(');
580 if (lns_suffix != std::string::npos) {
581 worker_name.erase(lns_suffix);
582 }
583
584 // Remove fixed_bools suffix.
585 const auto fixed_suffix = worker_name.find(" fixed_bools:");
586 if (fixed_suffix != std::string::npos) {
587 worker_name.erase(fixed_suffix);
588 }
589
590 return worker_name;
591}
592
593void SharedResponseManager::RegisterSolutionFound(
594 const std::string& improvement_info) {
595 if (improvement_info.empty()) return;
596 primal_improvements_count_[ExtractWorkerName(improvement_info)]++;
597}
598
599void SharedResponseManager::RegisterObjectiveBoundImprovement(
600 const std::string& improvement_info) {
601 if (improvement_info.empty() || improvement_info == "initial domain") return;
602 dual_improvements_count_[ExtractWorkerName(improvement_info)]++;
603}
604
606 absl::MutexLock mutex_lock(&mutex_);
607 if (!primal_improvements_count_.empty()) {
608 LOG(INFO) << "Solutions found per subsolver:";
609 for (const auto& entry : primal_improvements_count_) {
610 LOG(INFO) << " '" << entry.first << "': " << entry.second;
611 }
612 }
613 if (!dual_improvements_count_.empty()) {
614 LOG(INFO) << "Objective bounds found per subsolver:";
615 for (const auto& entry : dual_improvements_count_) {
616 LOG(INFO) << " '" << entry.first << "': " << entry.second;
617 }
618 }
619}
620
622 : num_variables_(model_proto.variables_size()),
623 model_proto_(model_proto),
624 lower_bounds_(num_variables_, kint64min),
625 upper_bounds_(num_variables_, kint64max),
626 synchronized_lower_bounds_(num_variables_, kint64min),
627 synchronized_upper_bounds_(num_variables_, kint64max) {
628 changed_variables_since_last_synchronize_.ClearAndResize(num_variables_);
629 for (int i = 0; i < num_variables_; ++i) {
630 lower_bounds_[i] = model_proto.variables(i).domain(0);
631 const int domain_size = model_proto.variables(i).domain_size();
632 upper_bounds_[i] = model_proto.variables(i).domain(domain_size - 1);
633 synchronized_lower_bounds_[i] = lower_bounds_[i];
634 synchronized_upper_bounds_[i] = upper_bounds_[i];
635 }
636}
637
639 const CpModelProto& model_proto, const std::string& worker_name,
640 const std::vector<int>& variables,
641 const std::vector<int64>& new_lower_bounds,
642 const std::vector<int64>& new_upper_bounds) {
643 CHECK_EQ(variables.size(), new_lower_bounds.size());
644 CHECK_EQ(variables.size(), new_upper_bounds.size());
645 int num_improvements = 0;
646
647 absl::MutexLock mutex_lock(&mutex_);
648 for (int i = 0; i < variables.size(); ++i) {
649 const int var = variables[i];
650 if (var >= num_variables_) continue;
651 const int64 old_lb = lower_bounds_[var];
652 const int64 old_ub = upper_bounds_[var];
653 const int64 new_lb = new_lower_bounds[i];
654 const int64 new_ub = new_upper_bounds[i];
655 const bool changed_lb = new_lb > old_lb;
656 const bool changed_ub = new_ub < old_ub;
657 CHECK_GE(var, 0);
658 if (!changed_lb && !changed_ub) continue;
659
660 if (changed_lb) {
661 lower_bounds_[var] = new_lb;
662 }
663 if (changed_ub) {
664 upper_bounds_[var] = new_ub;
665 }
666 changed_variables_since_last_synchronize_.Set(var);
667 num_improvements++;
668 }
669 // TODO(user): Display number of bound improvements cumulatively per
670 // workers at the end of the search.
671 if (num_improvements > 0) {
672 VLOG(2) << worker_name << " exports " << num_improvements
673 << " modifications";
674 }
675}
676
678 absl::MutexLock mutex_lock(&mutex_);
679 for (const int var :
680 changed_variables_since_last_synchronize_.PositionsSetAtLeastOnce()) {
681 synchronized_lower_bounds_[var] = lower_bounds_[var];
682 synchronized_upper_bounds_[var] = upper_bounds_[var];
683 for (int j = 0; j < id_to_changed_variables_.size(); ++j) {
684 id_to_changed_variables_[j].Set(var);
685 }
686 }
687 changed_variables_since_last_synchronize_.ClearAll();
688}
689
691 absl::MutexLock mutex_lock(&mutex_);
692 const int id = id_to_changed_variables_.size();
693 id_to_changed_variables_.resize(id + 1);
694 id_to_changed_variables_[id].ClearAndResize(num_variables_);
695 for (int var = 0; var < num_variables_; ++var) {
696 const int64 lb = model_proto_.variables(var).domain(0);
697 const int domain_size = model_proto_.variables(var).domain_size();
698 const int64 ub = model_proto_.variables(var).domain(domain_size - 1);
699 if (lb != synchronized_lower_bounds_[var] ||
700 ub != synchronized_upper_bounds_[var]) {
701 id_to_changed_variables_[id].Set(var);
702 }
703 }
704 return id;
705}
706
708 int id, std::vector<int>* variables, std::vector<int64>* new_lower_bounds,
709 std::vector<int64>* new_upper_bounds) {
710 variables->clear();
711 new_lower_bounds->clear();
712 new_upper_bounds->clear();
713
714 absl::MutexLock mutex_lock(&mutex_);
715 for (const int var : id_to_changed_variables_[id].PositionsSetAtLeastOnce()) {
716 variables->push_back(var);
717 new_lower_bounds->push_back(synchronized_lower_bounds_[var]);
718 new_upper_bounds->push_back(synchronized_upper_bounds_[var]);
719 }
720 id_to_changed_variables_[id].ClearAll();
721}
722
723} // namespace sat
724} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define LOG_IF(severity, condition)
Definition: base/logging.h:479
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_OK(x)
Definition: base/logging.h:40
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define LOG(severity)
Definition: base/logging.h:420
#define VLOG(verboselevel)
Definition: base/logging.h:978
double Get() const
Definition: timer.h:45
double GetElapsedDeterministicTime() const
Definition: time_limit.h:383
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
IntegerVariable NumIntegerVariables() const
Definition: integer.h:565
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
SharedBoundsManager(const CpModelProto &model_proto)
void GetChangedBounds(int id, std::vector< int > *variables, std::vector< int64 > *new_lower_bounds, std::vector< int64 > *new_upper_bounds)
void ReportPotentialNewBounds(const CpModelProto &model_proto, const std::string &worker_name, const std::vector< int > &variables, const std::vector< int64 > &new_lower_bounds, const std::vector< int64 > &new_upper_bounds)
void AddNewSolution(const std::vector< double > &lp_solution)
void NewLPSolution(std::vector< double > lp_solution)
void NewRelaxationSolution(const CpSolverResponse &response)
SharedResponseManager(bool log_updates, bool enumerate_all_solutions, const CpModelProto *proto, const WallTimer *wall_timer, SharedTimeLimit *shared_time_limit)
void NewSolution(const CpSolverResponse &response, Model *model)
void NotifyThatImprovingProblemIsInfeasible(const std::string &worker_info)
void AddUnsatCore(const std::vector< int > &core)
void SetGapLimitsFromParameters(const SatParameters &parameters)
int AddSolutionCallback(std::function< void(const CpSolverResponse &)> callback)
void UpdateInnerObjectiveBounds(const std::string &update_info, IntegerValue lb, IntegerValue ub)
void AddInternal(const Solution &solution) ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_)
SatParameters parameters
CpModelProto proto
CpModelProto const * model_proto
SharedResponseManager * response
SharedTimeLimit * time_limit
WallTimer * wall_timer
IntVar * var
Definition: expr_array.cc:1858
GRBmodel * model
MPCallback * callback
static const int64 kint64max
int64_t int64
static const int64 kint64min
const int INFO
Definition: log_severity.h:31
Definition: file.cc:141
absl::Status GetTextProto(const absl::string_view &filename, google::protobuf::Message *proto, int flags)
Definition: file.cc:275
absl::Status SetTextProto(const absl::string_view &filename, const google::protobuf::Message &proto, int flags)
Definition: file.cc:285
int Defaults()
Definition: base/file.h:119
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
int64 ComputeInnerObjective(const CpObjectiveProto &objective, const CpSolverResponse &response)
double ScaleObjectiveValue(const CpObjectiveProto &proto, int64 value)
std::vector< IntegerVariable > NegationOf(const std::vector< IntegerVariable > &vars)
Definition: integer.cc:27
std::string ExtractWorkerName(const std::string &improvement_info)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
ABSL_FLAG(bool, cp_model_dump_solutions, false, "DEBUG ONLY. If true, all the intermediate solution will be dumped " "under '\"FLAGS_cp_model_dump_prefix\" + \"solution_xxx.pb.txt\"'.")