14#ifndef OR_TOOLS_SAT_CP_MODEL_LNS_H_
15#define OR_TOOLS_SAT_CP_MODEL_LNS_H_
27#include "absl/base/thread_annotations.h"
28#include "absl/container/flat_hash_set.h"
29#include "absl/log/check.h"
30#include "absl/random/bit_gen_ref.h"
31#include "absl/strings/string_view.h"
32#include "absl/synchronization/mutex.h"
33#include "absl/types/span.h"
34#include "google/protobuf/arena.h"
35#include "ortools/sat/cp_model.pb.h"
38#include "ortools/sat/sat_parameters.pb.h"
54 google::protobuf::ArenaOptions(
55 {.start_block_size =
static_cast<size_t>(
57 delta(*google::protobuf::Arena::Create<CpModelProto>(
arena.get())) {}
73 std::unique_ptr<google::protobuf::Arena>
arena;
110 SatParameters
const* parameters,
132 const CpSolverResponse& initial_solution,
133 absl::Span<const int> relaxed_variables)
const;
149 CpModelProto* model_proto)
const;
158 std::vector<int> result;
160 result = active_variables_;
166 return active_variables_.size();
170 std::vector<int> result;
172 result = active_objective_variables_;
178 const int target_size =
179 static_cast<int>(std::ceil(difficulty * active_variables_.size()));
180 return target_size == active_variables_.size();
187 return active_variables_;
194 std::vector<int> result;
195 result = active_objective_variables_;
203 const CpSolverResponse& initial_solution)
const
205 ABSL_LOCKS_EXCLUDED(domain_mutex_);
213 return constraint_to_var_;
217 return var_to_constraint_;
222 ConstraintProto::ConstraintCase
type)
const {
223 if (
type >= type_to_constraints_.size())
return {};
224 return absl::MakeSpan(type_to_constraints_[
type]);
230 absl::Span<const int> unfiltered_intervals,
231 const CpSolverResponse& initial_solution)
const;
238 const CpSolverResponse& initial_solution)
const;
253 const CpSolverResponse& initial_solution)
const;
266 const CpSolverResponse& initial_solution)
const;
272 const absl::flat_hash_set<int>& ignored_intervals,
273 const CpSolverResponse& initial_solution, absl::BitGenRef random)
const;
280 const CpModelProto&
ModelProto()
const {
return model_proto_; }
281 const SatParameters&
Parameters()
const {
return parameters_; }
284 return *shared_response_;
301 void InitializeHelperData();
305 void RecomputeHelperData();
308 bool IsConstant(
int var)
const ABSL_SHARED_LOCKS_REQUIRED(domain_mutex_);
312 bool ObjectiveDomainIsConstraining() const
313 ABSL_SHARED_LOCKS_REQUIRED(domain_mutex_);
318 bool IntervalIsActive(
int index,
319 const CpSolverResponse& initial_solution) const
320 ABSL_SHARED_LOCKS_REQUIRED(domain_mutex_);
322 const SatParameters& parameters_;
323 const CpModelProto& model_proto_;
324 int shared_bounds_id_;
332 std::vector<
char> local_arena_storage_;
333 std::unique_ptr<
google::protobuf::Arena> local_arena_;
340 CpModelProto model_proto_with_only_variables_ ABSL_GUARDED_BY(domain_mutex_);
343 std::vector<
std::vector<
int>> type_to_constraints_;
347 std::vector<
bool> is_in_objective_;
350 std::vector<
bool> has_positive_objective_coefficient_;
355 CpModelProto* simplified_model_proto_ ABSL_GUARDED_BY(
graph_mutex_);
371 std::vector<
int> var_to_component_index_ ABSL_GUARDED_BY(
graph_mutex_);
380 std::vector<
int> active_objective_variables_ ABSL_GUARDED_BY(
graph_mutex_);
382 std::vector<
int> tmp_row_;
395 helper->
Parameters().lns_initial_deterministic_limit()),
396 difficulty_(helper->
Parameters().lns_initial_difficulty()) {}
404 CpSolverStatus
status = CpSolverStatus::UNKNOWN;
457 SolveData& data, absl::BitGenRef random) = 0;
474 solve_data_.push_back(data);
494 return num_fully_solved_calls_;
500 return num_improving_calls_;
508 return num_consecutive_non_improving_calls_;
514 return difficulty_.value();
530 std::vector<SolveData> solve_data_;
531 std::vector<double> tmp_dtimes_;
539 int64_t num_calls_ = 0;
540 int64_t num_fully_solved_calls_ = 0;
541 int64_t num_improving_calls_ = 0;
542 int64_t num_consecutive_non_improving_calls_ = 0;
543 int64_t next_time_limit_bump_ = 50;
544 double current_average_ = 0.0;
556 Neighborhood Generate(
const CpSolverResponse& initial_solution,
557 SolveData& data, absl::BitGenRef random)
final;
571 Neighborhood Generate(
const CpSolverResponse& initial_solution,
572 SolveData& data, absl::BitGenRef random)
final;
587 Neighborhood Generate(
const CpSolverResponse& initial_solution,
588 SolveData& data, absl::BitGenRef random)
final;
598 Neighborhood Generate(
const CpSolverResponse& initial_solution,
599 SolveData& data, absl::BitGenRef random)
final;
611 Neighborhood Generate(
const CpSolverResponse& initial_solution,
612 SolveData& data, absl::BitGenRef random)
final;
631 Neighborhood Generate(
const CpSolverResponse& initial_solution,
632 SolveData& data, absl::BitGenRef random)
final;
648 global_time_limit_(global_time_limit),
655 Neighborhood Generate(
const CpSolverResponse& initial_solution,
656 SolveData& data, absl::BitGenRef random)
final;
668 absl::Span<const int> intervals_to_relax,
669 absl::Span<const int> variables_to_fix,
670 const CpSolverResponse& initial_solution, absl::BitGenRef random,
677 absl::Span<
const std::pair<int, int>> precedences,
678 const CpSolverResponse& initial_solution,
691 Neighborhood Generate(
const CpSolverResponse& initial_solution,
692 SolveData& data, absl::BitGenRef random)
final;
707 Neighborhood Generate(
const CpSolverResponse& initial_solution,
708 SolveData& data, absl::BitGenRef random)
final;
719 Neighborhood Generate(
const CpSolverResponse& initial_solution,
720 SolveData& data, absl::BitGenRef random)
final;
731 const std::vector<std::vector<int>>& intervals_in_constraints,
732 absl::string_view
name)
734 intervals_in_constraints_(intervals_in_constraints) {}
736 Neighborhood Generate(
const CpSolverResponse& initial_solution,
737 SolveData& data, absl::BitGenRef random)
final;
740 const std::vector<std::vector<int>> intervals_in_constraints_;
753 Neighborhood Generate(
const CpSolverResponse& initial_solution,
754 SolveData& data, absl::BitGenRef random)
final;
766 Neighborhood Generate(
const CpSolverResponse& initial_solution,
767 SolveData& data, absl::BitGenRef random)
final;
781 Neighborhood Generate(
const CpSolverResponse& initial_solution,
782 SolveData& data, absl::BitGenRef random)
final;
796 Neighborhood Generate(
const CpSolverResponse& initial_solution,
797 SolveData& data, absl::BitGenRef random)
final;
809 Neighborhood Generate(
const CpSolverResponse& initial_solution,
810 SolveData& data, absl::BitGenRef random)
final;
818 absl::string_view
name)
821 Neighborhood Generate(
const CpSolverResponse& initial_solution,
822 SolveData& data, absl::BitGenRef random)
final;
830 absl::string_view
name)
833 Neighborhood Generate(
const CpSolverResponse& initial_solution,
834 SolveData& data, absl::BitGenRef random)
final;
850 Neighborhood Generate(
const CpSolverResponse& initial_solution,
851 SolveData& data, absl::BitGenRef random)
final;
875 absl::string_view
name)
877 response_manager_(response_manager),
878 lp_solutions_(lp_solutions),
879 incomplete_solutions_(incomplete_solutions) {
880 CHECK(lp_solutions_ !=
nullptr);
881 CHECK(incomplete_solutions !=
nullptr);
885 Neighborhood Generate(
const CpSolverResponse& initial_solution,
886 SolveData& data, absl::BitGenRef random)
final;
889 bool ReadyToGenerate()
const override;
ArcGraphNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
ConstraintGraphNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
DecompositionGraphNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
LocalBranchingLpBasedNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name, ModelSharedTimeLimit *const global_time_limit, SharedClasses *shared)
The model "singleton" shared time limit.
std::vector< int > ImprovableObjectiveVariablesWhileHoldingLock(const CpSolverResponse &initial_solution) const ABSL_LOCKS_EXCLUDED(domain_mutex_)
Neighborhood FullNeighborhood() const
Returns a neighborhood that correspond to the full problem.
bool IsActive(int var) const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
CpModelProto UpdatedModelProtoCopy() const
Returns a copy of the problem proto with updated domains.
std::vector< std::vector< int > > GetRoutingPathBooleanVariables(const CpSolverResponse &initial_solution) const
Neighborhood FixAllVariables(const CpSolverResponse &initial_solution) const
Neighborhood NoNeighborhood() const
Neighborhood FixGivenVariables(const CpSolverResponse &base_solution, const Bitset64< int > &variables_to_fix) const
const std::vector< int > & ActiveVariablesWhileHoldingLock() const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
const CompactVectorVector< int, int > & VarToConstraint() const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
int NumActiveVariables() const
const SharedResponseManager & shared_response() const
Neighborhood RelaxGivenVariables(const CpSolverResponse &initial_solution, absl::Span< const int > relaxed_variables) const
void Synchronize() override
std::vector< int > ActiveVariables() const
Returns the list of "active" variables.
std::vector< std::vector< int > > GetUniqueIntervalSets() const
const CompactVectorVector< int, int > & ConstraintToVar() const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
std::vector< ActiveRectangle > GetActiveRectangles(const CpSolverResponse &initial_solution) const
bool DifficultyMeansFullNeighborhood(double difficulty) const
const CpModelProto & ModelProto() const
void AddSolutionHinting(const CpSolverResponse &initial_solution, CpModelProto *model_proto) const
std::vector< int > ActiveObjectiveVariablesWhileHoldingLock() const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
std::function< void()> GenerateTask(int64_t) override
const SatParameters & Parameters() const
std::vector< int > GetActiveIntervals(const CpSolverResponse &initial_solution) const
std::vector< std::pair< int, int > > GetSchedulingPrecedences(const absl::flat_hash_set< int > &ignored_intervals, const CpSolverResponse &initial_solution, absl::BitGenRef random) const
absl::Span< const int > TypeToConstraints(ConstraintProto::ConstraintCase type) const
Returns all the constraints indices of a given type.
bool TaskIsAvailable() override
SubSolver interface.
std::vector< int > ActiveObjectiveVariables() const
NeighborhoodGeneratorHelper(CpModelProto const *model_proto, SatParameters const *parameters, SharedResponseManager *shared_response, ModelSharedTimeLimit *global_time_limit, SharedBoundsManager *shared_bounds=nullptr)
std::vector< int > KeepActiveIntervals(absl::Span< const int > unfiltered_intervals, const CpSolverResponse &initial_solution) const
NeighborhoodGeneratorHelper::ActiveRectangle ActiveRectangle
virtual bool ReadyToGenerate() const
Returns true if the neighborhood generator can generate a neighborhood.
double deterministic_limit() const
The current time limit that the sub-solve should use on this generator.
int64_t num_improving_calls() const
Out of num_calls(), how many improved the given solution.
double deterministic_limit_
void AddSolveData(SolveData data)
std::string name() const
Returns a short description of the generator.
virtual ~NeighborhoodGenerator()=default
virtual Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random)=0
absl::Mutex generator_mutex_
double difficulty() const
The current difficulty of this generator.
double GetUCBScore(int64_t total_num_calls) const
int64_t num_calls() const
Number of times this generator was called.
const NeighborhoodGeneratorHelper & helper_
int64_t num_fully_solved_calls() const
Number of time the neighborhood was fully solved (OPTIMAL/INFEASIBLE).
int64_t num_consecutive_non_improving_calls() const
NeighborhoodGenerator(absl::string_view name, NeighborhoodGeneratorHelper const *helper)
RandomIntervalSchedulingNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RandomPrecedenceSchedulingNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RandomPrecedencesPackingNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RandomRectanglesPackingNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RectanglesPackingRelaxOneNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RectanglesPackingRelaxTwoNeighborhoodsGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RelaxRandomConstraintsGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RelaxRandomVariablesGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RelaxationInducedNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const SharedResponseManager *response_manager, const SharedLPSolutionRepository *lp_solutions, SharedIncompleteSolutionManager *incomplete_solutions, absl::string_view name)
RoutingFullPathNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RoutingPathNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RoutingRandomNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
SchedulingResourceWindowsNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::vector< std::vector< int > > &intervals_in_constraints, absl::string_view name)
SchedulingTimeWindowNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
Solutions coming from the LP.
SlicePackingNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
SubSolver(absl::string_view name, SubsolverType type)
SubsolverType type() const
Returns the type of the subsolver.
VariableGraphNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
Neighborhood GenerateSchedulingNeighborhoodFromIntervalPrecedences(const absl::Span< const std::pair< int, int > > precedences, const CpSolverResponse &initial_solution, const NeighborhoodGeneratorHelper &helper)
Neighborhood GenerateSchedulingNeighborhoodFromRelaxedIntervals(absl::Span< const int > intervals_to_relax, absl::Span< const int > variables_to_fix, const CpSolverResponse &initial_solution, absl::BitGenRef random, const NeighborhoodGeneratorHelper &helper)
In SWIG mode, we don't want anything besides these top-level includes.
absl::flat_hash_set< int > no_overlap_2d_constraints
Adds solve data about one "solved" neighborhood.
double deterministic_time
The time it took to solve this neighborhood.
IntegerValue initial_best_objective
IntegerValue new_objective
double difficulty
The difficulty when this neighborhood was generated.
double deterministic_limit
The deterministic time limit given to the solver for this neighborhood.
CpSolverStatus status
The status of the sub-solve.
int task_id
For debugging.
bool operator<(const SolveData &o) const
This is just used to construct a deterministic order for the updates.
IntegerValue base_objective
Neighborhood returned by Neighborhood generators.
int num_relaxed_variables_in_objective
std::string source_info
Overwrites the name of the neighborhood generator in the logs.
bool is_simple
True if this neighborhood was just obtained by fixing some variables.
int num_relaxed_variables
Statistic, only filled when is_simple is true.
Neighborhood(int num_variables_hint=10)
std::unique_ptr< google::protobuf::Arena > arena
bool is_generated
True if neighborhood generator was able to generate a neighborhood.
std::vector< int > variables_that_can_be_fixed_to_local_optimum
static constexpr int kDefaultArenaSizePerVariable