16#if !defined(__PORTABLE_PLATFORM__)
21#include "absl/container/flat_hash_set.h"
22#include "absl/random/random.h"
25#include "ortools/sat/cp_model.pb.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),
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);
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);
135 absl::MutexLock mutex_lock(&mutex_);
136 update_integral_on_each_change_ = set;
140 absl::MutexLock mutex_lock(&mutex_);
141 UpdatePrimalIntegralInternal();
144void SharedResponseManager::UpdatePrimalIntegralInternal() {
145 if (!model_proto_.has_objective())
return;
148 const double time_delta = current_time - last_primal_integral_time_stamp_;
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;
162 last_primal_integral_time_stamp_ = current_time;
164 std::max(0.0,
static_cast<double>(inner_objective_upper_bound_) -
165 static_cast<double>(inner_objective_lower_bound_));
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();
176void SharedResponseManager::TestGapLimitsIfNeeded() {
180 if (update_integral_on_each_change_) UpdatePrimalIntegralInternal();
182 if (absolute_gap_limit_ == 0 && relative_gap_limit_ == 0)
return;
186 const CpObjectiveProto& obj = model_proto_.objective();
187 const double user_best =
189 const double user_bound =
191 const double gap = std::abs(user_best - user_bound);
192 if (gap <= absolute_gap_limit_) {
194 <<
"Absolute gap limit of " << absolute_gap_limit_ <<
" reached.";
195 best_response_.set_status(CpSolverStatus::OPTIMAL);
200 shared_time_limit_->
Stop();
202 if (gap /
std::max(1.0, std::abs(user_best)) < relative_gap_limit_) {
204 <<
"Relative gap limit of " << relative_gap_limit_ <<
" reached.";
205 best_response_.set_status(CpSolverStatus::OPTIMAL);
208 shared_time_limit_->
Stop();
213 const std::string& update_info, IntegerValue lb, IntegerValue ub) {
214 absl::MutexLock mutex_lock(&mutex_);
215 CHECK(model_proto_.has_objective());
222 if (inner_objective_lower_bound_ > inner_objective_upper_bound_) {
227 (lb > inner_objective_lower_bound_ || ub < inner_objective_upper_bound_);
228 if (lb > inner_objective_lower_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());
237 if (ub < inner_objective_upper_bound_) {
238 inner_objective_upper_bound_ = ub.value();
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);
245 best_response_.set_status(CpSolverStatus::INFEASIBLE);
247 if (update_integral_on_each_change_) UpdatePrimalIntegralInternal();
248 if (log_updates_) LogSatProgress(
"Done", wall_timer_.
Get(), update_info);
251 if (log_updates_ && change) {
252 const CpObjectiveProto& obj = model_proto_.objective();
257 if (model_proto_.objective().scaling_factor() < 0) {
258 std::swap(new_lb, new_ub);
260 RegisterObjectiveBoundImprovement(update_info);
261 LogProgress(
"Bound", wall_timer_.
Get(), best, new_lb, new_ub, update_info);
263 if (change) TestGapLimitsIfNeeded();
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) {
276 best_response_.set_status(CpSolverStatus::OPTIMAL);
277 if (!model_proto_.has_objective()) {
278 best_response_.set_all_solutions_were_found(
true);
283 inner_objective_lower_bound_ = best_solution_objective_value_;
284 if (update_integral_on_each_change_) UpdatePrimalIntegralInternal();
287 best_response_.set_status(CpSolverStatus::INFEASIBLE);
289 if (log_updates_) LogSatProgress(
"Done", wall_timer_.
Get(), worker_info);
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);
301 absl::MutexLock mutex_lock(&mutex_);
302 return IntegerValue(inner_objective_lower_bound_);
306 absl::MutexLock mutex_lock(&mutex_);
307 return IntegerValue(inner_objective_upper_bound_);
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_);
319 absl::MutexLock mutex_lock(&mutex_);
320 return synchronized_inner_objective_lower_bound_;
324 absl::MutexLock mutex_lock(&mutex_);
325 return synchronized_inner_objective_upper_bound_;
329 absl::MutexLock mutex_lock(&mutex_);
330 return IntegerValue(best_solution_objective_value_);
334 absl::MutexLock mutex_lock(&mutex_);
335 return primal_integral_;
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));
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);
354 LOG(DFATAL) <<
"Callback id " << callback_id <<
" not registered.";
358 absl::MutexLock mutex_lock(&mutex_);
359 FillObjectiveValuesInBestResponse();
360 return best_response_;
363void SharedResponseManager::FillObjectiveValuesInBestResponse() {
364 if (!model_proto_.has_objective())
return;
365 const CpObjectiveProto& obj = model_proto_.objective();
367 if (best_response_.status() == CpSolverStatus::INFEASIBLE) {
368 best_response_.clear_objective_value();
369 best_response_.clear_best_objective_bound();
375 if (best_response_.status() == CpSolverStatus::UNKNOWN) {
376 best_response_.set_objective_value(
379 best_response_.set_objective_value(
384 best_response_.set_best_objective_bound(
388 best_response_.set_primal_integral(primal_integral_);
393 absl::MutexLock mutex_lock(&mutex_);
395 if (model_proto_.has_objective()) {
396 const int64 objective_value =
402 solution.variable_values.assign(
response.solution().begin(),
404 solution.rank = objective_value;
405 solutions_.
Add(solution);
409 if (objective_value > inner_objective_upper_bound_)
return;
415 DCHECK_GE(objective_value, inner_objective_lower_bound_);
417 DCHECK_LT(objective_value, best_solution_objective_value_);
418 best_solution_objective_value_ = objective_value;
421 inner_objective_upper_bound_ = objective_value - 1;
426 if (!model_proto_.has_objective() && !enumerate_all_solutions_) {
427 best_response_.set_status(CpSolverStatus::OPTIMAL);
429 best_response_.set_status(CpSolverStatus::FEASIBLE);
432 best_response_.set_solution_info(
response.solution_info());
433 *best_response_.mutable_solution() =
response.solution();
434 *best_response_.mutable_solution_lower_bounds() =
436 *best_response_.mutable_solution_upper_bounds() =
440 if (model_proto_.has_objective() &&
441 inner_objective_lower_bound_ > inner_objective_upper_bound_) {
442 best_response_.set_status(CpSolverStatus::OPTIMAL);
448 std::string solution_info =
response.solution_info();
449 if (
model !=
nullptr) {
452 absl::StrAppend(&solution_info,
" fixed_bools:", num_fixed,
"/",
456 if (model_proto_.has_objective()) {
457 const CpObjectiveProto& obj = model_proto_.objective();
462 if (model_proto_.objective().scaling_factor() < 0) {
465 RegisterSolutionFound(solution_info);
466 LogProgress(absl::StrCat(num_solutions_), wall_timer_.
Get(), best, lb, ub,
469 LogSatProgress(absl::StrCat(num_solutions_), wall_timer_.
Get(),
476 TestGapLimitsIfNeeded();
477 if (!callbacks_.empty()) {
478 FillObjectiveValuesInBestResponse();
479 SetStatsFromModelInternal(
model);
480 for (
const auto& pair : callbacks_) {
481 pair.second(best_response_);
485#if !defined(__PORTABLE_PLATFORM__)
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 <<
"'.";
498#if !defined(__PORTABLE_PLATFORM__)
499 if (absl::GetFlag(FLAGS_cp_model_load_debug_solution).empty())
return;
503 LOG(
INFO) <<
"Reading solution from '"
504 << absl::GetFlag(FLAGS_cp_model_load_debug_solution) <<
"'.";
510 debug_solution.resize(
512 for (
int i = 0; i <
response.solution().size(); ++i) {
513 if (!mapping.IsInteger(i))
continue;
514 const IntegerVariable
var = mapping.Integer(i);
522 if (objective_def ==
nullptr)
return;
524 const IntegerVariable objective_var = objective_def->
objective_var;
525 const int64 objective_value =
527 debug_solution[objective_var] = objective_value;
528 debug_solution[
NegationOf(objective_var)] = -objective_value;
533 absl::MutexLock mutex_lock(&mutex_);
534 SetStatsFromModelInternal(
model);
537void SharedResponseManager::SetStatsFromModelInternal(
Model*
model) {
538 if (
model ==
nullptr)
return;
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());
549 best_response_.set_wall_time(
time_limit->GetElapsedTime());
550 best_response_.set_deterministic_time(
553 int64 num_lp_iters = 0;
556 num_lp_iters += lp->total_num_simplex_iterations();
558 best_response_.set_num_lp_iterations(num_lp_iters);
562 absl::MutexLock mutex_lock(&mutex_);
563 return best_response_.status() == CpSolverStatus::OPTIMAL ||
564 best_response_.status() == CpSolverStatus::INFEASIBLE;
568 if (improvement_info.empty())
return "";
570 std::string worker_name = improvement_info;
573 const auto& hint_suffix = worker_name.find(
" [");
574 if (hint_suffix != std::string::npos) {
575 worker_name.erase(hint_suffix);
579 const auto& lns_suffix = worker_name.find(
'(');
580 if (lns_suffix != std::string::npos) {
581 worker_name.erase(lns_suffix);
585 const auto fixed_suffix = worker_name.find(
" fixed_bools:");
586 if (fixed_suffix != std::string::npos) {
587 worker_name.erase(fixed_suffix);
593void SharedResponseManager::RegisterSolutionFound(
594 const std::string& improvement_info) {
595 if (improvement_info.empty())
return;
599void SharedResponseManager::RegisterObjectiveBoundImprovement(
600 const std::string& improvement_info) {
601 if (improvement_info.empty() || improvement_info ==
"initial domain")
return;
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;
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;
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];
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;
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;
658 if (!changed_lb && !changed_ub)
continue;
661 lower_bounds_[
var] = new_lb;
664 upper_bounds_[
var] = new_ub;
666 changed_variables_since_last_synchronize_.Set(
var);
671 if (num_improvements > 0) {
672 VLOG(2) << worker_name <<
" exports " << num_improvements
678 absl::MutexLock mutex_lock(&mutex_);
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);
687 changed_variables_since_last_synchronize_.ClearAll();
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);
708 int id, std::vector<int>* variables, std::vector<int64>* new_lower_bounds,
709 std::vector<int64>* new_upper_bounds) {
711 new_lower_bounds->clear();
712 new_upper_bounds->clear();
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]);
720 id_to_changed_variables_[id].ClearAll();
#define LOG_IF(severity, condition)
#define DCHECK_LE(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_LT(val1, val2)
#define VLOG(verboselevel)
double GetElapsedDeterministicTime() const
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
IntegerVariable NumIntegerVariables() const
Class that owns everything related to a particular optimization model.
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)
std::vector< double > GetNewSolution()
bool HasNewSolution() const
void NewLPSolution(std::vector< double > lp_solution)
void NewRelaxationSolution(const CpSolverResponse &response)
bool ProblemIsSolved() const
CpSolverResponse GetResponse()
void SetStatsFromModel(Model *model)
SharedResponseManager(bool log_updates, bool enumerate_all_solutions, const CpModelProto *proto, const WallTimer *wall_timer, SharedTimeLimit *shared_time_limit)
double PrimalIntegral() const
void UpdatePrimalIntegral()
IntegerValue GetInnerObjectiveUpperBound()
IntegerValue SynchronizedInnerObjectiveUpperBound()
IntegerValue SynchronizedInnerObjectiveLowerBound()
void NewSolution(const CpSolverResponse &response, Model *model)
void DisplayImprovementStatistics()
void NotifyThatImprovingProblemIsInfeasible(const std::string &worker_info)
IntegerValue BestSolutionInnerObjectiveValue()
void AddUnsatCore(const std::vector< int > &core)
void SetGapLimitsFromParameters(const SatParameters ¶meters)
int AddSolutionCallback(std::function< void(const CpSolverResponse &)> callback)
void SetUpdatePrimalIntegralOnEachChange(bool set)
void LoadDebugSolution(Model *)
IntegerValue GetInnerObjectiveLowerBound()
void UnregisterCallback(int callback_id)
void UpdateInnerObjectiveBounds(const std::string &update_info, IntegerValue lb, IntegerValue ub)
void Add(const Solution &solution)
void AddInternal(const Solution &solution) ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_)
CpModelProto const * model_proto
SharedResponseManager * response
SharedTimeLimit * time_limit
static const int64 kint64max
static const int64 kint64min
absl::Status GetTextProto(const absl::string_view &filename, google::protobuf::Message *proto, int flags)
absl::Status SetTextProto(const absl::string_view &filename, const google::protobuf::Message &proto, int flags)
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)
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...
IntegerVariable objective_var
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\"'.")