20#include "ortools/sat/cp_model.pb.h"
39 shared_time_limit_(shared_time_limit),
40 shared_bounds_(shared_bounds),
41 shared_response_(shared_response) {
42 CHECK(shared_response_ !=
nullptr);
43 if (shared_bounds_ !=
nullptr) {
46 *model_proto_with_only_variables_.mutable_variables() =
47 model_proto_.variables();
48 RecomputeHelperData();
53 absl::MutexLock mutex_lock(&mutex_);
54 if (shared_bounds_ !=
nullptr) {
55 std::vector<int> model_variables;
56 std::vector<int64> new_lower_bounds;
57 std::vector<int64> new_upper_bounds;
59 &new_lower_bounds, &new_upper_bounds);
61 for (
int i = 0; i < model_variables.size(); ++i) {
62 const int var = model_variables[i];
63 const int64 new_lb = new_lower_bounds[i];
64 const int64 new_ub = new_upper_bounds[i];
67 model_proto_with_only_variables_.variables(
var).domain();
68 const int64 old_lb = domain.Get(0);
69 const int64 old_ub = domain.Get(domain.size() - 1);
70 VLOG(3) <<
"Variable: " <<
var <<
" old domain: [" << old_lb <<
", "
71 << old_ub <<
"] new domain: [" << new_lb <<
", " << new_ub
95 new_domain, model_proto_with_only_variables_.mutable_variables(
var));
99 if (!model_variables.empty()) {
100 RecomputeHelperData();
105void NeighborhoodGeneratorHelper::RecomputeHelperData() {
112 var_to_constraint_.assign(model_proto_.variables_size(), {});
113 constraint_to_var_.assign(model_proto_.constraints_size(), {});
114 const auto register_var = [&](
int var,
int ct_index) {
116 if (IsConstant(
var))
return;
117 var_to_constraint_[
var].push_back(ct_index);
118 constraint_to_var_[ct_index].push_back(
var);
123 for (
int ct_index = 0; ct_index < model_proto_.constraints_size();
126 register_var(
var, ct_index);
130 if (parameters_.lns_expand_intervals_in_constraint_graph()) {
135 register_var(
var, ct_index);
141 type_to_constraints_.clear();
142 const int num_constraints = model_proto_.constraints_size();
143 for (
int c = 0; c < num_constraints; ++c) {
144 const int type = model_proto_.constraints(c).constraint_case();
145 if (type >= type_to_constraints_.size()) {
146 type_to_constraints_.resize(type + 1);
148 type_to_constraints_[type].push_back(c);
151 active_variables_.clear();
152 active_variables_set_.assign(model_proto_.variables_size(),
false);
154 if (parameters_.lns_focus_on_decision_variables()) {
155 for (
const auto& search_strategy : model_proto_.search_strategy()) {
156 for (
const int var : search_strategy.variables()) {
158 if (!active_variables_set_[pos_var] && !IsConstant(pos_var)) {
159 active_variables_set_[pos_var] =
true;
160 active_variables_.push_back(pos_var);
166 if (!active_variables_.empty())
return;
170 for (
int i = 0; i < model_proto_.variables_size(); ++i) {
171 if (!IsConstant(i)) {
172 active_variables_.push_back(i);
173 active_variables_set_[i] =
true;
179 return active_variables_set_[
var];
182bool NeighborhoodGeneratorHelper::IsConstant(
int var)
const {
183 return model_proto_with_only_variables_.variables(
var).domain_size() == 2 &&
184 model_proto_with_only_variables_.variables(
var).domain(0) ==
185 model_proto_with_only_variables_.variables(
var).domain(1);
192 neighborhood.
cp_model = model_proto_;
193 *neighborhood.
cp_model.mutable_variables() =
194 model_proto_with_only_variables_.variables();
199 const CpSolverResponse& initial_solution)
const {
200 std::vector<int> active_intervals;
202 const ConstraintProto& interval_ct =
ModelProto().constraints(i);
206 if (interval_ct.enforcement_literal().size() == 1) {
207 const int enforcement_ref = interval_ct.enforcement_literal(0);
208 const int enforcement_var =
PositiveRef(enforcement_ref);
209 const int value = initial_solution.solution(enforcement_var);
217 if (interval_ct.enforcement_literal().empty() &&
218 IsConstant(
PositiveRef(interval_ct.interval().start())) &&
219 IsConstant(
PositiveRef(interval_ct.interval().size())) &&
220 IsConstant(
PositiveRef(interval_ct.interval().end()))) {
224 active_intervals.push_back(i);
226 return active_intervals;
230 const CpSolverResponse& initial_solution,
231 const std::vector<int>& variables_to_fix)
const {
237 neighborhood.
cp_model.clear_solution_hint();
239 neighborhood.
cp_model.mutable_solution_hint()->add_vars(
var);
240 neighborhood.
cp_model.mutable_solution_hint()->add_values(
241 initial_solution.solution(
var));
244 neighborhood.
is_reduced = !variables_to_fix.empty();
245 if (!neighborhood.
is_reduced)
return neighborhood;
246 CHECK_EQ(initial_solution.solution_size(),
247 neighborhood.
cp_model.variables_size());
248 for (
const int var : variables_to_fix) {
249 neighborhood.
cp_model.mutable_variables(
var)->clear_domain();
250 neighborhood.
cp_model.mutable_variables(
var)->add_domain(
251 initial_solution.solution(
var));
252 neighborhood.
cp_model.mutable_variables(
var)->add_domain(
253 initial_solution.solution(
var));
264 const std::vector<int>& constraints_to_remove)
const {
269 if (constraints_to_remove.empty())
return neighborhood;
271 for (
const int constraint : constraints_to_remove) {
272 neighborhood.
cp_model.mutable_constraints(constraint)->Clear();
279 const CpSolverResponse& initial_solution,
280 const std::vector<int>& relaxed_variables)
const {
281 std::vector<bool> relaxed_variables_set(model_proto_.variables_size(),
false);
282 for (
const int var : relaxed_variables) relaxed_variables_set[
var] =
true;
283 std::vector<int> fixed_variables;
284 for (
const int i : active_variables_) {
285 if (!relaxed_variables_set[i]) {
286 fixed_variables.push_back(i);
293 const CpSolverResponse& initial_solution)
const {
294 std::vector<int> fixed_variables;
295 for (
const int i : active_variables_) {
296 fixed_variables.push_back(i);
306 absl::MutexLock mutex_lock(&
mutex_);
308 if (num_calls_ <= 10)
return std::numeric_limits<double>::infinity();
309 return current_average_ + sqrt((2 * log(total_num_calls)) / num_calls_);
313 absl::MutexLock mutex_lock(&
mutex_);
317 std::sort(solve_data_.begin(), solve_data_.end());
320 int num_fully_solved_in_batch = 0;
321 int num_not_fully_solved_in_batch = 0;
323 for (
const SolveData& data : solve_data_) {
330 if (data.status == CpSolverStatus::INFEASIBLE ||
331 data.status == CpSolverStatus::OPTIMAL) {
332 ++num_fully_solved_calls_;
333 ++num_fully_solved_in_batch;
335 ++num_not_fully_solved_in_batch;
344 const IntegerValue best_objective_improvement =
346 ? IntegerValue(
CapSub(data.new_objective_bound.value(),
347 data.initial_best_objective_bound.value()))
348 : IntegerValue(
CapSub(data.initial_best_objective.value(),
349 data.new_objective.value()));
350 if (best_objective_improvement > 0) {
351 num_consecutive_non_improving_calls_ = 0;
353 ++num_consecutive_non_improving_calls_;
358 const double gain_per_time_unit =
359 std::max(0.0,
static_cast<double>(best_objective_improvement.value())) /
360 (1.0 + data.deterministic_time);
361 if (num_calls_ <= 100) {
362 current_average_ += (gain_per_time_unit - current_average_) / num_calls_;
364 current_average_ = 0.9 * current_average_ + 0.1 * gain_per_time_unit;
367 deterministic_time_ += data.deterministic_time;
371 difficulty_.
Update(num_not_fully_solved_in_batch,
372 num_fully_solved_in_batch);
380 if (num_consecutive_non_improving_calls_ > 50) {
381 num_consecutive_non_improving_calls_ = 0;
382 deterministic_limit_ *= 1.02;
386 deterministic_limit_ =
std::min(60.0, deterministic_limit_);
394void GetRandomSubset(
double relative_size, std::vector<int>* base,
395 absl::BitGenRef random) {
398 std::shuffle(base->begin(), base->end(), random);
399 const int target_size = std::round(relative_size * base->size());
400 base->resize(target_size);
406 const CpSolverResponse& initial_solution,
double difficulty,
407 absl::BitGenRef random) {
409 GetRandomSubset(1.0 -
difficulty, &fixed_variables, random);
414 const CpSolverResponse& initial_solution,
double difficulty,
415 absl::BitGenRef random) {
416 std::vector<int> active_constraints;
419 ConstraintProto::CONSTRAINT_NOT_SET) {
422 active_constraints.push_back(
ct);
427 const int target_size = std::ceil(
difficulty * num_active_vars);
429 if (num_constraints == 0 || target_size == num_active_vars) {
434 std::shuffle(active_constraints.begin(), active_constraints.end(), random);
436 std::vector<bool> visited_variables_set(num_model_vars,
false);
437 std::vector<int> relaxed_variables;
439 for (
const int constraint_index : active_constraints) {
440 CHECK_LT(constraint_index, num_constraints);
442 if (visited_variables_set[
var])
continue;
443 visited_variables_set[
var] =
true;
445 relaxed_variables.push_back(
var);
446 if (relaxed_variables.size() == target_size)
break;
449 if (relaxed_variables.size() == target_size)
break;
455 const CpSolverResponse& initial_solution,
double difficulty,
456 absl::BitGenRef random) {
459 const int target_size = std::ceil(
difficulty * num_active_vars);
460 if (target_size == num_active_vars) {
465 std::vector<bool> visited_variables_set(num_model_vars,
false);
466 std::vector<int> relaxed_variables;
467 std::vector<int> visited_variables;
469 const int first_var =
471 visited_variables_set[first_var] =
true;
472 visited_variables.push_back(first_var);
473 relaxed_variables.push_back(first_var);
475 std::vector<int> random_variables;
476 for (
int i = 0; i < visited_variables.size(); ++i) {
477 random_variables.clear();
482 if (visited_variables_set[
var])
continue;
483 visited_variables_set[
var] =
true;
484 random_variables.push_back(
var);
488 std::shuffle(random_variables.begin(), random_variables.end(), random);
489 for (
const int var : random_variables) {
490 if (relaxed_variables.size() < target_size) {
491 visited_variables.push_back(
var);
493 relaxed_variables.push_back(
var);
499 if (relaxed_variables.size() >= target_size)
break;
506 const CpSolverResponse& initial_solution,
double difficulty,
507 absl::BitGenRef random) {
510 const int target_size = std::ceil(
difficulty * num_active_vars);
512 if (num_constraints == 0 || target_size == num_active_vars) {
517 std::vector<bool> visited_variables_set(num_model_vars,
false);
518 std::vector<int> relaxed_variables;
519 std::vector<bool> added_constraints(num_constraints,
false);
520 std::vector<int> next_constraints;
523 next_constraints.push_back(absl::Uniform<int>(random, 0, num_constraints));
524 added_constraints[next_constraints.back()] =
true;
526 std::vector<int> random_variables;
527 while (relaxed_variables.size() < target_size) {
529 if (next_constraints.empty())
break;
532 const int i = absl::Uniform<int>(random, 0, next_constraints.size());
533 const int constraint_index = next_constraints[i];
534 std::swap(next_constraints[i], next_constraints.back());
535 next_constraints.pop_back();
539 CHECK_LT(constraint_index, num_constraints);
541 std::shuffle(random_variables.begin(), random_variables.end(), random);
542 for (
const int var : random_variables) {
543 if (visited_variables_set[
var])
continue;
544 visited_variables_set[
var] =
true;
546 relaxed_variables.push_back(
var);
548 if (relaxed_variables.size() == target_size)
break;
551 if (added_constraints[
ct])
continue;
552 added_constraints[
ct] =
true;
553 next_constraints.push_back(
ct);
561 const absl::Span<const int> intervals_to_relax,
562 const CpSolverResponse& initial_solution,
566 (intervals_to_relax.size() <
570 std::set<int> ignored_intervals(intervals_to_relax.begin(),
571 intervals_to_relax.end());
575 if (ignored_intervals.count(i))
continue;
577 const ConstraintProto& interval_ct = neighborhood.
cp_model.constraints(i);
578 if (interval_ct.enforcement_literal().empty())
continue;
580 CHECK_EQ(interval_ct.enforcement_literal().size(), 1);
581 const int enforcement_ref = interval_ct.enforcement_literal(0);
582 const int enforcement_var =
PositiveRef(enforcement_ref);
583 const int value = initial_solution.solution(enforcement_var);
591 ignored_intervals.insert(i);
596 neighborhood.
cp_model.mutable_variables(enforcement_var)->clear_domain();
597 neighborhood.
cp_model.mutable_variables(enforcement_var)->add_domain(
value);
598 neighborhood.
cp_model.mutable_variables(enforcement_var)->add_domain(
value);
604 std::vector<std::pair<int64, int>> start_interval_pairs;
606 neighborhood.
cp_model.constraints(c).no_overlap().intervals()) {
607 if (ignored_intervals.count(i))
continue;
608 const ConstraintProto& interval_ct = neighborhood.
cp_model.constraints(i);
611 const int size_var = interval_ct.interval().size();
612 if (initial_solution.solution(size_var) == 0)
continue;
614 const int start_var = interval_ct.interval().start();
615 const int64 start_value = initial_solution.solution(start_var);
616 start_interval_pairs.push_back({start_value, i});
618 std::sort(start_interval_pairs.begin(), start_interval_pairs.end());
621 for (
int i = 0; i + 1 < start_interval_pairs.size(); ++i) {
622 const int before_var =
623 neighborhood.
cp_model.constraints(start_interval_pairs[i].second)
626 const int after_var =
627 neighborhood.
cp_model.constraints(start_interval_pairs[i + 1].second)
630 CHECK_LE(initial_solution.solution(before_var),
631 initial_solution.solution(after_var));
633 LinearConstraintProto* linear =
634 neighborhood.
cp_model.add_constraints()->mutable_linear();
636 linear->add_domain(0);
637 linear->add_vars(before_var);
638 linear->add_coeffs(1);
639 linear->add_vars(after_var);
640 linear->add_coeffs(-1);
647 neighborhood.
cp_model.clear_solution_hint();
649 neighborhood.
cp_model.mutable_solution_hint()->add_vars(
var);
650 neighborhood.
cp_model.mutable_solution_hint()->add_values(
651 initial_solution.solution(
var));
659 const CpSolverResponse& initial_solution,
double difficulty,
660 absl::BitGenRef random) {
661 std::vector<int> intervals_to_relax =
663 GetRandomSubset(
difficulty, &intervals_to_relax, random);
670 const CpSolverResponse& initial_solution,
double difficulty,
671 absl::BitGenRef random) {
672 std::vector<std::pair<int64, int>> start_interval_pairs;
675 const int start_var = interval_ct.interval().start();
676 const int64 start_value = initial_solution.solution(start_var);
677 start_interval_pairs.push_back({start_value, i});
679 std::sort(start_interval_pairs.begin(), start_interval_pairs.end());
680 const int relaxed_size = std::floor(
difficulty * start_interval_pairs.size());
682 std::uniform_int_distribution<int> random_var(
683 0, start_interval_pairs.size() - relaxed_size - 1);
684 const int random_start_index = random_var(random);
685 std::vector<int> intervals_to_relax;
688 for (
int i = random_start_index; i < relaxed_size; ++i) {
689 intervals_to_relax.push_back(start_interval_pairs[i].second);
696 if (incomplete_solutions_ !=
nullptr) {
700 if (response_manager_ !=
nullptr) {
708 if (lp_solutions_ !=
nullptr && lp_solutions_->
NumSolutions() > 0) {
712 if (relaxation_solutions_ !=
nullptr &&
720 const CpSolverResponse& initial_solution,
double difficulty,
721 absl::BitGenRef random) {
725 const bool lp_solution_available =
726 (lp_solutions_ !=
nullptr && lp_solutions_->
NumSolutions() > 0);
728 const bool relaxation_solution_available =
729 (relaxation_solutions_ !=
nullptr &&
732 const bool incomplete_solution_available =
733 (incomplete_solutions_ !=
nullptr &&
736 if (!lp_solution_available && !relaxation_solution_available &&
737 !incomplete_solution_available) {
745 std::bernoulli_distribution random_bool(0.5);
746 const bool use_lp_relaxation =
747 (lp_solution_available && relaxation_solution_available)
748 ? random_bool(random)
749 : lp_solution_available;
750 if (use_lp_relaxation) {
753 nullptr, lp_solutions_,
754 incomplete_solutions_, random);
756 incomplete_solution_available ?
"incomplete" :
"lp";
758 CHECK(relaxation_solution_available || incomplete_solution_available);
760 response_manager_, relaxation_solutions_,
761 nullptr, incomplete_solutions_, random);
763 incomplete_solution_available ?
"incomplete" :
"relaxation";
772 for (
const std::pair</*model_var*/ int, /*value*/ int64> fixed_var :
774 const int var = fixed_var.first;
776 if (
var >= neighborhood.
cp_model.variables_size())
continue;
786 neighborhood.
cp_model.mutable_variables(
var)->clear_domain();
792 for (
const std::pair<
int, std::pair<int64, int64>>
794 const int var = reduced_var.first;
795 const int64 lb = reduced_var.second.first;
796 const int64 ub = reduced_var.second.second;
797 if (
var >= neighborhood.
cp_model.variables_size())
continue;
813 const CpSolverResponse& initial_solution,
double difficulty,
814 absl::BitGenRef random) {
815 std::vector<int> removable_constraints;
817 removable_constraints.reserve(num_constraints);
818 for (
int c = 0; c < num_constraints; ++c) {
822 ConstraintProto::kInterval) {
825 removable_constraints.push_back(c);
828 const int target_size =
829 std::round((1.0 -
difficulty) * removable_constraints.size());
831 const int random_start_index =
832 absl::Uniform<int>(random, 0, removable_constraints.size());
833 std::vector<int> removed_constraints;
834 removed_constraints.reserve(target_size);
835 int c = random_start_index;
836 while (removed_constraints.size() < target_size) {
837 removed_constraints.push_back(removable_constraints[c]);
839 if (c == removable_constraints.size()) {
851 std::vector<int> removable_constraints;
853 constraint_weights_.reserve(num_constraints);
855 for (
int c = 0; c < num_constraints; ++c) {
857 case ConstraintProto::kCumulative:
858 case ConstraintProto::kAllDiff:
859 case ConstraintProto::kElement:
860 case ConstraintProto::kRoutes:
861 case ConstraintProto::kCircuit:
862 constraint_weights_.push_back(3.0);
863 num_removable_constraints_++;
865 case ConstraintProto::kBoolOr:
866 case ConstraintProto::kBoolAnd:
867 case ConstraintProto::kBoolXor:
868 case ConstraintProto::kIntProd:
869 case ConstraintProto::kIntDiv:
870 case ConstraintProto::kIntMod:
871 case ConstraintProto::kIntMax:
872 case ConstraintProto::kLinMax:
873 case ConstraintProto::kIntMin:
874 case ConstraintProto::kLinMin:
875 case ConstraintProto::kNoOverlap:
876 case ConstraintProto::kNoOverlap2D:
877 constraint_weights_.push_back(2.0);
878 num_removable_constraints_++;
880 case ConstraintProto::kLinear:
881 case ConstraintProto::kTable:
882 case ConstraintProto::kAutomaton:
883 case ConstraintProto::kInverse:
884 case ConstraintProto::kReservoir:
885 case ConstraintProto::kAtMostOne:
886 case ConstraintProto::kExactlyOne:
887 constraint_weights_.push_back(1.0);
888 num_removable_constraints_++;
890 case ConstraintProto::CONSTRAINT_NOT_SET:
891 case ConstraintProto::kInterval:
894 constraint_weights_.push_back(0.0);
900void WeightedRandomRelaxationNeighborhoodGenerator::
901 AdditionalProcessingOnSynchronize(
const SolveData& solve_data) {
902 const IntegerValue best_objective_improvement =
903 solve_data.new_objective_bound - solve_data.initial_best_objective_bound;
905 const std::vector<int>& removed_constraints =
906 removed_constraints_[solve_data.neighborhood_id];
920 if (best_objective_improvement > 0) {
922 for (
int c : removed_constraints) {
923 if (constraint_weights_[c] <= 90.0) {
924 constraint_weights_[c] += 10.0;
926 constraint_weights_[c] = 100.0;
929 }
else if (solve_data.status == CpSolverStatus::OPTIMAL &&
930 best_objective_improvement < 0) {
932 for (
int c : removed_constraints) {
933 if (constraint_weights_[c] > 0.5) {
934 constraint_weights_[c] -= 0.5;
938 removed_constraints_.erase(solve_data.neighborhood_id);
942 const CpSolverResponse& initial_solution,
double difficulty,
943 absl::BitGenRef random) {
944 const int target_size =
945 std::round((1.0 -
difficulty) * num_removable_constraints_);
947 std::vector<int> removed_constraints;
952 std::vector<std::pair<double, int>> constraint_removal_scores;
953 std::uniform_real_distribution<double> random_var(0.0, 1.0);
954 for (
int c = 0; c < constraint_weights_.size(); ++c) {
955 if (constraint_weights_[c] <= 0)
continue;
956 const double u = random_var(random);
957 const double score = std::pow(u, (1 / constraint_weights_[c]));
958 constraint_removal_scores.push_back({score, c});
960 std::sort(constraint_removal_scores.rbegin(),
961 constraint_removal_scores.rend());
962 for (
int i = 0; i < target_size; ++i) {
963 removed_constraints.push_back(constraint_removal_scores[i].second);
967 absl::MutexLock mutex_lock(&
mutex_);
968 result.
id = next_available_id_;
969 next_available_id_++;
970 removed_constraints_.insert({result.
id, removed_constraints});
#define CHECK_LT(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define CHECK_GT(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK(condition)
#define CHECK_LE(val1, val2)
#define VLOG(verboselevel)
void Update(int num_decreases, int num_increases)
We call domain any subset of Int64 = [kint64min, kint64max].
Domain IntersectionWith(const Domain &domain) const
Returns the intersection of D and domain.
bool IsEmpty() const
Returns true if this is the empty set.
bool Contains(int64 value) const
Returns true iff value is in Domain.
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
NeighborhoodGeneratorHelper(CpModelProto const *model_proto, SatParameters const *parameters, SharedResponseManager *shared_response, SharedTimeLimit *shared_time_limit=nullptr, SharedBoundsManager *shared_bounds=nullptr)
Neighborhood FullNeighborhood() const
Neighborhood FixAllVariables(const CpSolverResponse &initial_solution) const
bool IsActive(int var) const
const CpModelProto & ModelProto() const
Neighborhood FixGivenVariables(const CpSolverResponse &initial_solution, const std::vector< int > &variables_to_fix) const
const absl::Span< const int > TypeToConstraints(ConstraintProto::ConstraintCase type) const
const std::vector< int > & ActiveVariables() const
Neighborhood RelaxGivenVariables(const CpSolverResponse &initial_solution, const std::vector< int > &relaxed_variables) const
std::vector< int > GetActiveIntervals(const CpSolverResponse &initial_solution) const
const SharedResponseManager & shared_response() const
const std::vector< std::vector< int > > & ConstraintToVar() const
Neighborhood RemoveMarkedConstraints(const std::vector< int > &constraints_to_remove) const
const std::vector< std::vector< int > > & VarToConstraint() const
void Synchronize() override
virtual bool IsRelaxationGenerator() const
virtual bool ReadyToGenerate() const
double difficulty() const
double GetUCBScore(int64 total_num_calls) const
virtual void AdditionalProcessingOnSynchronize(const SolveData &solve_data)
const NeighborhoodGeneratorHelper & helper_
bool ReadyToGenerate() 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
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
void GetChangedBounds(int id, std::vector< int > *variables, std::vector< int64 > *new_lower_bounds, std::vector< int64 > *new_upper_bounds)
bool HasNewSolution() const
const SharedSolutionRepository< int64 > & SolutionsRepository() const
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
WeightedRandomRelaxationNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
CpModelProto const * model_proto
static const int64 kint64min
std::vector< int > UsedVariables(const ConstraintProto &ct)
std::vector< int > UsedIntervals(const ConstraintProto &ct)
Domain ReadDomainFromProto(const ProtoWithDomain &proto)
Neighborhood GenerateSchedulingNeighborhoodForRelaxation(const absl::Span< const int > intervals_to_relax, const CpSolverResponse &initial_solution, const NeighborhoodGeneratorHelper &helper)
bool RefIsPositive(int ref)
RINSNeighborhood GetRINSNeighborhood(const SharedResponseManager *response_manager, const SharedRelaxationSolutionRepository *relaxation_solutions, const SharedLPSolutionRepository *lp_solutions, SharedIncompleteSolutionManager *incomplete_solutions, absl::BitGenRef random)
void FillDomainInProto(const Domain &domain, ProtoWithDomain *proto)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapSub(int64 x, int64 y)
std::vector< std::pair< int, std::pair< int64, int64 > > > reduced_domain_vars
std::vector< std::pair< int, int64 > > fixed_vars
#define VLOG_IS_ON(verboselevel)