14 #ifndef OR_TOOLS_SAT_SYNCHRONIZATION_H_
15 #define OR_TOOLS_SAT_SYNCHRONIZATION_H_
21 #include "absl/random/bit_gen_ref.h"
22 #include "absl/random/random.h"
23 #include "absl/synchronization/mutex.h"
27 #include "ortools/sat/cp_model.pb.h"
31 #include "ortools/sat/sat_parameters.pb.h"
42 template <
typename ValueType>
98 void Add(
const Solution& solution);
111 ABSL_EXCLUSIVE_LOCKS_REQUIRED(
mutex_);
160 std::vector<std::vector<double>> solutions_;
161 mutable absl::Mutex mutex_;
193 std::function<
void(
const CpSolverResponse&)>
callback);
238 IntegerValue lb, IntegerValue ub);
293 dump_prefix_ = dump_prefix;
300 void TestGapLimitsIfNeeded() ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
301 void FillObjectiveValuesInBestResponse()
302 ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
304 ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
305 void UpdatePrimalIntegralInternal() ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
307 void RegisterSolutionFound(const std::
string& improvement_info)
308 ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
309 void RegisterObjectiveBoundImprovement(const std::
string& improvement_info)
310 ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
312 const
bool log_updates_;
313 const
bool enumerate_all_solutions_;
314 const CpModelProto& model_proto_;
318 mutable
absl::Mutex mutex_;
321 double absolute_gap_limit_ ABSL_GUARDED_BY(mutex_) = 0.0;
322 double relative_gap_limit_ ABSL_GUARDED_BY(mutex_) = 0.0;
324 CpSolverResponse best_response_ ABSL_GUARDED_BY(mutex_);
327 int num_solutions_ ABSL_GUARDED_BY(mutex_) = 0;
328 int64 inner_objective_lower_bound_ ABSL_GUARDED_BY(mutex_) =
kint64min;
329 int64 inner_objective_upper_bound_ ABSL_GUARDED_BY(mutex_) =
kint64max;
330 int64 best_solution_objective_value_ ABSL_GUARDED_BY(mutex_) =
kint64max;
332 IntegerValue synchronized_inner_objective_lower_bound_
333 ABSL_GUARDED_BY(mutex_) = IntegerValue(
kint64min);
334 IntegerValue synchronized_inner_objective_upper_bound_
335 ABSL_GUARDED_BY(mutex_) = IntegerValue(
kint64max);
337 bool update_integral_on_each_change_ ABSL_GUARDED_BY(mutex_) = false;
338 double primal_integral_ ABSL_GUARDED_BY(mutex_) = 0.0;
339 double last_absolute_gap_ ABSL_GUARDED_BY(mutex_) = 0.0;
340 double last_primal_integral_time_stamp_ ABSL_GUARDED_BY(mutex_) = 0.0;
342 int next_callback_id_ ABSL_GUARDED_BY(mutex_) = 0;
343 std::vector<std::pair<
int, std::function<
void(const CpSolverResponse&)>>>
344 callbacks_ ABSL_GUARDED_BY(mutex_);
347 std::
string dump_prefix_;
350 std::map<std::
string,
int> primal_improvements_count_ ABSL_GUARDED_BY(mutex_);
351 std::map<std::
string,
int> dual_improvements_count_ ABSL_GUARDED_BY(mutex_);
363 void ReportPotentialNewBounds(
const CpModelProto&
model_proto,
364 const std::string& worker_name,
365 const std::vector<int>& variables,
366 const std::vector<int64>& new_lower_bounds,
367 const std::vector<int64>& new_upper_bounds);
376 void GetChangedBounds(
int id, std::vector<int>* variables,
377 std::vector<int64>* new_lower_bounds,
378 std::vector<int64>* new_upper_bounds);
385 const int num_variables_;
386 const CpModelProto& model_proto_;
391 std::vector<int64> lower_bounds_ ABSL_GUARDED_BY(mutex_);
392 std::vector<int64> upper_bounds_ ABSL_GUARDED_BY(mutex_);
394 ABSL_GUARDED_BY(mutex_);
397 std::vector<int64> synchronized_lower_bounds_ ABSL_GUARDED_BY(mutex_);
398 std::vector<int64> synchronized_upper_bounds_ ABSL_GUARDED_BY(mutex_);
399 std::deque<SparseBitset<int64>> id_to_changed_variables_
400 ABSL_GUARDED_BY(mutex_);
403 template <
typename ValueType>
405 absl::MutexLock mutex_lock(&mutex_);
406 return solutions_.size();
409 template <
typename ValueType>
412 absl::MutexLock mutex_lock(&mutex_);
413 return solutions_[i];
416 template <
typename ValueType>
418 int var_index,
int solution_index)
const {
419 absl::MutexLock mutex_lock(&mutex_);
420 return solutions_[solution_index].variable_values[var_index];
424 template <
typename ValueType>
427 absl::BitGenRef random)
const {
428 absl::MutexLock mutex_lock(&mutex_);
429 const int64 best_rank = solutions_[0].rank;
438 const int kExplorationThreshold = 100;
441 tmp_indices_.clear();
442 for (
int i = 0; i < solutions_.size(); ++i) {
443 const auto& solution = solutions_[i];
444 if (solution.rank == best_rank &&
445 solution.num_selected <= kExplorationThreshold) {
446 tmp_indices_.push_back(i);
451 if (tmp_indices_.empty()) {
452 index = absl::Uniform<int>(random, 0, solutions_.size());
454 index = tmp_indices_[absl::Uniform<int>(random, 0, tmp_indices_.size())];
456 solutions_[
index].num_selected++;
457 return solutions_[
index];
460 template <
typename ValueType>
462 absl::MutexLock mutex_lock(&mutex_);
463 AddInternal(solution);
466 template <
typename ValueType>
469 int worse_solution_index = 0;
470 for (
int i = 0; i < new_solutions_.size(); ++i) {
472 if (new_solutions_[i] == solution)
return;
473 if (new_solutions_[worse_solution_index] < new_solutions_[i]) {
474 worse_solution_index = i;
477 if (new_solutions_.size() < num_solutions_to_keep_) {
478 new_solutions_.push_back(solution);
479 }
else if (solution < new_solutions_[worse_solution_index]) {
480 new_solutions_[worse_solution_index] = solution;
484 template <
typename ValueType>
486 absl::MutexLock mutex_lock(&mutex_);
487 solutions_.insert(solutions_.end(), new_solutions_.begin(),
488 new_solutions_.end());
489 new_solutions_.clear();
496 if (solutions_.size() > num_solutions_to_keep_) {
497 solutions_.resize(num_solutions_to_keep_);
499 num_synchronization_++;
#define CHECK_GE(val1, val2)
Class that owns everything related to a particular optimization model.
void AddNewSolution(const std::vector< double > &lp_solution)
std::vector< double > GetNewSolution()
bool HasNewSolution() const
SharedLPSolutionRepository(int num_solutions_to_keep)
void NewLPSolution(std::vector< double > lp_solution)
SharedRelaxationSolutionRepository(int num_solutions_to_keep)
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
const SharedSolutionRepository< int64 > & SolutionsRepository() const
SharedSolutionRepository< int64 > * MutableSolutionsRepository()
void set_dump_prefix(const std::string &dump_prefix)
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)
Solution GetRandomBiasedSolution(absl::BitGenRef random) const
std::vector< int > tmp_indices_ ABSL_GUARDED_BY(mutex_)
SharedSolutionRepository(int num_solutions_to_keep)
int64 num_synchronization_ ABSL_GUARDED_BY(mutex_)=0
Solution GetSolution(int index) const
const int num_solutions_to_keep_
std::vector< Solution > new_solutions_ ABSL_GUARDED_BY(mutex_)
void AddInternal(const Solution &solution) ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_)
ValueType GetVariableValueInSolution(int var_index, int solution_index) const
std::vector< Solution > solutions_ ABSL_GUARDED_BY(mutex_)
CpModelProto const * model_proto
SharedResponseManager * response
static const int64 kint64max
static const int64 kint64min
void STLStableSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool operator<(const Solution &other) const
std::vector< ValueType > variable_values
bool operator==(const Solution &other) const