29#include "absl/algorithm/container.h"
30#include "absl/base/log_severity.h"
31#include "absl/container/flat_hash_map.h"
32#include "absl/container/flat_hash_set.h"
33#include "absl/flags/flag.h"
34#include "absl/log/check.h"
35#include "absl/log/log.h"
36#include "absl/log/vlog_is_on.h"
37#include "absl/meta/type_traits.h"
38#include "absl/random/bit_gen_ref.h"
39#include "absl/random/distributions.h"
40#include "absl/strings/str_cat.h"
41#include "absl/strings/str_join.h"
42#include "absl/synchronization/mutex.h"
43#include "absl/types/span.h"
44#include "google/protobuf/arena.h"
78 parameters_(*parameters),
79 model_proto_(*model_proto),
80 shared_bounds_(shared_bounds),
81 global_time_limit_(global_time_limit),
85 model_proto_.variables_size(),
87 local_arena_ = std::make_unique<google::protobuf::Arena>(
88 local_arena_storage_.data(), local_arena_storage_.size());
89 simplified_model_proto_ =
90 google::protobuf::Arena::Create<CpModelProto>(local_arena_.get());
92 CHECK(shared_response_ !=
nullptr);
93 if (shared_bounds_ !=
nullptr) {
94 shared_bounds_id_ = shared_bounds_->RegisterNewId();
96 *model_proto_with_only_variables_.mutable_variables() =
97 model_proto_.variables();
98 InitializeHelperData();
99 RecomputeHelperData();
104 if (shared_response_->ProblemIsSolved() ||
105 global_time_limit_->LimitReached()) {
108 if (shared_bounds_ !=
nullptr) {
109 std::vector<int> model_variables;
110 std::vector<int64_t> new_lower_bounds;
111 std::vector<int64_t> new_upper_bounds;
112 shared_bounds_->GetChangedBounds(shared_bounds_id_, &model_variables,
113 &new_lower_bounds, &new_upper_bounds);
115 bool new_variables_have_been_fixed =
false;
117 if (!model_variables.empty()) {
118 absl::MutexLock domain_lock(&domain_mutex_);
120 for (
int i = 0;
i < model_variables.size(); ++
i) {
121 const int var = model_variables[
i];
122 const int64_t new_lb = new_lower_bounds[
i];
123 const int64_t new_ub = new_upper_bounds[
i];
126 model_proto_with_only_variables_.variables(var).domain();
127 const int64_t old_lb = domain.Get(0);
128 const int64_t old_ub = domain.Get(domain.size() - 1);
129 VLOG(3) <<
"Variable: " << var <<
" old domain: [" << old_lb <<
", "
130 << old_ub <<
"] new domain: [" << new_lb <<
", " << new_ub
134 model_proto_with_only_variables_.variables(var));
155 model_proto_with_only_variables_.mutable_variables(var));
156 new_variables_have_been_fixed |= new_domain.
IsFixed();
161 if (new_variables_have_been_fixed) {
162 RecomputeHelperData();
167bool NeighborhoodGeneratorHelper::ObjectiveDomainIsConstraining()
const {
171 int64_t min_activity = 0;
172 int64_t max_activity = 0;
173 const int num_terms = model_proto_.
objective().
vars().size();
174 for (
int i = 0;
i < num_terms; ++
i) {
177 const auto& var_domain =
178 model_proto_with_only_variables_.variables(var).domain();
179 const int64_t
v1 = coeff * var_domain[0];
180 const int64_t v2 = coeff * var_domain[var_domain.size() - 1];
181 min_activity += std::min(
v1, v2);
182 max_activity += std::max(
v1, v2);
186 const Domain inferred_domain =
187 Domain(min_activity, max_activity)
189 Domain(std::numeric_limits<int64_t>::min(), obj_domain.
Max()));
193void NeighborhoodGeneratorHelper::InitializeHelperData() {
194 type_to_constraints_.clear();
196 for (
int c = 0; c < num_constraints; ++c) {
198 if (
type >= type_to_constraints_.size()) {
199 type_to_constraints_.resize(
type + 1);
201 type_to_constraints_[
type].push_back(c);
204 const int num_variables = model_proto_.variables().size();
205 is_in_objective_.resize(num_variables,
false);
206 has_positive_objective_coefficient_.resize(num_variables,
false);
207 if (model_proto_.has_objective()) {
208 for (
int i = 0;
i < model_proto_.objective().vars_size(); ++
i) {
209 const int ref = model_proto_.objective().vars(
i);
210 const int64_t coeff = model_proto_.objective().coeffs(
i);
213 has_positive_objective_coefficient_[
PositiveRef(ref)] =
221void NeighborhoodGeneratorHelper::RecomputeHelperData() {
223 absl::ReaderMutexLock domain_lock(&domain_mutex_);
237 CpModelProto mapping_proto;
241 int64_t new_size = local_arena_->SpaceUsed();
242 new_size += new_size / 2;
243 simplified_model_proto_->Clear();
244 local_arena_.reset();
245 local_arena_storage_.resize(new_size);
246 local_arena_ = std::make_unique<google::protobuf::Arena>(
247 local_arena_storage_.data(), local_arena_storage_.size());
248 simplified_model_proto_ =
249 google::protobuf::Arena::Create<CpModelProto>(local_arena_.get());
250 *simplified_model_proto_->mutable_variables() =
251 model_proto_with_only_variables_.variables();
252 PresolveContext context(&local_model, simplified_model_proto_,
254 ModelCopy copier(&context);
258 copier.ImportAndSimplifyConstraints(model_proto_, {});
264 const auto& constraints = simplified_model_proto_->constraints();
265 constraint_to_var_.clear();
266 constraint_to_var_.reserve(constraints.size());
267 for (
int ct_index = 0; ct_index < constraints.size(); ++ct_index) {
279 if (IsConstant(var))
continue;
280 tmp_row_.push_back(var);
285 bool need_sort =
false;
286 for (
const int interval :
UsedIntervals(constraints[ct_index])) {
289 if (IsConstant(var))
continue;
290 tmp_row_.push_back(var);
296 if (tmp_row_.size() <= 1) {
304 constraint_to_var_.Add(tmp_row_);
309 var_to_constraint_.ResetFromTranspose(
311 model_proto_.variables().size());
315 active_variables_.clear();
316 const int num_variables = model_proto_.variables_size();
317 active_variables_set_.assign(num_variables,
false);
318 for (
int i = 0;
i < num_variables; ++
i) {
319 if (!IsConstant(
i)) {
320 active_variables_.push_back(
i);
321 active_variables_set_[
i] =
true;
325 active_objective_variables_.clear();
326 for (
const int var : model_proto_.objective().vars()) {
328 if (active_variables_set_[var]) {
329 active_objective_variables_.push_back(var);
335 DenseConnectedComponentsFinder union_find;
337 for (
int c = 0;
c < constraint_to_var_.size(); ++
c) {
338 const auto row = constraint_to_var_[
c];
339 if (row.size() <= 1)
continue;
340 for (
int i = 1;
i < row.size(); ++
i) {
347 if (ObjectiveDomainIsConstraining()) {
348 const auto& refs = model_proto_.objective().vars();
349 const int num_terms = refs.size();
350 for (
int i = 1;
i < num_terms; ++
i) {
361 var_to_component_index_.assign(num_variables, -1);
362 for (
int var = 0; var < num_variables; ++var) {
363 if (IsConstant(var))
continue;
364 const int root = union_find.
FindRoot(var);
365 DCHECK_LT(root, var_to_component_index_.size());
366 int& index = var_to_component_index_[root];
368 index = components_.size();
369 components_.push_back({});
371 var_to_component_index_[var] = index;
372 components_[index].push_back(var);
379 if (!shared_response_->LoggingIsEnabled())
return;
381 std::vector<int> component_sizes;
382 for (
const std::vector<int>& component : components_) {
383 component_sizes.push_back(component.size());
385 std::sort(component_sizes.begin(), component_sizes.end(),
386 std::greater<int>());
387 std::string compo_message;
388 if (component_sizes.size() > 1) {
389 if (component_sizes.size() <= 10) {
391 absl::StrCat(
" compo:", absl::StrJoin(component_sizes,
","));
393 component_sizes.resize(10);
395 absl::StrCat(
" compo:", absl::StrJoin(component_sizes,
","),
",...");
402 shared_response_->LogMessageWithThrottling(
403 "Model", absl::StrCat(
"var:", active_variables_.size(),
"/",
404 num_variables,
" constraints:",
405 simplified_model_proto_->constraints().size(),
"/",
406 model_proto_.constraints().size(), compo_message));
410 return active_variables_set_[var];
413bool NeighborhoodGeneratorHelper::IsConstant(
int var)
const {
414 const auto& var_proto = model_proto_with_only_variables_.variables(var);
415 return var_proto.domain_size() == 2 &&
416 var_proto.domain(0) == var_proto.domain(1);
424 absl::ReaderMutexLock lock(&domain_mutex_);
426 model_proto_with_only_variables_.variables();
437bool NeighborhoodGeneratorHelper::IntervalIsActive(
445 const int enforcement_var =
PositiveRef(enforcement_ref);
446 const int value = initial_solution.
solution(enforcement_var);
447 if (
RefIsPositive(enforcement_ref) == (value == 0))
return false;
451 if (!IsConstant(v))
return true;
454 if (!IsConstant(v))
return true;
457 if (!IsConstant(v))
return true;
463 absl::Span<const int> unfiltered_intervals,
465 std::vector<int> filtered_intervals;
466 filtered_intervals.reserve(unfiltered_intervals.size());
467 absl::ReaderMutexLock lock(&domain_mutex_);
468 for (
const int i : unfiltered_intervals) {
469 if (IntervalIsActive(
i, initial_solution)) filtered_intervals.push_back(
i);
471 return filtered_intervals;
480std::vector<NeighborhoodGeneratorHelper::ActiveRectangle>
483 const std::vector<int> active_intervals =
485 const absl::flat_hash_set<int> active_intervals_set(active_intervals.begin(),
486 active_intervals.end());
488 absl::flat_hash_map<std::pair<int, int>, std::vector<int>> active_rectangles;
491 model_proto_.constraints(ct_index).no_overlap_2d();
495 if (active_intervals_set.contains(x_i) ||
496 active_intervals_set.contains(y_i)) {
497 active_rectangles[{x_i, y_i}].push_back(ct_index);
502 std::vector<ActiveRectangle> results;
503 results.reserve(active_rectangles.size());
504 for (
const auto& [rectangle, no_overlap_2d_constraints] : active_rectangles) {
509 no_overlap_2d_constraints.end()};
514std::vector<std::vector<int>>
516 std::vector<std::vector<int>> intervals_in_constraints;
517 absl::flat_hash_set<std::vector<int>> added_intervals_sets;
518 const auto add_interval_list_only_once =
519 [&intervals_in_constraints,
520 &added_intervals_sets](
const auto& intervals) {
521 std::vector<int> candidate({intervals.begin(), intervals.end()});
523 if (added_intervals_sets.insert(candidate).second) {
524 intervals_in_constraints.push_back(candidate);
528 add_interval_list_only_once(
529 model_proto_.constraints(ct_index).no_overlap().intervals());
532 add_interval_list_only_once(
533 model_proto_.constraints(ct_index).cumulative().intervals());
536 add_interval_list_only_once(
537 model_proto_.constraints(ct_index).no_overlap_2d().x_intervals());
538 add_interval_list_only_once(
539 model_proto_.constraints(ct_index).no_overlap_2d().y_intervals());
541 return intervals_in_constraints;
548 int64_t result = expr.
offset();
555void RestrictAffineExpression(
const LinearExpressionProto& expr,
556 const Domain& restriction,
557 CpModelProto* mutable_proto) {
558 CHECK_LE(expr.vars().size(), 1);
559 if (expr.vars().empty())
return;
560 const Domain implied_domain = restriction.AdditionWith(
Domain(-expr.offset()))
561 .InverseMultiplicationBy(expr.coeffs(0));
565 if (!domain.IsEmpty()) {
570struct StartEndIndex {
573 int index_in_input_vector;
575 bool operator<(
const StartEndIndex& o)
const {
576 return std::tie(start, end, noise, index_in_input_vector) <
577 std::tie(o.start, o.end, o.noise, o.index_in_input_vector);
581struct TimePartition {
582 std::vector<int> indices_before_selected;
583 std::vector<int> selected_indices;
584 std::vector<int> indices_after_selected;
589TimePartition PartitionIndicesAroundRandomTimeWindow(
590 absl::Span<const int> intervals,
const CpModelProto& model_proto,
592 absl::BitGenRef random) {
593 std::vector<StartEndIndex> start_end_indices;
594 for (
int index = 0; index < intervals.size(); ++index) {
595 const int interval = intervals[index];
596 const ConstraintProto& interval_ct = model_proto.constraints(interval);
597 const int64_t start_value = GetLinearExpressionValue(
598 interval_ct.interval().start(), initial_solution);
599 const int64_t end_value = GetLinearExpressionValue(
600 interval_ct.interval().end(), initial_solution);
601 start_end_indices.push_back(
602 {start_value, end_value, index, absl::Uniform(random, 0., 1.0)});
605 if (start_end_indices.empty())
return {};
607 std::sort(start_end_indices.begin(), start_end_indices.end());
608 const int relaxed_size = std::floor(difficulty * start_end_indices.size());
610 std::uniform_int_distribution<int> random_var(
611 0, start_end_indices.size() - relaxed_size - 1);
614 const int random_start_index = random_var(random);
621 std::sort(start_end_indices.begin() + random_start_index,
622 start_end_indices.end(),
623 [](
const StartEndIndex& a,
const StartEndIndex&
b) {
624 return std::tie(a.end, a.noise, a.index_in_input_vector) <
625 std::tie(b.end, b.noise, b.index_in_input_vector);
627 TimePartition result;
629 for (;
i < random_start_index; ++
i) {
630 result.indices_before_selected.push_back(
631 start_end_indices[
i].index_in_input_vector);
633 for (;
i < random_start_index + relaxed_size; ++
i) {
634 result.selected_indices.push_back(
635 start_end_indices[
i].index_in_input_vector);
637 for (;
i < start_end_indices.size(); ++
i) {
638 result.indices_after_selected.push_back(
639 start_end_indices[
i].index_in_input_vector);
654 bool operator<(
const Demand& other)
const {
655 return std::tie(start, height, end) <
656 std::tie(other.start, other.height, other.end);
659 std::string DebugString()
const {
660 return absl::StrCat(
"{i=", interval_index,
" span=[", start,
",", end,
"]",
665void InsertPrecedencesFromSortedListOfNonOverlapingIntervals(
666 const std::vector<Demand>& demands,
667 absl::flat_hash_set<std::pair<int, int>>* precedences) {
668 for (
int i = 0;
i + 1 < demands.size(); ++
i) {
669 DCHECK_LE(demands[
i].
end, demands[
i + 1].start);
671 {demands[
i].interval_index, demands[
i + 1].interval_index});
677 if (interval_ct.enforcement_literal().size() != 1)
return true;
679 const int enforcement_ref = interval_ct.enforcement_literal(0);
680 const int enforcement_var =
PositiveRef(enforcement_ref);
681 const int64_t value = initial_solution.solution(enforcement_var);
685void InsertNoOverlapPrecedences(
686 const absl::flat_hash_set<int>& ignored_intervals,
688 int no_overlap_index,
689 absl::flat_hash_set<std::pair<int, int>>* precedences) {
690 std::vector<Demand> demands;
692 model_proto.constraints(no_overlap_index).no_overlap();
693 for (
const int interval_index : no_overlap.intervals()) {
694 if (ignored_intervals.contains(interval_index))
continue;
696 model_proto.constraints(interval_index);
697 if (!IsPresent(interval_ct, initial_solution))
continue;
699 const int64_t start_value = GetLinearExpressionValue(
700 interval_ct.interval().start(), initial_solution);
701 const int64_t end_value = GetLinearExpressionValue(
702 interval_ct.interval().end(), initial_solution);
703 DCHECK_LE(start_value, end_value);
704 demands.push_back({interval_index, start_value, end_value, 1});
709 std::sort(demands.begin(), demands.end());
710 InsertPrecedencesFromSortedListOfNonOverlapingIntervals(demands, precedences);
713void ProcessDemandListFromCumulativeConstraint(
714 const std::vector<Demand>& demands, int64_t capacity,
715 std::deque<std::pair<std::vector<Demand>, int64_t>>* to_process,
716 absl::BitGenRef random,
717 absl::flat_hash_set<std::pair<int, int>>* precedences) {
718 if (demands.size() <= 1)
return;
721 int64_t sum_of_min_two_capacities = 2;
723 int64_t min1 = std::numeric_limits<int64_t>::max();
724 int64_t min2 = std::numeric_limits<int64_t>::max();
725 for (
const Demand& demand : demands) {
726 if (demand.height <= min1) {
728 min1 = demand.height;
729 }
else if (demand.height < min2) {
730 min2 = demand.height;
733 sum_of_min_two_capacities = min1 + min2;
736 DCHECK_GT(sum_of_min_two_capacities, 1);
737 if (sum_of_min_two_capacities > capacity) {
738 InsertPrecedencesFromSortedListOfNonOverlapingIntervals(demands,
743 std::vector<int64_t> unique_starts;
744 for (
const Demand& demand : demands) {
745 DCHECK(unique_starts.empty() || demand.start >= unique_starts.back());
746 if (unique_starts.empty() || unique_starts.back() < demand.start) {
747 unique_starts.push_back(demand.start);
750 DCHECK(std::is_sorted(unique_starts.begin(), unique_starts.end()));
751 const int num_points = unique_starts.size();
754 const int64_t capacity1 = capacity / 2;
755 std::vector<int64_t> usage1(num_points);
756 std::vector<Demand> demands1;
758 const int64_t capacity2 = capacity - capacity1;
759 std::vector<int64_t> usage2(num_points);
760 std::vector<Demand> demands2;
763 for (
const Demand& d : demands) {
766 while (usage_index < num_points && unique_starts[usage_index] < d.start) {
769 DCHECK_LT(usage_index, num_points);
770 DCHECK_EQ(unique_starts[usage_index], d.start);
771 const int64_t slack1 = capacity1 - usage1[usage_index];
772 const int64_t slack2 = capacity2 - usage2[usage_index];
779 ? absl::Bernoulli(random, 0.5)
780 : (d.height <= std::min(slack1, slack2) ? slack2 < slack1
783 auto& selected_usage = prefer2 ? usage2 : usage1;
784 auto& residual_usage = prefer2 ? usage1 : usage2;
785 std::vector<Demand>& selected_demands = prefer2 ? demands2 : demands1;
786 std::vector<Demand>& residual_demands = prefer2 ? demands1 : demands2;
787 const int64_t selected_slack = prefer2 ? slack2 : slack1;
789 const int64_t assigned_to_selected = std::min(selected_slack, d.height);
790 DCHECK_GT(assigned_to_selected, 0);
791 for (
int i = usage_index;
i < num_points; ++
i) {
792 if (d.end <= unique_starts[
i])
break;
793 selected_usage[
i] += assigned_to_selected;
795 selected_demands.push_back(
796 {d.interval_index, d.start, d.end, assigned_to_selected});
798 if (d.height > selected_slack) {
799 const int64_t residual = d.height - selected_slack;
800 DCHECK_GT(residual, 0);
801 DCHECK_LE(residual, prefer2 ? slack1 : slack2);
802 for (
int i = usage_index;
i < num_points; ++
i) {
803 if (d.end <= unique_starts[
i])
break;
804 residual_usage[
i] += residual;
806 residual_demands.push_back({d.interval_index, d.start, d.end, residual});
810 if (demands1.size() > 1) {
811 to_process->emplace_back(std::move(demands1), capacity1);
813 if (demands2.size() > 1) {
814 to_process->emplace_back(std::move(demands2), capacity2);
818void InsertCumulativePrecedences(
819 const absl::flat_hash_set<int>& ignored_intervals,
821 int cumulative_index, absl::BitGenRef random,
822 absl::flat_hash_set<std::pair<int, int>>* precedences) {
824 model_proto.constraints(cumulative_index).cumulative();
826 std::vector<Demand> demands;
827 for (
int i = 0;
i < cumulative.intervals().size(); ++
i) {
828 const int interval_index = cumulative.intervals(
i);
829 if (ignored_intervals.contains(interval_index))
continue;
831 model_proto.constraints(interval_index);
832 if (!IsPresent(interval_ct, initial_solution))
continue;
834 const int64_t start_value = GetLinearExpressionValue(
835 interval_ct.interval().start(), initial_solution);
836 const int64_t end_value = GetLinearExpressionValue(
837 interval_ct.interval().end(), initial_solution);
838 const int64_t demand_value =
839 GetLinearExpressionValue(cumulative.demands(
i), initial_solution);
840 if (start_value == end_value || demand_value == 0)
continue;
842 demands.push_back({interval_index, start_value, end_value, demand_value});
844 std::sort(demands.begin(), demands.end());
846 const int64_t capacity_value =
847 GetLinearExpressionValue(cumulative.capacity(), initial_solution);
848 DCHECK_GT(capacity_value, 0);
851 std::deque<std::pair<std::vector<Demand>, int64_t>> to_process;
852 to_process.emplace_back(std::move(demands), capacity_value);
854 while (!to_process.empty()) {
855 auto& next_task = to_process.front();
856 ProcessDemandListFromCumulativeConstraint(next_task.first,
858 &to_process, random, precedences);
859 to_process.pop_front();
863struct IndexedRectangle {
867 bool operator<(
const IndexedRectangle& other)
const {
868 return std::tie(r.x_min, r.x_max) < std::tie(other.r.x_min, other.r.x_max);
872void InsertRectanglePredecences(
873 absl::Span<const IndexedRectangle> rectangles,
874 absl::flat_hash_set<std::pair<int, int>>* precedences) {
876 std::vector<IntegerValue> interesting_points;
877 for (
const IndexedRectangle& idx_r : rectangles) {
878 interesting_points.push_back(idx_r.r.y_max - 1);
881 std::vector<Demand> demands;
882 for (
const IntegerValue t : interesting_points) {
884 for (
const IndexedRectangle& idx_r : rectangles) {
885 if (idx_r.r.y_min > t || idx_r.r.y_max <= t)
continue;
886 demands.push_back({idx_r.interval_index, idx_r.r.x_min.value(),
887 idx_r.r.x_max.value(), 1});
889 std::sort(demands.begin(), demands.end());
890 InsertPrecedencesFromSortedListOfNonOverlapingIntervals(demands,
895void InsertNoOverlap2dPrecedences(
896 const absl::flat_hash_set<int>& ignored_intervals,
898 int no_overlap_2d_index,
899 absl::flat_hash_set<std::pair<int, int>>* precedences) {
900 std::vector<Demand> demands;
902 model_proto.constraints(no_overlap_2d_index).no_overlap_2d();
903 std::vector<IndexedRectangle> x_main;
904 std::vector<IndexedRectangle> y_main;
905 for (
int i = 0;
i < no_overlap_2d.x_intervals_size(); ++
i) {
907 const int x_interval_index = no_overlap_2d.x_intervals(
i);
908 if (ignored_intervals.contains(x_interval_index))
continue;
910 model_proto.constraints(x_interval_index);
911 if (!IsPresent(x_interval_ct, initial_solution))
continue;
913 const int y_interval_index = no_overlap_2d.y_intervals(
i);
914 if (ignored_intervals.contains(y_interval_index))
continue;
916 model_proto.constraints(y_interval_index);
917 if (!IsPresent(y_interval_ct, initial_solution))
continue;
919 const int64_t x_start_value = GetLinearExpressionValue(
920 x_interval_ct.interval().start(), initial_solution);
921 const int64_t x_end_value = GetLinearExpressionValue(
922 x_interval_ct.interval().end(), initial_solution);
923 const int64_t y_start_value = GetLinearExpressionValue(
924 y_interval_ct.interval().start(), initial_solution);
925 const int64_t y_end_value = GetLinearExpressionValue(
926 y_interval_ct.interval().end(), initial_solution);
929 if (x_start_value == x_end_value || y_start_value == y_end_value)
continue;
931 x_main.push_back({.interval_index = x_interval_index,
932 .r = {.x_min = x_start_value,
933 .x_max = x_end_value,
934 .y_min = y_start_value,
935 .y_max = y_end_value}});
936 y_main.push_back({.interval_index = y_interval_index,
937 .r = {.x_min = y_start_value,
938 .x_max = y_end_value,
939 .y_min = x_start_value,
940 .y_max = x_end_value}});
943 if (x_main.empty() || y_main.empty())
return;
945 std::sort(x_main.begin(), x_main.end());
946 InsertRectanglePredecences(x_main, precedences);
947 std::sort(y_main.begin(), y_main.end());
948 InsertRectanglePredecences(y_main, precedences);
956std::vector<std::pair<int, int>>
958 const absl::flat_hash_set<int>& ignored_intervals,
960 absl::flat_hash_set<std::pair<int, int>> precedences;
962 InsertNoOverlapPrecedences(ignored_intervals, initial_solution,
966 InsertCumulativePrecedences(ignored_intervals, initial_solution,
970 InsertNoOverlap2dPrecedences(ignored_intervals, initial_solution,
975 std::vector<std::pair<int, int>> result(precedences.begin(),
977 std::sort(result.begin(), result.end());
981std::vector<std::vector<int>>
984 struct HeadAndArcBooleanVariable {
989 std::vector<std::vector<int>> result;
990 absl::flat_hash_map<int, HeadAndArcBooleanVariable>
991 tail_to_head_and_arc_bool_var;
997 int min_node = std::numeric_limits<int>::max();
998 tail_to_head_and_arc_bool_var.clear();
1001 const int head = ct.
heads(
i);
1002 const int tail = ct.
tails(
i);
1004 const int64_t value = initial_solution.
solution(bool_var);
1008 if (head == tail)
continue;
1009 tail_to_head_and_arc_bool_var[tail] = {head, bool_var};
1010 min_node = std::min(tail, min_node);
1012 if (tail_to_head_and_arc_bool_var.empty())
continue;
1015 int current_node = min_node;
1016 std::vector<int> path;
1018 auto it = tail_to_head_and_arc_bool_var.find(current_node);
1019 CHECK(it != tail_to_head_and_arc_bool_var.end());
1020 current_node = it->second.head;
1021 path.push_back(it->second.bool_var);
1022 }
while (current_node != min_node);
1023 result.push_back(std::move(path));
1026 std::vector<HeadAndArcBooleanVariable> route_starts;
1029 tail_to_head_and_arc_bool_var.clear();
1030 route_starts.clear();
1035 const int head = ct.
heads(
i);
1036 const int tail = ct.
tails(
i);
1038 const int64_t value = initial_solution.
solution(bool_var);
1042 if (head == tail)
continue;
1044 route_starts.push_back({head, bool_var});
1046 tail_to_head_and_arc_bool_var[tail] = {head, bool_var};
1051 for (
const HeadAndArcBooleanVariable& head_var : route_starts) {
1052 std::vector<int> path;
1053 int current_node = head_var.head;
1054 path.push_back(head_var.bool_var);
1056 auto it = tail_to_head_and_arc_bool_var.find(current_node);
1057 CHECK(it != tail_to_head_and_arc_bool_var.end());
1058 current_node = it->second.head;
1059 path.push_back(it->second.bool_var);
1060 }
while (current_node != 0);
1061 result.push_back(std::move(path));
1071 const int num_variables = variables_to_fix.
size();
1077 const int unique_objective_variable =
1078 model_proto_.has_objective() && model_proto_.objective().vars_size() == 1
1079 ? model_proto_.objective().vars(0)
1085 absl::ReaderMutexLock domain_lock(&domain_mutex_);
1086 for (
int i = 0;
i < num_variables; ++
i) {
1088 model_proto_with_only_variables_.variables(
i);
1094 if (variables_to_fix[
i] &&
i != unique_objective_variable) {
1099 const int64_t base_value = base_solution.
solution(
i);
1108 int64_t closest_value = domain.
Min();
1109 int64_t closest_dist = std::abs(closest_value - base_value);
1111 for (
const int64_t value : {interval.start, interval.end}) {
1112 const int64_t dist = std::abs(value - base_value);
1113 if (dist < closest_dist) {
1114 closest_value = value;
1115 closest_dist = dist;
1132 std::vector<int> count(components_.size(), 0);
1134 for (
int var = 0; var < num_variables; ++var) {
1136 if (domain.size() != 2 || domain[0] != domain[1]) {
1138 if (is_in_objective_[var]) {
1141 const int c = var_to_component_index_[var];
1142 if (c != -1) count[c]++;
1146 for (
int i = 0;
i < components_.size(); ++
i) {
1147 if (count[
i] == components_[
i].size()) {
1150 components_[
i].begin(), components_[
i].end());
1160 if (model_proto_.has_objective() &&
1161 (model_proto_.objective().domain().size() != 2 ||
1162 shared_response_->GetInnerObjectiveLowerBound() <
1163 model_proto_.objective().domain(0))) {
1167 const int num_relaxed = num_variables - num_fixed;
1182 return neighborhood;
1189 const auto is_fixed = [model_proto](
int var) {
1195 if (is_fixed(var))
continue;
1205 absl::Span<const int> relaxed_variables)
const {
1209 for (
const int i : active_variables_) {
1210 fixed_variables.
Set(
i);
1213 for (
const int var : relaxed_variables) fixed_variables.
Clear(var);
1222 for (
const int i : active_variables_) {
1223 fixed_variables.
Set(
i);
1232 absl::MutexLock domain_lock(&domain_mutex_);
1234 model_proto_with_only_variables_.variables();
1236 return updated_model;
1240 return (
helper_.shared_response().SolutionsRepository().NumSolutions() > 0);
1245 DCHECK_GE(total_num_calls, num_calls_);
1246 if (num_calls_ <= 10)
return std::numeric_limits<double>::infinity();
1247 return current_average_ + sqrt((2 * log(total_num_calls)) / num_calls_);
1255 std::sort(solve_data_.begin(), solve_data_.end());
1258 int num_fully_solved_in_batch = 0;
1259 int num_not_fully_solved_in_batch = 0;
1261 tmp_dtimes_.clear();
1262 for (
const SolveData& data : solve_data_) {
1270 ++num_fully_solved_calls_;
1271 ++num_fully_solved_in_batch;
1273 ++num_not_fully_solved_in_batch;
1282 const IntegerValue best_objective_improvement = IntegerValue(
CapSub(
1283 data.initial_best_objective.value(), data.new_objective.value()));
1284 if (best_objective_improvement > 0) {
1285 num_consecutive_non_improving_calls_ = 0;
1286 next_time_limit_bump_ = 50;
1288 ++num_consecutive_non_improving_calls_;
1292 if (data.base_objective > data.new_objective) {
1293 ++num_improving_calls_;
1298 const double gain_per_time_unit =
1299 std::max(0.0,
static_cast<double>(best_objective_improvement.value())) /
1300 (1.0 + data.deterministic_time);
1301 if (num_calls_ <= 100) {
1302 current_average_ += (gain_per_time_unit - current_average_) / num_calls_;
1304 current_average_ = 0.9 * current_average_ + 0.1 * gain_per_time_unit;
1307 tmp_dtimes_.push_back(data.deterministic_time);
1311 difficulty_.Update(num_not_fully_solved_in_batch,
1312 num_fully_solved_in_batch);
1320 if (num_consecutive_non_improving_calls_ > next_time_limit_bump_) {
1321 next_time_limit_bump_ = num_consecutive_non_improving_calls_ + 50;
1329 solve_data_.clear();
1336 std::vector<int> result;
1337 absl::ReaderMutexLock lock(&domain_mutex_);
1338 for (
const int var : active_objective_variables_) {
1339 const auto& domain =
1340 model_proto_with_only_variables_.variables(var).domain();
1341 bool at_best_value =
false;
1342 if (has_positive_objective_coefficient_[var]) {
1343 at_best_value = initial_solution.
solution(var) == domain[0];
1346 initial_solution.
solution(var) == domain[domain.size() - 1];
1348 if (!at_best_value) result.push_back(var);
1356void GetRandomSubset(
double relative_size, std::vector<T>*
base,
1357 absl::BitGenRef random) {
1358 if (
base->empty())
return;
1362 std::shuffle(
base->begin(),
base->end(), random);
1363 const int target_size = std::round(relative_size *
base->size());
1364 base->resize(target_size);
1371 absl::BitGenRef random) {
1372 std::vector<int> fixed_variables =
helper_.ActiveVariables();
1373 GetRandomSubset(1.0 - data.
difficulty, &fixed_variables, random);
1376 for (
const int var : fixed_variables) to_fix.
Set(var);
1377 return helper_.FixGivenVariables(initial_solution, to_fix);
1382 absl::BitGenRef random) {
1384 return helper_.FullNeighborhood();
1387 std::vector<int> relaxed_variables;
1389 absl::ReaderMutexLock graph_lock(&
helper_.graph_mutex_);
1390 const int num_active_constraints =
helper_.ConstraintToVar().size();
1391 std::vector<int> active_constraints(num_active_constraints);
1392 for (
int c = 0; c < num_active_constraints; ++c) {
1393 active_constraints[c] = c;
1395 std::shuffle(active_constraints.begin(), active_constraints.end(), random);
1397 const int num_model_vars =
helper_.ModelProto().variables_size();
1398 std::vector<bool> visited_variables_set(num_model_vars,
false);
1400 const int num_active_vars =
1401 helper_.ActiveVariablesWhileHoldingLock().size();
1402 const int target_size = std::ceil(data.
difficulty * num_active_vars);
1403 if (target_size == num_active_vars)
return helper_.FullNeighborhood();
1406 for (
const int constraint_index : active_constraints) {
1409 for (
const int var :
helper_.ConstraintToVar()[constraint_index]) {
1410 if (visited_variables_set[var])
continue;
1411 visited_variables_set[var] =
true;
1413 relaxed_variables.push_back(var);
1414 if (relaxed_variables.size() >= target_size)
break;
1417 if (relaxed_variables.size() >= target_size)
break;
1421 return helper_.RelaxGivenVariables(initial_solution, relaxed_variables);
1428 absl::BitGenRef random) {
1429 const int num_model_vars =
helper_.ModelProto().variables_size();
1430 std::vector<bool> visited_variables_set(num_model_vars,
false);
1431 std::vector<int> relaxed_variables;
1432 std::vector<int> visited_variables;
1435 const int num_model_constraints =
helper_.ModelProto().constraints_size();
1436 std::vector<bool> scanned_constraints(num_model_constraints,
false);
1438 std::vector<int> random_variables;
1440 absl::ReaderMutexLock graph_lock(&
helper_.graph_mutex_);
1442 std::vector<int> initial_vars =
1443 helper_.ImprovableObjectiveVariablesWhileHoldingLock(initial_solution);
1444 if (initial_vars.empty()) {
1445 initial_vars =
helper_.ActiveVariablesWhileHoldingLock();
1449 const int num_active_vars =
1450 helper_.ActiveVariablesWhileHoldingLock().size();
1451 const int target_size = std::ceil(data.
difficulty * num_active_vars);
1452 if (target_size == num_active_vars)
return helper_.FullNeighborhood();
1454 const int first_var =
1455 initial_vars[absl::Uniform<int>(random, 0, initial_vars.size())];
1456 visited_variables_set[first_var] =
true;
1457 visited_variables.push_back(first_var);
1458 relaxed_variables.push_back(first_var);
1460 for (
int i = 0;
i < visited_variables.size(); ++
i) {
1461 random_variables.clear();
1464 for (
const int ct :
helper_.VarToConstraint()[visited_variables[
i]]) {
1465 if (scanned_constraints[ct])
continue;
1466 scanned_constraints[ct] =
true;
1467 for (
const int var :
helper_.ConstraintToVar()[ct]) {
1468 if (visited_variables_set[var])
continue;
1469 visited_variables_set[var] =
true;
1470 random_variables.push_back(var);
1475 std::shuffle(random_variables.begin(), random_variables.end(), random);
1476 for (
const int var : random_variables) {
1477 if (relaxed_variables.size() < target_size) {
1478 visited_variables.push_back(var);
1480 relaxed_variables.push_back(var);
1486 if (relaxed_variables.size() >= target_size)
break;
1490 return helper_.RelaxGivenVariables(initial_solution, relaxed_variables);
1497 absl::BitGenRef random) {
1498 const int num_model_vars =
helper_.ModelProto().variables_size();
1499 if (num_model_vars == 0)
return helper_.NoNeighborhood();
1507 int num_active_vars = 0;
1508 std::vector<int> active_objective_vars;
1510 absl::ReaderMutexLock graph_lock(&
helper_.graph_mutex_);
1511 num_active_vars =
helper_.ActiveVariablesWhileHoldingLock().size();
1512 active_objective_vars =
1513 helper_.ImprovableObjectiveVariablesWhileHoldingLock(initial_solution);
1514 constraints_to_vars =
helper_.ConstraintToVar();
1515 vars_to_constraints =
helper_.VarToConstraint();
1518 const int target_size = std::ceil(data.
difficulty * num_active_vars);
1519 if (target_size == 0)
return helper_.NoNeighborhood();
1522 const int num_objective_variables = active_objective_vars.size();
1523 if (num_objective_variables == 0)
return helper_.NoNeighborhood();
1524 const int first_var = active_objective_vars[absl::Uniform<int>(
1525 random, 0, num_objective_variables)];
1527 std::vector<bool> relaxed_variables_set(num_model_vars,
false);
1528 std::vector<int> relaxed_variables;
1530 std::vector<int> active_vars;
1532 relaxed_variables_set[first_var] =
true;
1533 relaxed_variables.push_back(first_var);
1534 active_vars.push_back(first_var);
1536 while (relaxed_variables.size() < target_size) {
1537 if (active_vars.empty())
break;
1539 const int tail_index = absl::Uniform<int>(random, 0, active_vars.size());
1540 const int tail_var = active_vars[tail_index];
1541 int head_var = tail_var;
1542 while (!vars_to_constraints[tail_var].empty() && head_var == tail_var) {
1543 const auto cts = vars_to_constraints[tail_var];
1544 const int pos_ct = absl::Uniform<int>(random, 0, cts.size());
1545 const int ct = cts[pos_ct];
1546 while (!constraints_to_vars[ct].empty() && head_var == tail_var) {
1547 const auto vars = constraints_to_vars[ct];
1548 const int pos_var = absl::Uniform<int>(random, 0, vars.size());
1549 const int candidate = vars[pos_var];
1554 if (!relaxed_variables_set[candidate]) {
1555 head_var = candidate;
1558 if (constraints_to_vars[ct].empty()) {
1565 if (vars_to_constraints[tail_var].empty()) {
1566 std::swap(active_vars[tail_index], active_vars.back());
1567 active_vars.pop_back();
1570 if (head_var != tail_var) {
1571 relaxed_variables_set[head_var] =
true;
1572 relaxed_variables.push_back(head_var);
1573 active_vars.push_back(head_var);
1576 return helper_.RelaxGivenVariables(initial_solution, relaxed_variables);
1583 absl::BitGenRef random) {
1584 const int num_model_constraints =
helper_.ModelProto().constraints_size();
1585 if (num_model_constraints == 0) {
1586 return helper_.FullNeighborhood();
1589 const int num_model_vars =
helper_.ModelProto().variables_size();
1590 std::vector<bool> visited_variables_set(num_model_vars,
false);
1591 std::vector<int> relaxed_variables;
1593 std::vector<bool> added_constraints(num_model_constraints,
false);
1594 std::vector<int> next_constraints;
1596 std::vector<int> random_variables;
1598 absl::ReaderMutexLock graph_lock(&
helper_.graph_mutex_);
1599 const int num_active_vars =
1600 helper_.ActiveVariablesWhileHoldingLock().size();
1601 const int target_size = std::ceil(data.
difficulty * num_active_vars);
1602 if (target_size == num_active_vars)
return helper_.FullNeighborhood();
1605 const int num_active_constraints =
helper_.ConstraintToVar().size();
1606 if (num_active_constraints == 0)
return helper_.NoNeighborhood();
1607 next_constraints.push_back(
1608 absl::Uniform<int>(random, 0, num_active_constraints));
1609 added_constraints[next_constraints.back()] =
true;
1611 while (relaxed_variables.size() < target_size) {
1613 if (next_constraints.empty())
break;
1616 const int i = absl::Uniform<int>(random, 0, next_constraints.size());
1617 const int constraint_index = next_constraints[
i];
1618 std::swap(next_constraints[
i], next_constraints.back());
1619 next_constraints.pop_back();
1623 DCHECK_LT(constraint_index, num_active_constraints);
1624 random_variables.assign(
1625 helper_.ConstraintToVar()[constraint_index].begin(),
1626 helper_.ConstraintToVar()[constraint_index].end());
1627 std::shuffle(random_variables.begin(), random_variables.end(), random);
1628 for (
const int var : random_variables) {
1629 if (visited_variables_set[var])
continue;
1630 visited_variables_set[var] =
true;
1632 relaxed_variables.push_back(var);
1634 if (relaxed_variables.size() >= target_size)
break;
1636 for (
const int ct :
helper_.VarToConstraint()[var]) {
1637 if (added_constraints[ct])
continue;
1638 added_constraints[ct] =
true;
1639 next_constraints.push_back(ct);
1645 return helper_.RelaxGivenVariables(initial_solution, relaxed_variables);
1650 absl::BitGenRef random) {
1652 int size_at_min_width_after_100;
1653 int min_width_after_100 = std::numeric_limits<int>::max();
1654 int num_zero_score = 0;
1655 std::vector<int> relaxed_variables;
1661 absl::ReaderMutexLock graph_lock(&
helper_.graph_mutex_);
1663 const int num_active_vars =
1664 helper_.ActiveVariablesWhileHoldingLock().size();
1665 const int target_size = std::ceil(data.
difficulty * num_active_vars);
1666 if (target_size == num_active_vars)
return helper_.FullNeighborhood();
1668 const int num_vars =
helper_.VarToConstraint().size();
1669 const int num_constraints =
helper_.ConstraintToVar().size();
1670 if (num_constraints == 0 || num_vars == 0) {
1671 return helper_.FullNeighborhood();
1676 const int num_nodes = num_vars + num_constraints;
1677 std::vector<bool> added(num_nodes,
false);
1678 std::vector<bool> added_or_connected(num_nodes,
false);
1681 struct QueueElement {
1682 int Index()
const {
return index; }
1683 bool operator<(
const QueueElement& o)
const {
1684 if (score == o.score)
return tie_break < o.tie_break;
1685 return score < o.score;
1690 double tie_break = 0.0;
1692 std::vector<QueueElement> elements(num_nodes);
1696 for (
int i = 0;
i < num_nodes; ++
i) {
1697 elements[
i].index =
i;
1698 elements[
i].tie_break = absl::Uniform<double>(random, 0.0, 1.0);
1708 const int first_index =
1709 helper_.ActiveVariablesWhileHoldingLock()[absl::Uniform<int>(
1710 random, 0, num_active_vars)];
1711 elements[first_index].score =
helper_.VarToConstraint()[first_index].size();
1712 pq.
Add(elements[first_index]);
1713 added_or_connected[first_index] =
true;
1716 std::vector<int> to_update;
1717 while (!pq.
IsEmpty() && relaxed_variables.size() < target_size) {
1719 if (relaxed_variables.size() > 100 && pq.
Size() < min_width_after_100) {
1720 min_width_after_100 = pq.
Size();
1721 size_at_min_width_after_100 = relaxed_variables.size();
1724 const int index = pq.
Top().index;
1725 const int score = pq.
Top().score;
1727 added[index] =
true;
1732 if (index < num_vars) relaxed_variables.push_back(index);
1742 if (index < num_vars) {
1743 relaxed_variables.push_back(index);
1744 for (
const int c :
helper_.VarToConstraint()[index]) {
1745 const int c_index = num_vars + c;
1746 if (added_or_connected[c_index])
continue;
1748 added_or_connected[c_index] =
true;
1749 to_update.push_back(c_index);
1750 for (
const int v :
helper_.ConstraintToVar()[c]) {
1751 if (added[v])
continue;
1752 if (added_or_connected[v]) {
1753 to_update.push_back(v);
1754 elements[v].score--;
1756 elements[c_index].score++;
1761 for (
const int v :
helper_.ConstraintToVar()[index - num_vars]) {
1762 if (added_or_connected[v])
continue;
1764 added_or_connected[v] =
true;
1765 to_update.push_back(v);
1766 for (
const int c :
helper_.VarToConstraint()[v]) {
1767 if (added[num_vars + c])
continue;
1768 if (added_or_connected[num_vars + c]) {
1769 elements[num_vars + c].score--;
1770 to_update.push_back(num_vars + c);
1772 elements[v].score++;
1781 CHECK_EQ(num_added, score);
1784 for (
const int index : to_update) {
1785 DCHECK(!added[index]);
1789 pq.
Add(elements[index]);
1793 max_width = std::max(max_width, pq.
Size());
1797 if (pq.
Size() < min_width_after_100) {
1798 min_width_after_100 = pq.
Size();
1799 size_at_min_width_after_100 = relaxed_variables.size();
1802 VLOG(2) <<
"#relaxed " << relaxed_variables.size() <<
" #zero_score "
1803 << num_zero_score <<
" max_width " << max_width
1804 <<
" (size,min_width)_after_100 (" << size_at_min_width_after_100
1805 <<
"," << min_width_after_100 <<
") "
1806 <<
" final_width " << pq.
Size();
1809 return helper_.RelaxGivenVariables(initial_solution, relaxed_variables);
1816 absl::Span<
const std::pair<int, int64_t>> dist_to_lower_bound,
1817 absl::Span<
const std::pair<int, int64_t>> dist_to_upper_bound,
1818 const int64_t rhs) {
1822 int64_t lhs_constant_value = 0;
1823 for (
const auto [var, lb] : dist_to_lower_bound) {
1827 lhs_constant_value -= lb;
1829 for (
const auto [var, ub] : dist_to_upper_bound) {
1831 lhs_constant_value += ub;
1835 linear->
add_domain(std::numeric_limits<int64_t>::min());
1836 linear->
add_domain(rhs - lhs_constant_value);
1837 return new_constraint;
1844 absl::BitGenRef random) {
1845 const std::vector<int> active_variables =
helper_.ActiveVariables();
1846 if (active_variables.empty())
return helper_.NoNeighborhood();
1852 const int size = active_variables.size();
1853 if (
static_cast<int>(std::ceil(data.
difficulty * size)) == size) {
1854 return helper_.FullNeighborhood();
1860 std::vector<std::pair<int, double>> candidates_with_score;
1861 std::vector<int> other_variables;
1865 std::vector<std::pair<int, int64_t>> dist_to_lower_bound;
1866 std::vector<std::pair<int, int64_t>> dist_to_upper_bound;
1870 const bool only_look_at_binary = absl::Bernoulli(random, 0.5);
1877 bool some_non_binary_at_bound =
false;
1878 for (
const int var : active_variables) {
1879 DCHECK_LT(var, initial_solution.
solution().size());
1880 DCHECK_LT(var, local_cp_model.
variables().size());
1882 const int64_t base_value = initial_solution.
solution(var);
1883 const bool is_binary = var_proto.
domain_size() == 2 &&
1885 if (only_look_at_binary && !is_binary) {
1886 other_variables.push_back(var);
1890 DCHECK(!var_proto.
domain().empty());
1891 const int64_t domain_min = var_proto.
domain(0);
1892 const int64_t domain_max = var_proto.
domain(var_proto.
domain().size() - 1);
1893 if (base_value <= domain_min) {
1894 if (!is_binary) some_non_binary_at_bound =
true;
1895 candidates_with_score.push_back({var, 0.0});
1896 dist_to_lower_bound.push_back({var, domain_min});
1897 }
else if (base_value >= domain_max) {
1898 if (!is_binary) some_non_binary_at_bound =
true;
1899 candidates_with_score.push_back({var, 0.0});
1900 dist_to_upper_bound.push_back({var, domain_max});
1902 other_variables.push_back(var);
1906 bool use_hamming_for_others =
false;
1907 if (!other_variables.empty() && absl::Bernoulli(random, 0.5)) {
1908 use_hamming_for_others =
true;
1910 if (!use_hamming_for_others && candidates_with_score.empty()) {
1911 return helper_.NoNeighborhood();
1916 if (use_hamming_for_others) {
1917 for (
const int var : other_variables) {
1918 const int indicator = local_cp_model.
variables().size();
1921 var_proto->add_domain(1);
1925 const int64_t base_value = initial_solution.
solution(var);
1926 new_ct->mutable_linear()->add_domain(base_value);
1927 new_ct->mutable_linear()->add_domain(base_value);
1928 new_ct->mutable_linear()->add_vars(var);
1929 new_ct->mutable_linear()->add_coeffs(1);
1932 dist_to_lower_bound.push_back({indicator, 0});
1933 candidates_with_score.push_back({var, 0.0});
1937 other_variables.clear();
1941 const int size = dist_to_upper_bound.size() + dist_to_lower_bound.size();
1942 const int target_size =
static_cast<int>(std::ceil(data.
difficulty * size));
1943 DCHECK_LE(target_size, candidates_with_score.size());
1944 *local_cp_model.
add_constraints() = DistanceToBoundsSmallerThanConstraint(
1945 dist_to_lower_bound, dist_to_upper_bound, target_size);
1947 Model model(
"lb_relax_lns_lp");
1952 params->set_linearization_level(2);
1953 params->set_stop_after_root_propagation(
true);
1954 params->set_add_lp_constraints_lazily(
false);
1957 params->set_cp_model_presolve(
false);
1958 params->set_cp_model_probing_level(0);
1962 params->set_root_lp_iterations(100000);
1966 params->set_max_deterministic_time(10);
1968 if (global_time_limit_ !=
nullptr) {
1981 if (absl::GetFlag(FLAGS_cp_model_dump_submodels)) {
1982 const std::string dump_name =
1983 absl::StrCat(absl::GetFlag(FLAGS_cp_model_dump_prefix),
1984 "lb_relax_lns_lp_", data.
task_id,
".pb.txt");
1985 LOG(INFO) <<
"Dumping linear relaxed model to '" << dump_name <<
"'.";
1998 response_manager->InitializeObjective(local_cp_model);
2016 return helper_.NoNeighborhood();
2022 if (inner_lb >= current_inner_obj) {
2028 return helper_.NoNeighborhood();
2036 if (lp_solution->empty()) {
2038 return helper_.NoNeighborhood();
2040 for (
auto& [var, score] : candidates_with_score) {
2041 const IntegerVariable integer = var_mapping->Integer(var);
2042 DCHECK_LT(integer, lp_solution->size());
2043 DCHECK_LT(var, initial_solution.
solution().size());
2044 const double difference =
2045 std::abs(lp_solution->at(var_mapping->Integer(var)) -
2047 score = difference + absl::Uniform<double>(random, 0.0, 1e-6);
2051 absl::c_sort(candidates_with_score, [](
const std::pair<int, double>& a,
2052 const std::pair<int, double>&
b) {
2053 return a.second >
b.second;
2056 std::vector<int> vars_to_relax;
2057 vars_to_relax.
reserve(target_size);
2058 DCHECK_LE(target_size, candidates_with_score.size());
2059 for (
int i = 0;
i < target_size; ++
i) {
2060 vars_to_relax.push_back(candidates_with_score[
i].first);
2065 vars_to_relax.insert(vars_to_relax.end(), other_variables.begin(),
2066 other_variables.end());
2068 helper_.RelaxGivenVariables(initial_solution, vars_to_relax);
2076 some_non_binary_at_bound ?
"_int" :
"_bool");
2077 if (use_hamming_for_others) {
2089 linear->
add_domain(std::numeric_limits<int64_t>::min());
2104 const absl::Span<
const std::pair<int, int>> precedences,
2109 neighborhood.
is_reduced = !precedences.empty();
2113 return neighborhood;
2117 absl::flat_hash_set<int> seen_intervals;
2118 for (
const std::pair<int, int>& prec : precedences) {
2119 seen_intervals.insert(prec.first);
2120 seen_intervals.insert(prec.second);
2124 bool enforcement_literals_fixed =
false;
2126 if (seen_intervals.contains(
i))
continue;
2133 const int enforcement_var =
PositiveRef(enforcement_ref);
2134 const int value = initial_solution.
solution(enforcement_var);
2141 if (
RefIsPositive(enforcement_ref) == (value == 0))
continue;
2147 enforcement_literals_fixed =
true;
2150 for (
const std::pair<int, int>& prec : precedences) {
2155 DCHECK_LE(GetLinearExpressionValue(before_end, initial_solution),
2156 GetLinearExpressionValue(after_start, initial_solution));
2157 AddPrecedence(before_end, after_start, &neighborhood.
delta);
2164 return neighborhood;
2168 absl::Span<const int> intervals_to_relax,
2169 absl::Span<const int> variables_to_fix,
2175 absl::flat_hash_set<int> ignored_intervals(intervals_to_relax.begin(),
2176 intervals_to_relax.end());
2181 if (ignored_intervals.contains(
i))
continue;
2188 const int enforcement_var =
PositiveRef(enforcement_ref);
2189 const int value = initial_solution.
solution(enforcement_var);
2197 ignored_intervals.insert(
i);
2207 if (ignored_intervals.size() >=
2212 return neighborhood;
2221 const std::vector<std::pair<int, int>> precedences =
2224 for (
const std::pair<int, int>& prec : precedences) {
2229 DCHECK_LE(GetLinearExpressionValue(before_end, initial_solution),
2230 GetLinearExpressionValue(after_start, initial_solution));
2231 AddPrecedence(before_end, after_start, &neighborhood.
delta);
2235 for (
const int var : variables_to_fix) {
2236 const int value = initial_solution.
solution(var);
2246 return neighborhood;
2251 absl::BitGenRef random) {
2252 std::vector<int> intervals_to_relax =
2253 helper_.GetActiveIntervals(initial_solution);
2254 GetRandomSubset(data.
difficulty, &intervals_to_relax, random);
2257 intervals_to_relax, {}, initial_solution, random,
helper_);
2262 absl::BitGenRef random) {
2263 std::vector<std::pair<int, int>> precedences =
2264 helper_.GetSchedulingPrecedences({}, initial_solution, random);
2265 GetRandomSubset(1.0 - data.
difficulty, &precedences, random);
2267 precedences, initial_solution,
helper_);
2271void AppendVarsFromAllIntervalIndices(absl::Span<const int> indices,
2272 absl::Span<const int> all_intervals,
2274 std::vector<int>* variables) {
2275 for (
const int index : indices) {
2276 const std::vector<int> vars =
2278 variables->insert(variables->end(), vars.begin(), vars.end());
2285 absl::BitGenRef random) {
2286 const std::vector<int> active_intervals =
2287 helper_.GetActiveIntervals(initial_solution);
2289 if (active_intervals.empty())
return helper_.FullNeighborhood();
2291 const TimePartition partition = PartitionIndicesAroundRandomTimeWindow(
2294 std::vector<int> intervals_to_relax;
2295 intervals_to_relax.reserve(partition.selected_indices.size());
2296 std::vector<int> variables_to_fix;
2297 intervals_to_relax.insert(intervals_to_relax.end(),
2298 partition.selected_indices.begin(),
2299 partition.selected_indices.end());
2301 if (
helper_.Parameters().push_all_tasks_toward_start()) {
2302 intervals_to_relax.insert(intervals_to_relax.end(),
2303 partition.indices_before_selected.begin(),
2304 partition.indices_before_selected.end());
2305 AppendVarsFromAllIntervalIndices(partition.indices_before_selected,
2306 active_intervals,
helper_.ModelProto(),
2313 intervals_to_relax, variables_to_fix, initial_solution, random,
helper_);
2318 absl::BitGenRef random) {
2319 std::vector<int> intervals_to_relax;
2320 std::vector<int> variables_to_fix;
2321 std::vector<int> active_intervals;
2322 for (
const std::vector<int>& intervals : intervals_in_constraints_) {
2323 active_intervals =
helper_.KeepActiveIntervals(intervals, initial_solution);
2324 const TimePartition partition = PartitionIndicesAroundRandomTimeWindow(
2325 active_intervals,
helper_.ModelProto(), initial_solution,
2327 intervals_to_relax.insert(intervals_to_relax.end(),
2328 partition.selected_indices.begin(),
2329 partition.selected_indices.end());
2331 if (
helper_.Parameters().push_all_tasks_toward_start()) {
2332 intervals_to_relax.insert(intervals_to_relax.end(),
2333 partition.indices_before_selected.begin(),
2334 partition.indices_before_selected.end());
2335 AppendVarsFromAllIntervalIndices(partition.indices_before_selected,
2336 active_intervals,
helper_.ModelProto(),
2341 if (intervals_to_relax.empty() && variables_to_fix.empty()) {
2342 return helper_.FullNeighborhood();
2348 intervals_to_relax, variables_to_fix, initial_solution, random,
helper_);
2353 absl::BitGenRef random) {
2354 std::vector<ActiveRectangle> rectangles_to_freeze =
2355 helper_.GetActiveRectangles(initial_solution);
2356 GetRandomSubset(1.0 - data.
difficulty, &rectangles_to_freeze, random);
2361 variables_to_freeze);
2363 variables_to_freeze);
2365 return helper_.FixGivenVariables(initial_solution, variables_to_freeze);
2370 absl::BitGenRef random) {
2372 const std::vector<ActiveRectangle> all_active_rectangles =
2373 helper_.GetActiveRectangles(initial_solution);
2374 if (all_active_rectangles.size() <= 1)
return helper_.FullNeighborhood();
2377 all_active_rectangles[absl::Uniform<int>(random, 0,
2378 all_active_rectangles.size())];
2380 const auto get_rectangle = [&initial_solution, helper = &
helper_](
2382 const int x_interval_idx = rectangle.x_interval;
2383 const int y_interval_idx = rectangle.y_interval;
2385 helper->ModelProto().constraints(x_interval_idx);
2387 helper->ModelProto().constraints(y_interval_idx);
2388 return Rectangle{.x_min = GetLinearExpressionValue(
2390 .x_max = GetLinearExpressionValue(
2391 x_interval_ct.
interval().
end(), initial_solution),
2392 .y_min = GetLinearExpressionValue(
2394 .y_max = GetLinearExpressionValue(
2395 y_interval_ct.
interval().
end(), initial_solution)};
2398 const Rectangle center_rect = get_rectangle(base_rectangle);
2407 std::vector<std::pair<int, double>> distances;
2408 distances.reserve(all_active_rectangles.size());
2409 for (
int i = 0;
i < all_active_rectangles.size(); ++
i) {
2412 variables_to_freeze);
2414 variables_to_freeze);
2416 const Rectangle rect = get_rectangle(rectangle);
2417 const bool same_no_overlap_as_center_rect = absl::c_any_of(
2419 return rectangle.no_overlap_2d_constraints.contains(c);
2421 if (same_no_overlap_as_center_rect) {
2422 distances.push_back(
2427 distances.begin(), distances.end(),
2428 [](
const auto& a,
const auto&
b) { return a.second < b.second; });
2430 const int num_to_sample = data.
difficulty * all_active_rectangles.size();
2431 const int num_to_relax = std::min<int>(distances.size(), num_to_sample);
2432 Rectangle relaxed_bounding_box = center_rect;
2433 absl::flat_hash_set<int> boxes_to_relax;
2434 for (
int i = 0;
i < num_to_relax; ++
i) {
2435 const int rectangle_idx = distances[
i].first;
2436 const ActiveRectangle& rectangle = all_active_rectangles[rectangle_idx];
2437 relaxed_bounding_box.
GrowToInclude(get_rectangle(rectangle));
2438 boxes_to_relax.insert(rectangle_idx);
2444 const IntegerValue x_size = relaxed_bounding_box.
SizeX();
2445 const IntegerValue y_size = relaxed_bounding_box.
SizeY();
2451 for (
const int b : boxes_to_relax) {
2454 variables_to_freeze);
2456 variables_to_freeze);
2459 helper_.FixGivenVariables(initial_solution, variables_to_freeze);
2470 for (
const int b : boxes_to_relax) {
2474 .constraints(all_active_rectangles[
b].x_interval)
2477 relaxed_bounding_box.
x_max.value());
2478 RestrictAffineExpression(x_interval.
start(), x_domain,
2479 &neighborhood.
delta);
2480 RestrictAffineExpression(x_interval.
end(), x_domain, &neighborhood.
delta);
2485 .constraints(all_active_rectangles[
b].y_interval)
2488 relaxed_bounding_box.
y_max.value());
2489 RestrictAffineExpression(y_interval.
start(), y_domain,
2490 &neighborhood.
delta);
2491 RestrictAffineExpression(y_interval.
end(), y_domain, &neighborhood.
delta);
2494 return neighborhood;
2499 absl::BitGenRef random) {
2501 std::vector<ActiveRectangle> all_active_rectangles =
2502 helper_.GetActiveRectangles(initial_solution);
2503 if (all_active_rectangles.size() <= 2)
return helper_.FullNeighborhood();
2505 const int first_idx =
2506 absl::Uniform<int>(random, 0, all_active_rectangles.size());
2508 absl::Uniform<int>(random, 0, all_active_rectangles.size() - 1);
2509 if (second_idx >= first_idx) {
2513 const ActiveRectangle& chosen_rectangle_1 = all_active_rectangles[first_idx];
2514 const ActiveRectangle& chosen_rectangle_2 = all_active_rectangles[second_idx];
2516 const auto get_rectangle = [&initial_solution, helper = &
helper_](
2518 const int x_interval_idx = rectangle.x_interval;
2519 const int y_interval_idx = rectangle.y_interval;
2521 helper->ModelProto().constraints(x_interval_idx);
2523 helper->ModelProto().constraints(y_interval_idx);
2524 return Rectangle{.x_min = GetLinearExpressionValue(
2526 .x_max = GetLinearExpressionValue(
2527 x_interval_ct.
interval().
end(), initial_solution),
2528 .y_min = GetLinearExpressionValue(
2530 .y_max = GetLinearExpressionValue(
2531 y_interval_ct.
interval().
end(), initial_solution)};
2534 const Rectangle rect1 = get_rectangle(chosen_rectangle_1);
2535 const Rectangle rect2 = get_rectangle(chosen_rectangle_2);
2545 std::vector<std::pair<int, double>> distances1;
2546 std::vector<std::pair<int, double>> distances2;
2547 distances1.reserve(all_active_rectangles.size());
2548 distances2.reserve(all_active_rectangles.size());
2549 for (
int i = 0;
i < all_active_rectangles.size(); ++
i) {
2552 variables_to_freeze);
2554 variables_to_freeze);
2556 const Rectangle rect = get_rectangle(rectangle);
2557 const bool same_no_overlap_as_rect1 =
2559 [&rectangle](
const int c) {
2560 return rectangle.no_overlap_2d_constraints.contains(c);
2562 const bool same_no_overlap_as_rect2 =
2564 [&rectangle](
const int c) {
2565 return rectangle.no_overlap_2d_constraints.contains(c);
2567 if (same_no_overlap_as_rect1) {
2570 if (same_no_overlap_as_rect2) {
2574 const int num_to_sample_each =
2575 data.
difficulty * all_active_rectangles.size() / 2;
2576 std::sort(distances1.begin(), distances1.end(),
2577 [](
const auto& a,
const auto&
b) { return a.second < b.second; });
2578 std::sort(distances2.begin(), distances2.end(),
2579 [](
const auto& a,
const auto&
b) { return a.second < b.second; });
2580 for (
auto& samples : {distances1, distances2}) {
2581 const int num_potential_samples = samples.size();
2582 for (
int i = 0;
i < std::min(num_potential_samples, num_to_sample_each);
2584 const int rectangle_idx = samples[
i].first;
2585 const ActiveRectangle& rectangle = all_active_rectangles[rectangle_idx];
2587 variables_to_freeze);
2589 variables_to_freeze);
2593 return helper_.FixGivenVariables(initial_solution, variables_to_freeze);
2598 absl::BitGenRef random) {
2599 std::vector<ActiveRectangle> rectangles_to_relax =
2600 helper_.GetActiveRectangles(initial_solution);
2601 GetRandomSubset(data.
difficulty, &rectangles_to_relax, random);
2602 std::vector<int> intervals_to_relax;
2604 intervals_to_relax.push_back(rect.x_interval);
2605 intervals_to_relax.push_back(rect.y_interval);
2610 intervals_to_relax, {}, initial_solution, random,
helper_);
2615 absl::BitGenRef random) {
2616 const std::vector<ActiveRectangle> active_rectangles =
2617 helper_.GetActiveRectangles(initial_solution);
2618 const bool use_first_dimension = absl::Bernoulli(random, 0.5);
2619 std::vector<int> projected_intervals;
2620 projected_intervals.reserve(active_rectangles.size());
2622 projected_intervals.push_back(use_first_dimension ? rect.x_interval
2626 const TimePartition partition = PartitionIndicesAroundRandomTimeWindow(
2627 projected_intervals,
helper_.ModelProto(), initial_solution,
2629 std::vector<bool> indices_to_fix(active_rectangles.size(),
true);
2630 for (
const int index : partition.selected_indices) {
2631 indices_to_fix[index] =
false;
2635 for (
int index = 0; index < active_rectangles.size(); ++index) {
2636 if (indices_to_fix[index]) {
2638 active_rectangles[index].x_interval,
2639 variables_to_freeze);
2641 active_rectangles[index].y_interval,
2642 variables_to_freeze);
2646 return helper_.FixGivenVariables(initial_solution, variables_to_freeze);
2651 absl::BitGenRef random) {
2652 const std::vector<std::vector<int>> all_paths =
2653 helper_.GetRoutingPathBooleanVariables(initial_solution);
2656 std::vector<int> variables_to_fix;
2657 for (
const auto& path : all_paths) {
2658 variables_to_fix.insert(variables_to_fix.end(), path.begin(), path.end());
2661 GetRandomSubset(1.0 - data.
difficulty, &variables_to_fix, random);
2664 for (
const int var : variables_to_fix) to_fix.
Set(var);
2665 return helper_.FixGivenVariables(initial_solution, to_fix);
2670 absl::BitGenRef random) {
2671 std::vector<std::vector<int>> all_paths =
2672 helper_.GetRoutingPathBooleanVariables(initial_solution);
2675 if (all_paths.empty()) {
2676 return helper_.NoNeighborhood();
2680 std::vector<int> all_path_variables;
2681 int sum_of_path_sizes = 0;
2682 for (
const auto& path : all_paths) {
2683 sum_of_path_sizes += path.size();
2685 all_path_variables.reserve(sum_of_path_sizes);
2686 for (
const auto& path : all_paths) {
2687 all_path_variables.insert(all_path_variables.end(), path.begin(),
2693 const int num_variables_to_relax =
2694 static_cast<int>(all_path_variables.size() * data.
difficulty);
2695 absl::flat_hash_set<int> relaxed_variables;
2697 while (relaxed_variables.size() < num_variables_to_relax) {
2698 DCHECK(!all_paths.empty());
2699 const int path_index = absl::Uniform<int>(random, 0, all_paths.size());
2700 std::vector<int>& path = all_paths[path_index];
2701 const int path_size = path.size();
2702 const int segment_length =
2703 std::min(path_size, absl::Uniform<int>(random, 4, 8));
2704 const int segment_start =
2705 absl::Uniform<int>(random, 0, path_size - segment_length);
2706 for (
int i = segment_start;
i < segment_start + segment_length; ++
i) {
2707 relaxed_variables.insert(path[
i]);
2711 path.erase(path.begin() + segment_start,
2712 path.begin() + segment_start + segment_length);
2714 std::swap(all_paths[path_index], all_paths.back());
2715 all_paths.pop_back();
2721 for (
const int var : all_path_variables) {
2722 if (!relaxed_variables.contains(var)) to_fix.
Set(var);
2724 return helper_.FixGivenVariables(initial_solution, to_fix);
2729 absl::BitGenRef random) {
2730 std::vector<std::vector<int>> all_paths =
2731 helper_.GetRoutingPathBooleanVariables(initial_solution);
2734 if (all_paths.empty()) {
2735 return helper_.NoNeighborhood();
2739 std::vector<int> all_path_variables;
2740 int sum_of_path_sizes = 0;
2741 for (
const auto& path : all_paths) {
2742 sum_of_path_sizes += path.size();
2744 all_path_variables.reserve(sum_of_path_sizes);
2745 for (
const auto& path : all_paths) {
2746 all_path_variables.insert(all_path_variables.end(), path.begin(),
2752 const int num_variables_to_relax =
2753 static_cast<int>(all_path_variables.size() * data.
difficulty);
2754 absl::flat_hash_set<int> relaxed_variables;
2758 for (
const auto& path : all_paths) {
2759 relaxed_variables.insert(path.front());
2760 relaxed_variables.insert(path.back());
2764 const int path_index = absl::Uniform<int>(random, 0, all_paths.size());
2765 std::shuffle(all_paths[path_index].
begin(), all_paths[path_index].
end(),
2767 while (relaxed_variables.size() < num_variables_to_relax &&
2768 !all_paths[path_index].empty()) {
2769 relaxed_variables.insert(all_paths[path_index].back());
2770 all_paths[path_index].pop_back();
2774 if (relaxed_variables.size() < num_variables_to_relax) {
2775 std::shuffle(all_path_variables.begin(), all_path_variables.end(), random);
2776 while (relaxed_variables.size() < num_variables_to_relax) {
2777 relaxed_variables.insert(all_path_variables.back());
2778 all_path_variables.pop_back();
2784 for (
const int var : all_path_variables) {
2785 if (!relaxed_variables.contains(var)) to_fix.
Set(var);
2787 return helper_.FixGivenVariables(initial_solution, to_fix);
2791 return (incomplete_solutions_->HasSolution() ||
2792 lp_solutions_->NumSolutions() > 0);
2797 absl::BitGenRef random) {
2803 incomplete_solutions_, data.
difficulty, random);
2807 return neighborhood;
2811 absl::ReaderMutexLock graph_lock(&
helper_.graph_mutex_);
2813 for (
const std::pair</*model_var*/ int, /*value*/ int64_t>& fixed_var :
2815 const int var = fixed_var.first;
2816 const int64_t value = fixed_var.second;
2818 if (!
helper_.IsActive(var))
continue;
2822 return neighborhood;
2831 for (
const std::pair<
int,
2832 std::pair<int64_t, int64_t>>& reduced_var :
2834 const int var = reduced_var.first;
2835 const int64_t lb = reduced_var.second.first;
2836 const int64_t ub = reduced_var.second.second;
2838 if (!
helper_.IsActive(var))
continue;
2850 return neighborhood;
bool AddEdge(int node1, int node2)
void SetNumberOfNodes(int num_nodes)
IndexType size() const
Returns how many bits this Bitset64 can hold.
void Clear(IndexType i)
Sets the bit at position i to 0.
void Set(IndexType i)
Sets the bit at position i to 1.
static Domain FromValues(std::vector< int64_t > values)
Domain IntersectionWith(const Domain &domain) const
bool IsIncludedIn(const Domain &domain) const
int64_t ClosestValue(int64_t wanted) const
void Add(Element element)
void ChangePriority(Element element)
int Size() const
Returns the number of elements currently present.
bool Contains(int index) const
Returns true if the element with given index is currently in the queue.
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
::int32_t heads(int index) const
::int32_t literals(int index) const
int literals_size() const
repeated int32 literals = 5;
::int32_t tails(int index) const
void RemoveBySwap(K key, int index)
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
ConstraintCase constraint_case() const
::int32_t enforcement_literal(int index) const
const ::operations_research::sat::IntervalConstraintProto & interval() const
const ::operations_research::sat::RoutesConstraintProto & routes() const
void add_enforcement_literal(::int32_t value)
::operations_research::sat::LinearConstraintProto *PROTOBUF_NONNULL mutable_linear()
const ::operations_research::sat::CircuitConstraintProto & circuit() const
const ::operations_research::sat::IntegerVariableProto & variables(int index) const
const ::operations_research::sat::ConstraintProto & constraints(int index) const
void clear_solution_hint()
bool has_objective() const
.operations_research.sat.CpObjectiveProto objective = 4;
int constraints_size() const
repeated .operations_research.sat.ConstraintProto constraints = 3;
::operations_research::sat::IntegerVariableProto *PROTOBUF_NONNULL add_variables()
::operations_research::sat::PartialVariableAssignment *PROTOBUF_NONNULL mutable_solution_hint()
::operations_research::sat::ConstraintProto *PROTOBUF_NONNULL add_constraints()
int variables_size() const
repeated .operations_research.sat.IntegerVariableProto variables = 2;
::operations_research::sat::CpObjectiveProto *PROTOBUF_NONNULL mutable_objective()
::operations_research::sat::IntegerVariableProto *PROTOBUF_NONNULL mutable_variables(int index)
const ::operations_research::sat::CpObjectiveProto & objective() const
void set_integer_scaling_factor(::int64_t value)
::int64_t domain(int index) const
void set_integer_before_offset(::int64_t value)
void set_integer_after_offset(::int64_t value)
::int32_t vars(int index) const
::int64_t coeffs(int index) const
::int64_t inner_objective_lower_bound() const
::operations_research::sat::CpSolverStatus status() const
::int64_t solution(int index) const
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
::google::protobuf::RepeatedField<::int64_t > *PROTOBUF_NONNULL mutable_domain()
int domain_size() const
repeated int64 domain = 2;
const ::std::string & name() const
void add_domain(::int64_t value)
void set_name(Arg_ &&arg, Args_... args)
::int64_t domain(int index) const
const ::operations_research::sat::LinearExpressionProto & size() const
const ::operations_research::sat::LinearExpressionProto & end() const
const ::operations_research::sat::LinearExpressionProto & start() const
void add_vars(::int32_t value)
void add_domain(::int64_t value)
void add_coeffs(::int64_t value)
::int64_t coeffs(int index) const
::int32_t vars(int index) const
int vars_size() const
repeated int32 vars = 1;
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
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 SharedResponseManager & shared_response() const
Neighborhood RelaxGivenVariables(const CpSolverResponse &initial_solution, absl::Span< const int > relaxed_variables) const
void Synchronize() override
std::vector< std::vector< int > > GetUniqueIntervalSets() const
std::vector< ActiveRectangle > GetActiveRectangles(const CpSolverResponse &initial_solution) const
const CpModelProto & ModelProto() const
void AddSolutionHinting(const CpSolverResponse &initial_solution, CpModelProto *model_proto) 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.
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_
void AddSolveData(SolveData data)
absl::Mutex generator_mutex_
double GetUCBScore(int64_t total_num_calls) const
absl::Span< const double > Synchronize()
const NeighborhoodGeneratorHelper & helper_
::int32_t y_intervals(int index) const
::int32_t x_intervals(int index) const
int x_intervals_size() const
repeated int32 x_intervals = 1;
::google::protobuf::RepeatedField<::int64_t > *PROTOBUF_NONNULL mutable_values()
::google::protobuf::RepeatedField<::int32_t > *PROTOBUF_NONNULL mutable_vars()
void add_values(::int64_t value)
void add_vars(::int32_t value)
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
Both initial solution and difficulty values are ignored.
bool ReadyToGenerate() const override
Returns true if the required solutions are available.
::int32_t heads(int index) const
int literals_size() const
repeated int32 literals = 3;
::int32_t literals(int index) const
::int32_t tails(int index) const
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
void set_num_workers(::int32_t value)
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
SubSolver(absl::string_view name, SubsolverType type)
SubsolverType type() const
Returns the type of the subsolver.
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
void reserve(size_type n)
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
void SolveLoadedCpModel(const CpModelProto &model_proto, Model *model)
void RemoveVariablesFromInterval(const CpModelProto &model_proto, int index, Bitset64< int > &output)
bool RefIsPositive(int ref)
int64_t ComputeInnerObjective(const CpObjectiveProto &objective, absl::Span< const int64_t > solution)
ReducedDomainNeighborhood GetRinsRensNeighborhood(const SharedResponseManager *response_manager, const SharedLPSolutionRepository *lp_solutions, SharedIncompleteSolutionManager *incomplete_solutions, double difficulty, absl::BitGenRef random)
bool WriteModelProtoToFile(const M &proto, absl::string_view filename)
bool DomainInProtoContains(const ProtoWithDomain &proto, int64_t value)
Neighborhood GenerateSchedulingNeighborhoodFromIntervalPrecedences(const absl::Span< const std::pair< int, int > > precedences, const CpSolverResponse &initial_solution, const NeighborhoodGeneratorHelper &helper)
double CenterToCenterLInfinityDistance(const Rectangle &a, const Rectangle &b)
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)
double CenterToCenterL2Distance(const Rectangle &a, const Rectangle &b)
Returns the L2 distance between the centers of the two rectangles.
std::vector< int > UsedVariables(const ConstraintProto &ct)
std::vector< int > UsedIntervals(const ConstraintProto &ct)
Returns the sorted list of interval used by a constraint.
void FillDomainInProto(const Domain &domain, ProtoWithDomain *proto)
Serializes a Domain into the domain field of a proto.
IntegerValue CapAddI(IntegerValue a, IntegerValue b)
Domain ReadDomainFromProto(const ProtoWithDomain &proto)
Reads a Domain from the domain field of a proto.
void LoadCpModel(const CpModelProto &model_proto, Model *model)
int NegatedRef(int ref)
Small utility functions to deal with negative variable/literal references.
void InsertVariablesFromInterval(const CpModelProto &model_proto, int index, Bitset64< int > &output)
Insert/Remove variables from an interval constraint into a bitset.
IntegerValue CapSubI(IntegerValue a, IntegerValue b)
In SWIG mode, we don't want anything besides these top-level includes.
int64_t CapSub(int64_t x, int64_t y)
ClosedInterval::Iterator end(ClosedInterval interval)
ClosedInterval::Iterator begin(ClosedInterval interval)
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.
double difficulty
The difficulty when this neighborhood was generated.
CpSolverStatus status
The status of the sub-solve.
int task_id
For debugging.
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.
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
void GrowToInclude(const Rectangle &other)
IntegerValue SizeY() const
IntegerValue SizeX() const
std::vector< std::pair< int, std::pair< int64_t, int64_t > > > reduced_domain_vars
std::vector< std::pair< int, int64_t > > fixed_vars
A variable will appear only once and not in both vectors.