27 #ifndef OR_TOOLS_BOP_BOP_LS_H_
28 #define OR_TOOLS_BOP_BOP_LS_H_
33 #include "absl/container/flat_hash_map.h"
34 #include "absl/container/flat_hash_set.h"
35 #include "absl/random/random.h"
42 #include "ortools/sat/boolean_problem.pb.h"
82 std::vector<sat::Literal>* propagated_literals);
104 class LocalSearchAssignmentIterator;
123 bool ShouldBeRun(
const ProblemState& problem_state)
const override;
128 int64_t state_update_stamp_;
133 const int max_num_decisions_;
142 std::unique_ptr<LocalSearchAssignmentIterator> assignment_iterator_;
157 template <
typename IntType>
170 void ChangeState(IntType i,
bool should_be_inside);
174 int size()
const {
return size_; }
177 const std::vector<IntType>&
Superset()
const {
return stack_; }
190 std::vector<IntType> stack_;
191 std::vector<bool> in_stack_;
195 std::vector<int> saved_sizes_;
196 std::vector<int> saved_stack_sizes_;
201 template <
typename IntType>
209 for (IntType i(0); i < size; ++i) {
210 hashes_[i] = random_.
Rand64();
221 uint64_t
Hash(
const std::vector<IntType>& set)
const {
223 for (
const IntType i : set)
hash ^= hashes_[i];
229 uint64_t
Hash(IntType e)
const {
return hashes_[e]; }
269 const sat::LinearBooleanProblem& problem);
289 void Assign(
const std::vector<sat::Literal>& literals);
319 return infeasible_constraint_set_.
size();
324 return infeasible_constraint_set_.
Superset();
342 return constraint_lower_bounds_[constraint];
347 return constraint_upper_bounds_[constraint];
354 return constraint_values_[constraint];
368 void InitializeConstraintSetHasher();
375 DEFINE_INT_TYPE(ConstraintIndexWithDirection, int32_t);
376 ConstraintIndexWithDirection FromConstraintIndex(ConstraintIndex
index,
378 return ConstraintIndexWithDirection(2 *
index.value() + (up ? 1 : 0));
383 void MakeObjectiveConstraintInfeasible(
int delta);
387 struct ConstraintEntry {
388 ConstraintEntry(ConstraintIndex c, int64_t w) : constraint(c),
weight(w) {}
389 ConstraintIndex constraint;
399 BopSolution assignment_;
400 BopSolution reference_;
403 BacktrackableIntegerSet<ConstraintIndex> infeasible_constraint_set_;
408 std::vector<int> flipped_var_trail_backtrack_levels_;
409 std::vector<VariableIndex> flipped_var_trail_;
412 std::vector<sat::Literal> tmp_potential_repairs_;
413 NonOrderedSetHasher<ConstraintIndexWithDirection> constraint_set_hasher_;
414 absl::flat_hash_map<uint64_t, std::vector<sat::Literal>>
415 hash_to_potential_repairs_;
441 const sat::LinearBooleanProblem& problem,
467 TermIndex init_term_index,
468 TermIndex start_term_index)
const;
472 bool RepairIsValid(ConstraintIndex ct_index, TermIndex term_index)
const;
489 void SortTermsOfEachConstraints(
int num_variables);
493 by_constraint_matrix_;
508 int max_num_decisions,
509 int max_num_broken_constraints,
516 use_potential_one_flip_repairs_ = v;
540 return better_solution_has_been_found_;
553 void UseCurrentStateAsReference();
556 static constexpr
size_t kStoredMaxDecisions = 4;
564 SearchNode(ConstraintIndex c, TermIndex t) : constraint(c), term_index(t) {}
565 ConstraintIndex constraint;
566 TermIndex term_index;
570 void ApplyDecision(sat::Literal
literal);
581 bool NewStateIsInTranspositionTable(sat::Literal l);
584 void InsertInTranspositionTable();
588 void InitializeTranspositionTableKey(
589 std::array<int32_t, kStoredMaxDecisions>*
a);
594 bool EnqueueNextRepairingTermIfAny(ConstraintIndex ct_to_repair,
597 const int max_num_decisions_;
598 const int max_num_broken_constraints_;
599 bool better_solution_has_been_found_;
600 AssignmentAndConstraintFeasibilityMaintainer maintainer_;
601 SatWrapper*
const sat_wrapper_;
602 OneFlipConstraintRepairer repairer_;
603 std::vector<SearchNode> search_nodes_;
607 std::vector<sat::Literal> tmp_propagated_literals_;
622 bool use_transposition_table_;
623 absl::flat_hash_set<std::array<int32_t, kStoredMaxDecisions>>
624 transposition_table_;
626 bool use_potential_one_flip_repairs_;
632 int64_t num_skipped_nodes_;
636 int64_t num_improvements_;
637 int64_t num_improvements_by_one_flip_repairs_;
638 int64_t num_inspected_one_flip_repairs_;
void resize(size_type new_size)
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
AssignmentAndConstraintFeasibilityMaintainer(const sat::LinearBooleanProblem &problem)
int64_t ConstraintLowerBound(ConstraintIndex constraint) const
const BopSolution & reference() const
const std::vector< ConstraintIndex > & PossiblyInfeasibleConstraints() const
void AddBacktrackingLevel()
void UseCurrentStateAsReference()
static const ConstraintIndex kObjectiveConstraint
int NumInfeasibleConstraints() const
std::string DebugString() const
void SetReferenceSolution(const BopSolution &reference_solution)
int64_t ConstraintUpperBound(ConstraintIndex constraint) const
size_t NumConstraints() const
bool ConstraintIsFeasible(ConstraintIndex constraint) const
int64_t ConstraintValue(ConstraintIndex constraint) const
bool Assignment(VariableIndex var) const
void Assign(const std::vector< sat::Literal > &literals)
const std::vector< sat::Literal > & PotentialOneFlipRepairs()
const std::vector< IntType > & Superset() const
void ClearAndResize(IntType n)
void AddBacktrackingLevel()
BacktrackableIntegerSet()
void ChangeState(IntType i, bool should_be_inside)
const std::string & name() const
bool Value(VariableIndex var) const
~LocalSearchAssignmentIterator()
void SynchronizeSatWrapper()
LocalSearchAssignmentIterator(const ProblemState &problem_state, int max_num_decisions, int max_num_broken_constraints, SatWrapper *sat_wrapper)
void UseTranspositionTable(bool v)
std::string DebugString() const
void UsePotentialOneFlipRepairs(bool v)
void Synchronize(const ProblemState &problem_state)
double deterministic_time() const
const BopSolution & LastReferenceAssignment() const
bool BetterSolutionHasBeenFound() const
LocalSearchOptimizer(const std::string &name, int max_num_decisions, sat::SatSolver *sat_propagator)
~LocalSearchOptimizer() override
bool IsInitialized() const
void Initialize(int size)
uint64_t Hash(IntType e) const
void IgnoreElement(IntType e)
uint64_t Hash(const std::vector< IntType > &set) const
sat::Literal GetFlip(ConstraintIndex ct_index, TermIndex term_index) const
static const TermIndex kInvalidTerm
ConstraintIndex ConstraintToRepair() const
bool RepairIsValid(ConstraintIndex ct_index, TermIndex term_index) const
TermIndex NextRepairingTerm(ConstraintIndex ct_index, TermIndex init_term_index, TermIndex start_term_index) const
static const TermIndex kInitTerm
OneFlipConstraintRepairer(const sat::LinearBooleanProblem &problem, const AssignmentAndConstraintFeasibilityMaintainer &maintainer, const sat::VariablesAssignment &sat_assignment)
static const ConstraintIndex kInvalidConstraint
const sat::VariablesAssignment & SatAssignment() const
SatWrapper(sat::SatSolver *sat_solver)
std::vector< sat::Literal > FullSatTrail() const
int ApplyDecision(sat::Literal decision_literal, std::vector< sat::Literal > *propagated_literals)
void ExtractLearnedInfo(LearnedInfo *info)
bool IsModelUnsat() const
double deterministic_time() const
const VariablesAssignment & Assignment() const
bool IsModelUnsat() const
SharedTimeLimit * time_limit
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
ConstraintTerm(VariableIndex v, int64_t w)