16 #if !defined(__PORTABLE_PLATFORM__)
19 #endif // __PORTABLE_PLATFORM__
21 #include "absl/container/flat_hash_set.h"
22 #include "absl/random/random.h"
34 "DEBUG ONLY. If true, all the intermediate solution will be dumped "
35 "under '\"FLAGS_cp_model_dump_prefix\" + \"solution_xxx.pb.txt\"'.");
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.");
50 if (
response.solution().empty())
return;
54 solution.variable_values.assign(
response.solution().begin(),
61 solution.rank = -
response.best_objective_bound();
67 std::vector<double> lp_solution) {
68 if (lp_solution.empty())
return;
72 solution.variable_values = std::move(lp_solution);
75 absl::MutexLock mutex_lock(&
mutex_);
76 solution.rank = -num_synchronization_;
81 absl::MutexLock mutex_lock(&mutex_);
82 return !solutions_.empty();
86 absl::MutexLock mutex_lock(&mutex_);
87 std::vector<double> solution;
88 if (solutions_.empty())
return solution;
90 solution = std::move(solutions_.back());
91 solutions_.pop_back();
96 const std::vector<double>& lp_solution) {
97 absl::MutexLock mutex_lock(&mutex_);
98 solutions_.push_back(lp_solution);
103 bool enumerate_all_solutions,
104 const CpModelProto*
proto,
107 : log_updates_(log_updates),
108 enumerate_all_solutions_(enumerate_all_solutions),
109 model_proto_(*
proto),
111 shared_time_limit_(shared_time_limit),
116 void LogNewSolution(
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);
126 void LogNewSatSolution(
const std::string& event_or_solution_count,
127 double time_in_seconds,
128 const std::string& solution_info) {
129 LOG(
INFO) << absl::StrFormat(
"#%-5s %6.2fs %s", event_or_solution_count,
130 time_in_seconds, solution_info);
136 absl::MutexLock mutex_lock(&mutex_);
137 if (!model_proto_.has_objective())
return;
140 const double time_delta = current_time - last_primal_integral_time_stamp_;
141 last_primal_integral_time_stamp_ = current_time;
148 const CpObjectiveProto& obj = model_proto_.objective();
149 const double factor =
150 obj.scaling_factor() != 0.0 ? std::abs(obj.scaling_factor()) : 1.0;
151 const double bounds_delta = std::log(
152 1 + factor * std::abs(
static_cast<double>(inner_objective_upper_bound_) -
153 static_cast<double>(inner_objective_lower_bound_)));
154 primal_integral_ += time_delta * bounds_delta;
159 absl::MutexLock mutex_lock(&mutex_);
160 if (!model_proto_.has_objective())
return;
161 absolute_gap_limit_ =
parameters.absolute_gap_limit();
162 relative_gap_limit_ =
parameters.relative_gap_limit();
165 void SharedResponseManager::TestGapLimitsIfNeeded() {
166 if (absolute_gap_limit_ == 0 && relative_gap_limit_ == 0)
return;
170 const CpObjectiveProto& obj = model_proto_.objective();
171 const double user_best =
173 const double user_bound =
175 const double gap = std::abs(user_best - user_bound);
176 if (gap <= absolute_gap_limit_) {
178 <<
"Absolute gap limit of " << absolute_gap_limit_ <<
" reached.";
184 shared_time_limit_->
Stop();
186 if (gap /
std::max(1.0, std::abs(user_best)) < relative_gap_limit_) {
188 <<
"Relative gap limit of " << relative_gap_limit_ <<
" reached.";
192 shared_time_limit_->
Stop();
197 const std::string& worker_info, IntegerValue lb, IntegerValue ub) {
198 absl::MutexLock mutex_lock(&mutex_);
199 CHECK(model_proto_.has_objective());
206 if (inner_objective_lower_bound_ > inner_objective_upper_bound_) {
211 (lb > inner_objective_lower_bound_ || ub < inner_objective_upper_bound_);
212 if (lb > inner_objective_lower_bound_) {
217 DCHECK_LE(inner_objective_upper_bound_, best_solution_objective_value_);
218 inner_objective_lower_bound_ =
219 std::min(best_solution_objective_value_, lb.value());
221 if (ub < inner_objective_upper_bound_) {
222 inner_objective_upper_bound_ = ub.value();
224 if (inner_objective_lower_bound_ > inner_objective_upper_bound_) {
231 if (log_updates_) LogNewSatSolution(
"Done", wall_timer_.
Get(), worker_info);
234 if (log_updates_ && change) {
235 const CpObjectiveProto& obj = model_proto_.objective();
240 if (model_proto_.objective().scaling_factor() < 0) {
241 std::swap(new_lb, new_ub);
243 LogNewSolution(
"Bound", wall_timer_.
Get(), best, new_lb, new_ub,
246 if (change) TestGapLimitsIfNeeded();
253 const std::string& worker_info) {
254 absl::MutexLock mutex_lock(&mutex_);
260 if (!model_proto_.has_objective()) {
261 best_response_.set_all_solutions_were_found(
true);
266 inner_objective_lower_bound_ = best_solution_objective_value_;
271 if (log_updates_) LogNewSatSolution(
"Done", wall_timer_.
Get(), worker_info);
275 absl::MutexLock mutex_lock(&mutex_);
276 best_response_.clear_sufficient_assumptions_for_infeasibility();
277 for (
const int ref : core) {
278 best_response_.add_sufficient_assumptions_for_infeasibility(ref);
283 absl::MutexLock mutex_lock(&mutex_);
284 return IntegerValue(inner_objective_lower_bound_);
288 absl::MutexLock mutex_lock(&mutex_);
289 return IntegerValue(inner_objective_upper_bound_);
293 absl::MutexLock mutex_lock(&mutex_);
294 synchronized_inner_objective_lower_bound_ =
295 IntegerValue(inner_objective_lower_bound_);
296 synchronized_inner_objective_upper_bound_ =
297 IntegerValue(inner_objective_upper_bound_);
301 absl::MutexLock mutex_lock(&mutex_);
302 return synchronized_inner_objective_lower_bound_;
306 absl::MutexLock mutex_lock(&mutex_);
307 return synchronized_inner_objective_upper_bound_;
311 absl::MutexLock mutex_lock(&mutex_);
312 return IntegerValue(best_solution_objective_value_);
316 absl::MutexLock mutex_lock(&mutex_);
317 return primal_integral_;
321 std::function<
void(
const CpSolverResponse&)>
callback) {
322 absl::MutexLock mutex_lock(&mutex_);
323 const int id = next_callback_id_++;
324 callbacks_.emplace_back(
id, std::move(
callback));
329 absl::MutexLock mutex_lock(&mutex_);
330 for (
int i = 0; i < callbacks_.size(); ++i) {
331 if (callbacks_[i].first == callback_id) {
332 callbacks_.erase(callbacks_.begin() + i);
336 LOG(DFATAL) <<
"Callback id " << callback_id <<
" not registered.";
340 absl::MutexLock mutex_lock(&mutex_);
341 FillObjectiveValuesInBestResponse();
342 return best_response_;
345 void SharedResponseManager::FillObjectiveValuesInBestResponse() {
346 if (!model_proto_.has_objective())
return;
347 const CpObjectiveProto& obj = model_proto_.objective();
350 best_response_.clear_objective_value();
351 best_response_.clear_best_objective_bound();
358 best_response_.set_objective_value(
361 best_response_.set_objective_value(
366 best_response_.set_best_objective_bound(
370 best_response_.set_primal_integral(primal_integral_);
375 absl::MutexLock mutex_lock(&mutex_);
377 if (model_proto_.has_objective()) {
378 const int64 objective_value =
384 solution.variable_values.assign(
response.solution().begin(),
386 solution.rank = objective_value;
387 solutions_.
Add(solution);
391 if (objective_value > inner_objective_upper_bound_)
return;
397 DCHECK_GE(objective_value, inner_objective_lower_bound_);
399 DCHECK_LT(objective_value, best_solution_objective_value_);
400 best_solution_objective_value_ = objective_value;
403 inner_objective_upper_bound_ = objective_value - 1;
408 if (!model_proto_.has_objective() && !enumerate_all_solutions_) {
414 best_response_.set_solution_info(
response.solution_info());
415 *best_response_.mutable_solution() =
response.solution();
416 *best_response_.mutable_solution_lower_bounds() =
418 *best_response_.mutable_solution_upper_bounds() =
422 if (model_proto_.has_objective() &&
423 inner_objective_lower_bound_ > inner_objective_upper_bound_) {
430 std::string solution_info =
response.solution_info();
431 if (
model !=
nullptr) {
434 absl::StrAppend(&solution_info,
" fixed_bools:", num_fixed,
"/",
438 if (model_proto_.has_objective()) {
439 const CpObjectiveProto& obj = model_proto_.objective();
444 if (model_proto_.objective().scaling_factor() < 0) {
447 LogNewSolution(absl::StrCat(num_solutions_), wall_timer_.
Get(), best, lb,
450 LogNewSatSolution(absl::StrCat(num_solutions_), wall_timer_.
Get(),
457 TestGapLimitsIfNeeded();
458 if (!callbacks_.empty()) {
459 FillObjectiveValuesInBestResponse();
460 SetStatsFromModelInternal(
model);
461 for (
const auto& pair : callbacks_) {
462 pair.second(best_response_);
466 #if !defined(__PORTABLE_PLATFORM__)
469 if (absl::GetFlag(FLAGS_cp_model_dump_solutions) && log_updates_) {
470 const std::string
file =
471 absl::StrCat(dump_prefix_,
"solution_", num_solutions_,
".pbtxt");
472 LOG(
INFO) <<
"Dumping solution to '" <<
file <<
"'.";
475 #endif // __PORTABLE_PLATFORM__
479 #if !defined(__PORTABLE_PLATFORM__)
480 if (absl::GetFlag(FLAGS_cp_model_load_debug_solution).empty())
return;
484 LOG(
INFO) <<
"Reading solution from '"
485 << absl::GetFlag(FLAGS_cp_model_load_debug_solution) <<
"'.";
491 debug_solution.resize(
493 for (
int i = 0; i <
response.solution().size(); ++i) {
494 if (!mapping.IsInteger(i))
continue;
495 const IntegerVariable
var = mapping.Integer(i);
503 if (objective_def ==
nullptr)
return;
505 const IntegerVariable objective_var = objective_def->
objective_var;
506 const int64 objective_value =
508 debug_solution[objective_var] = objective_value;
509 debug_solution[
NegationOf(objective_var)] = -objective_value;
510 #endif // __PORTABLE_PLATFORM__
514 absl::MutexLock mutex_lock(&mutex_);
515 SetStatsFromModelInternal(
model);
518 void SharedResponseManager::SetStatsFromModelInternal(
Model*
model) {
519 if (
model ==
nullptr)
return;
522 best_response_.set_num_booleans(sat_solver->NumVariables());
523 best_response_.set_num_branches(sat_solver->num_branches());
524 best_response_.set_num_conflicts(sat_solver->num_failures());
525 best_response_.set_num_binary_propagations(sat_solver->num_propagations());
526 best_response_.set_num_restarts(sat_solver->num_restarts());
527 best_response_.set_num_integer_propagations(
528 integer_trail ==
nullptr ? 0 : integer_trail->num_enqueues());
530 best_response_.set_wall_time(
time_limit->GetElapsedTime());
531 best_response_.set_deterministic_time(
534 int64 num_lp_iters = 0;
537 num_lp_iters += lp->total_num_simplex_iterations();
539 best_response_.set_num_lp_iterations(num_lp_iters);
543 absl::MutexLock mutex_lock(&mutex_);
551 lower_bounds_(num_variables_,
kint64min),
552 upper_bounds_(num_variables_,
kint64max),
553 synchronized_lower_bounds_(num_variables_,
kint64min),
554 synchronized_upper_bounds_(num_variables_,
kint64max) {
555 changed_variables_since_last_synchronize_.ClearAndResize(num_variables_);
556 for (
int i = 0; i < num_variables_; ++i) {
557 lower_bounds_[i] =
model_proto.variables(i).domain(0);
558 const int domain_size =
model_proto.variables(i).domain_size();
559 upper_bounds_[i] =
model_proto.variables(i).domain(domain_size - 1);
560 synchronized_lower_bounds_[i] = lower_bounds_[i];
561 synchronized_upper_bounds_[i] = upper_bounds_[i];
566 const CpModelProto&
model_proto,
const std::string& worker_name,
567 const std::vector<int>& variables,
568 const std::vector<int64>& new_lower_bounds,
569 const std::vector<int64>& new_upper_bounds) {
570 CHECK_EQ(variables.size(), new_lower_bounds.size());
571 CHECK_EQ(variables.size(), new_upper_bounds.size());
572 int num_improvements = 0;
574 absl::MutexLock mutex_lock(&mutex_);
575 for (
int i = 0; i < variables.size(); ++i) {
576 const int var = variables[i];
577 if (
var >= num_variables_)
continue;
578 const int64 old_lb = lower_bounds_[
var];
579 const int64 old_ub = upper_bounds_[
var];
580 const int64 new_lb = new_lower_bounds[i];
581 const int64 new_ub = new_upper_bounds[i];
582 const bool changed_lb = new_lb > old_lb;
583 const bool changed_ub = new_ub < old_ub;
585 if (!changed_lb && !changed_ub)
continue;
588 lower_bounds_[
var] = new_lb;
591 upper_bounds_[
var] = new_ub;
593 changed_variables_since_last_synchronize_.Set(
var);
598 if (num_improvements > 0) {
599 VLOG(2) << worker_name <<
" exports " << num_improvements
605 absl::MutexLock mutex_lock(&mutex_);
607 changed_variables_since_last_synchronize_.PositionsSetAtLeastOnce()) {
608 synchronized_lower_bounds_[
var] = lower_bounds_[
var];
609 synchronized_upper_bounds_[
var] = upper_bounds_[
var];
610 for (
int j = 0; j < id_to_changed_variables_.size(); ++j) {
611 id_to_changed_variables_[j].Set(
var);
614 changed_variables_since_last_synchronize_.ClearAll();
618 absl::MutexLock mutex_lock(&mutex_);
619 const int id = id_to_changed_variables_.size();
620 id_to_changed_variables_.resize(
id + 1);
621 id_to_changed_variables_[id].ClearAndResize(num_variables_);
622 for (
int var = 0;
var < num_variables_; ++
var) {
623 const int64 lb = model_proto_.variables(
var).domain(0);
624 const int domain_size = model_proto_.variables(
var).domain_size();
625 const int64 ub = model_proto_.variables(
var).domain(domain_size - 1);
626 if (lb != synchronized_lower_bounds_[
var] ||
627 ub != synchronized_upper_bounds_[
var]) {
628 id_to_changed_variables_[id].Set(
var);
635 int id, std::vector<int>* variables, std::vector<int64>* new_lower_bounds,
636 std::vector<int64>* new_upper_bounds) {
638 new_lower_bounds->clear();
639 new_upper_bounds->clear();
641 absl::MutexLock mutex_lock(&mutex_);
642 for (
const int var : id_to_changed_variables_[
id].PositionsSetAtLeastOnce()) {
643 variables->push_back(
var);
644 new_lower_bounds->push_back(synchronized_lower_bounds_[
var]);
645 new_upper_bounds->push_back(synchronized_upper_bounds_[
var]);
647 id_to_changed_variables_[id].ClearAll();