14 #ifndef OR_TOOLS_SAT_CP_MODEL_LNS_H_
15 #define OR_TOOLS_SAT_CP_MODEL_LNS_H_
19 #include "absl/container/flat_hash_map.h"
20 #include "absl/random/bit_gen_ref.h"
21 #include "absl/synchronization/mutex.h"
22 #include "absl/types/span.h"
24 #include "ortools/sat/cp_model.pb.h"
80 const CpSolverResponse& initial_solution,
81 const std::vector<int>& variables_to_fix)
const;
85 const std::vector<int>& constraints_to_remove)
const;
90 const CpSolverResponse& initial_solution,
91 const std::vector<int>& relaxed_variables)
const;
111 return constraint_to_var_;
114 return var_to_constraint_;
119 ConstraintProto::ConstraintCase type)
const {
120 if (type >= type_to_constraints_.size())
return {};
121 return absl::MakeSpan(type_to_constraints_[type]);
129 const CpSolverResponse& initial_solution)
const;
133 const CpModelProto&
ModelProto()
const {
return model_proto_; }
134 const SatParameters&
Parameters()
const {
return parameters_; }
145 return *shared_response_;
151 void RecomputeHelperData();
154 bool IsConstant(
int var)
const;
156 const SatParameters& parameters_;
157 const CpModelProto& model_proto_;
158 int shared_bounds_id_;
169 CpModelProto model_proto_with_only_variables_;
171 mutable absl::Mutex mutex_;
174 std::vector<std::vector<int>> type_to_constraints_;
177 std::vector<std::vector<int>> constraint_to_var_;
178 std::vector<std::vector<int>> var_to_constraint_;
184 std::vector<bool> active_variables_set_;
185 std::vector<int> active_variables_;
211 double difficulty, absl::BitGenRef random) = 0;
237 CpSolverStatus
status = CpSolverStatus::UNKNOWN;
280 absl::MutexLock mutex_lock(&
mutex_);
281 solve_data_.push_back(data);
293 absl::MutexLock mutex_lock(&
mutex_);
299 absl::MutexLock mutex_lock(&
mutex_);
300 return num_fully_solved_calls_;
305 absl::MutexLock mutex_lock(&
mutex_);
306 return difficulty_.
value();
311 absl::MutexLock mutex_lock(&
mutex_);
312 return deterministic_limit_;
317 absl::MutexLock mutex_lock(&
mutex_);
318 return deterministic_time_;
332 std::vector<SolveData> solve_data_;
337 double deterministic_limit_ = 0.1;
341 int64 num_calls_ = 0;
342 int64 num_fully_solved_calls_ = 0;
343 int64 num_consecutive_non_improving_calls_ = 0;
344 double deterministic_time_ = 0.0;
345 double current_average_ = 0.0;
355 double difficulty, absl::BitGenRef random)
final;
367 double difficulty, absl::BitGenRef random)
final;
380 double difficulty, absl::BitGenRef random)
final;
393 double difficulty, absl::BitGenRef random)
final;
400 const absl::Span<const int> intervals_to_relax,
401 const CpSolverResponse& initial_solution,
402 const NeighborhoodGeneratorHelper& helper);
416 double difficulty, absl::BitGenRef random)
final;
428 double difficulty, absl::BitGenRef random)
final;
453 const std::string&
name)
455 response_manager_(response_manager),
459 CHECK(lp_solutions_ !=
nullptr || relaxation_solutions_ !=
nullptr ||
465 double difficulty, absl::BitGenRef random)
final;
487 double difficulty, absl::BitGenRef random)
final;
507 double difficulty, absl::BitGenRef random)
final;
515 void AdditionalProcessingOnSynchronize(
const SolveData& solve_data)
override
516 ABSL_EXCLUSIVE_LOCKS_REQUIRED(
mutex_);
519 std::vector<double> constraint_weights_;
520 int num_removable_constraints_ = 0;
523 absl::flat_hash_map<int64, std::vector<int>> removed_constraints_
528 int64 next_available_id_ ABSL_GUARDED_BY(
mutex_) = 0;
bool ReadyToGenerate() const override
ConsecutiveConstraintsRelaxationNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
bool IsRelaxationGenerator() const override
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
ConstraintGraphNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
NeighborhoodGeneratorHelper(CpModelProto const *model_proto, SatParameters const *parameters, SharedResponseManager *shared_response, SharedTimeLimit *shared_time_limit=nullptr, SharedBoundsManager *shared_bounds=nullptr)
const SharedResponseManager & shared_response() const
const std::vector< std::vector< int > > & VarToConstraint() const
Neighborhood FullNeighborhood() const
Neighborhood FixAllVariables(const CpSolverResponse &initial_solution) const
bool IsActive(int var) const
absl::Mutex * MutableMutex() const
Neighborhood FixGivenVariables(const CpSolverResponse &initial_solution, const std::vector< int > &variables_to_fix) const
std::function< void()> GenerateTask(int64 task_id) override
const absl::Span< const int > TypeToConstraints(ConstraintProto::ConstraintCase type) const
Neighborhood RelaxGivenVariables(const CpSolverResponse &initial_solution, const std::vector< int > &relaxed_variables) const
std::vector< int > GetActiveIntervals(const CpSolverResponse &initial_solution) const
const std::vector< int > & ActiveVariables() const
const CpModelProto & ModelProto() const
bool TaskIsAvailable() override
Neighborhood RemoveMarkedConstraints(const std::vector< int > &constraints_to_remove) const
const std::vector< std::vector< int > > & ConstraintToVar() const
const SatParameters & Parameters() const
void Synchronize() override
virtual Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random)=0
virtual bool IsRelaxationGenerator() const
virtual ~NeighborhoodGenerator()
void AddSolveData(SolveData data)
virtual bool ReadyToGenerate() const
double difficulty() const
NeighborhoodGenerator(const std::string &name, NeighborhoodGeneratorHelper const *helper)
double GetUCBScore(int64 total_num_calls) const
int64 num_fully_solved_calls() const
virtual void AdditionalProcessingOnSynchronize(const SolveData &solve_data)
const NeighborhoodGeneratorHelper & helper_
double deterministic_time() const
double deterministic_limit() const
RelaxationInducedNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const SharedResponseManager *response_manager, const SharedRelaxationSolutionRepository *relaxation_solutions, const SharedLPSolutionRepository *lp_solutions, SharedIncompleteSolutionManager *incomplete_solutions, const std::string &name)
bool ReadyToGenerate() const override
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
SchedulingNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
SchedulingTimeWindowNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
SimpleConstraintNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
SimpleNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
VariableGraphNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
bool ReadyToGenerate() const override
WeightedRandomRelaxationNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
bool IsRelaxationGenerator() const override
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
SharedRelaxationSolutionRepository * relaxation_solutions
SharedLPSolutionRepository * lp_solutions
CpModelProto const * model_proto
SharedIncompleteSolutionManager * incomplete_solutions
Neighborhood GenerateSchedulingNeighborhoodForRelaxation(const absl::Span< const int > intervals_to_relax, const CpSolverResponse &initial_solution, const NeighborhoodGeneratorHelper &helper)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool operator<(const SolveData &o) const
IntegerValue base_objective
IntegerValue initial_best_objective_bound
IntegerValue initial_best_objective
double deterministic_limit
IntegerValue new_objective
IntegerValue new_objective_bound
double deterministic_time