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"
24 #include "ortools/base/stl_util.h"
25 #include "ortools/sat/cp_model.pb.h"
27 #include "ortools/sat/integer.h"
29 #include "ortools/sat/model.h"
30 #include "ortools/sat/sat_base.h"
32 
33 ABSL_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 
43 namespace operations_research {
44 namespace 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 
114 namespace {
115 
116 void 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 
126 void 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 
144 void 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 
176 void 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 
292 void 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 
363 void 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 
391 void 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),
506  &response, file::Defaults()));
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 
537 void 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 :
555  *model->GetOrCreate<LinearProgrammingConstraintCollection>()) {
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 
567 std::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 
593 void SharedResponseManager::RegisterSolutionFound(
594  const std::string& improvement_info) {
595  if (improvement_info.empty()) return;
596  primal_improvements_count_[ExtractWorkerName(improvement_info)]++;
597 }
598 
599 void 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
int Defaults()
Definition: base/file.h:119
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
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
int64 ComputeInnerObjective(const CpObjectiveProto &objective, const CpSolverResponse &response)
double ScaleObjectiveValue(const CpObjectiveProto &proto, int64 value)
std::string ExtractWorkerName(const std::string &improvement_info)
std::vector< IntegerVariable > NegationOf(const std::vector< IntegerVariable > &vars)
Definition: integer.cc:27
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\"'.")