Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
cp_model_lns.cc
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
15
16#include <algorithm>
17#include <cmath>
18#include <cstdint>
19#include <deque>
20#include <functional>
21#include <limits>
22#include <memory>
23#include <random>
24#include <string>
25#include <tuple>
26#include <utility>
27#include <vector>
28
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"
55#include "ortools/sat/model.h"
57#include "ortools/sat/rins.h"
61#include "ortools/sat/util.h"
63#include "ortools/util/bitset.h"
69
70namespace operations_research {
71namespace sat {
72
74 CpModelProto const* model_proto, SatParameters const* parameters,
76 ModelSharedTimeLimit* global_time_limit, SharedBoundsManager* shared_bounds)
77 : SubSolver("neighborhood_helper", HELPER),
78 parameters_(*parameters),
79 model_proto_(*model_proto),
80 shared_bounds_(shared_bounds),
81 global_time_limit_(global_time_limit),
82 shared_response_(shared_response) {
83 // Initialize proto memory.
84 local_arena_storage_.assign(Neighborhood::kDefaultArenaSizePerVariable *
85 model_proto_.variables_size(),
86 0);
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());
91
92 CHECK(shared_response_ != nullptr);
93 if (shared_bounds_ != nullptr) {
94 shared_bounds_id_ = shared_bounds_->RegisterNewId();
95 }
96 *model_proto_with_only_variables_.mutable_variables() =
97 model_proto_.variables();
98 InitializeHelperData();
99 RecomputeHelperData();
100 Synchronize();
101}
102
104 if (shared_response_->ProblemIsSolved() ||
105 global_time_limit_->LimitReached()) {
106 return;
107 }
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);
114
115 bool new_variables_have_been_fixed = false;
116
117 if (!model_variables.empty()) {
118 absl::MutexLock domain_lock(&domain_mutex_);
119
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];
124 if (VLOG_IS_ON(3)) {
125 const auto& domain =
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
131 << "]";
132 }
133 const Domain old_domain = ReadDomainFromProto(
134 model_proto_with_only_variables_.variables(var));
135 const Domain new_domain =
136 old_domain.IntersectionWith(Domain(new_lb, new_ub));
137 if (new_domain.IsEmpty()) {
138 // This can mean two things:
139 // 1/ This variable is a normal one and the problem is UNSAT or
140 // 2/ This variable is optional, and its associated literal must be
141 // set to false.
142 //
143 // Currently, we wait for any full solver to pick the crossing bounds
144 // and do the correct stuff on their own. We do not want to have empty
145 // domain in the proto as this would means INFEASIBLE. So we just
146 // ignore such bounds here.
147 //
148 // TODO(user): We could set the optional literal to false directly in
149 // the bound sharing manager. We do have to be careful that all the
150 // different solvers have the same optionality definition though.
151 continue;
152 }
154 new_domain,
155 model_proto_with_only_variables_.mutable_variables(var));
156 new_variables_have_been_fixed |= new_domain.IsFixed();
157 }
158 }
159
160 // Only trigger the computation if needed.
161 if (new_variables_have_been_fixed) {
162 RecomputeHelperData();
163 }
164 }
165}
166
167bool NeighborhoodGeneratorHelper::ObjectiveDomainIsConstraining() const {
168 if (!model_proto_.has_objective()) return false;
169 if (model_proto_.objective().domain().empty()) return false;
170
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) {
175 const int var = PositiveRef(model_proto_.objective().vars(i));
176 const int64_t coeff = model_proto_.objective().coeffs(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);
183 }
184
185 const Domain obj_domain = ReadDomainFromProto(model_proto_.objective());
186 const Domain inferred_domain =
187 Domain(min_activity, max_activity)
189 Domain(std::numeric_limits<int64_t>::min(), obj_domain.Max()));
190 return !inferred_domain.IsIncludedIn(obj_domain);
191}
192
193void NeighborhoodGeneratorHelper::InitializeHelperData() {
194 type_to_constraints_.clear();
195 const int num_constraints = model_proto_.constraints_size();
196 for (int c = 0; c < num_constraints; ++c) {
197 const int type = model_proto_.constraints(c).constraint_case();
198 if (type >= type_to_constraints_.size()) {
199 type_to_constraints_.resize(type + 1);
200 }
201 type_to_constraints_[type].push_back(c);
202 }
203
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);
211 DCHECK_NE(coeff, 0);
212 is_in_objective_[PositiveRef(ref)] = true;
213 has_positive_objective_coefficient_[PositiveRef(ref)] =
214 ref == PositiveRef(ref) ? coeff > 0 : coeff < 0;
215 }
216 }
217}
218
219// Recompute all the data when new variables have been fixed. Note that this
220// shouldn't be called if there is no change as it is in O(problem size).
221void NeighborhoodGeneratorHelper::RecomputeHelperData() {
222 absl::MutexLock graph_lock(&graph_mutex_);
223 absl::ReaderMutexLock domain_lock(&domain_mutex_);
224
225 // Do basic presolving to have a more precise graph.
226 // Here we just remove trivially true constraints.
227 //
228 // Note(user): We do that each time a new variable is fixed. It might be too
229 // much, but on the miplib and in 1200s, we do that only about 1k time on the
230 // worst case problem.
231 //
232 // TODO(user): Change API to avoid a few copy?
233 // TODO(user): We could keep the context in the class.
234 // TODO(user): We can also start from the previous simplified model instead.
235 {
236 Model local_model;
237 CpModelProto mapping_proto;
238 // We want to replace the simplified_model_proto_ by a new one. Since
239 // deleting an object in the arena doesn't free the memory, we also delete
240 // and recreate the arena, but reusing the same storage.
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_,
253 &mapping_proto);
254 ModelCopy copier(&context);
255
256 // TODO(user): Not sure what to do if the model is UNSAT.
257 // This shouldn't matter as it should be dealt with elsewhere.
258 copier.ImportAndSimplifyConstraints(model_proto_, {});
259 }
260
261 // Compute the constraint <-> variable graph.
262 //
263 // TODO(user): Remove duplicate constraints?
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) {
268 // We remove the interval constraints since we should have an equivalent
269 // linear constraint somewhere else. This is not the case if we have a fixed
270 // size optional interval variable. But it should not matter as the
271 // intervals are replaced by their underlying variables in the scheduling
272 // constraints.
273 if (constraints[ct_index].constraint_case() == ConstraintProto::kInterval) {
274 continue;
275 }
276
277 tmp_row_.clear();
278 for (const int var : UsedVariables(constraints[ct_index])) {
279 if (IsConstant(var)) continue;
280 tmp_row_.push_back(var);
281 }
282
283 // We replace intervals by their underlying integer variables. Note that
284 // this is needed for a correct decomposition into independent part.
285 bool need_sort = false;
286 for (const int interval : UsedIntervals(constraints[ct_index])) {
287 need_sort = true;
288 for (const int var : UsedVariables(constraints[interval])) {
289 if (IsConstant(var)) continue;
290 tmp_row_.push_back(var);
291 }
292 }
293
294 // We remove constraint of size 0 and 1 since they are not useful for LNS
295 // based on this graph.
296 if (tmp_row_.size() <= 1) {
297 continue;
298 }
299
300 // Keep this constraint.
301 if (need_sort) {
303 }
304 constraint_to_var_.Add(tmp_row_);
305 }
306
307 // Initialize var to constraints, and make sure it has an entry for all
308 // variables.
309 var_to_constraint_.ResetFromTranspose(
310 constraint_to_var_,
311 /*min_transpose_size=*/model_proto_.variables().size());
312
313 // We mark as active all non-constant variables.
314 // Non-active variable will never be fixed in standard LNS fragment.
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;
322 }
323 }
324
325 active_objective_variables_.clear();
326 for (const int var : model_proto_.objective().vars()) {
327 DCHECK(RefIsPositive(var));
328 if (active_variables_set_[var]) {
329 active_objective_variables_.push_back(var);
330 }
331 }
332
333 // Compute connected components.
334 // Note that fixed variable are just ignored.
335 DenseConnectedComponentsFinder union_find;
336 union_find.SetNumberOfNodes(num_variables);
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) {
341 union_find.AddEdge(row[0], row[i]);
342 }
343 }
344
345 // If we have a lower bound on the objective, then this "objective constraint"
346 // might link components together.
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) {
351 union_find.AddEdge(PositiveRef(refs[0]), PositiveRef(refs[i]));
352 }
353 }
354
355 // Compute all components involving non-fixed variables.
356 //
357 // TODO(user): If a component has no objective, we can fix it to any feasible
358 // solution. This will automatically be done by LNS fragment covering such
359 // component though.
360 components_.clear();
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];
367 if (index == -1) {
368 index = components_.size();
369 components_.push_back({});
370 }
371 var_to_component_index_[var] = index;
372 components_[index].push_back(var);
373 }
374
375 // Display information about the reduced problem.
376 //
377 // TODO(user): Exploit connected component while generating fragments.
378 // TODO(user): Do not generate fragment not touching the objective.
379 if (!shared_response_->LoggingIsEnabled()) return;
380
381 std::vector<int> component_sizes;
382 for (const std::vector<int>& component : components_) {
383 component_sizes.push_back(component.size());
384 }
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) {
390 compo_message =
391 absl::StrCat(" compo:", absl::StrJoin(component_sizes, ","));
392 } else {
393 component_sizes.resize(10);
394 compo_message =
395 absl::StrCat(" compo:", absl::StrJoin(component_sizes, ","), ",...");
396 }
397 }
398
399 // TODO(user): This is not ideal, as if two reductions appears in a row and
400 // nothing else is done for a while, we will never see the "latest" size
401 // in the log until it is reduced again.
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));
407}
408
410 return active_variables_set_[var];
411}
412
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);
417}
418
420 Neighborhood neighborhood;
421 neighborhood.is_reduced = false;
422 neighborhood.is_generated = true;
423 {
424 absl::ReaderMutexLock lock(&domain_mutex_);
425 *neighborhood.delta.mutable_variables() =
426 model_proto_with_only_variables_.variables();
427 }
428 return neighborhood;
429}
430
432 Neighborhood neighborhood;
433 neighborhood.is_generated = false;
434 return neighborhood;
435}
436
437bool NeighborhoodGeneratorHelper::IntervalIsActive(
438 int index, const CpSolverResponse& initial_solution) const {
439 const ConstraintProto& interval_ct = ModelProto().constraints(index);
440 // We only look at intervals that are performed in the solution. The
441 // unperformed intervals should be automatically freed during the generation
442 // phase.
443 if (interval_ct.enforcement_literal().size() == 1) {
444 const int enforcement_ref = interval_ct.enforcement_literal(0);
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;
448 }
449
450 for (const int v : interval_ct.interval().start().vars()) {
451 if (!IsConstant(v)) return true;
452 }
453 for (const int v : interval_ct.interval().size().vars()) {
454 if (!IsConstant(v)) return true;
455 }
456 for (const int v : interval_ct.interval().end().vars()) {
457 if (!IsConstant(v)) return true;
458 }
459 return false;
460}
461
463 absl::Span<const int> unfiltered_intervals,
464 const CpSolverResponse& initial_solution) const {
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);
470 }
471 return filtered_intervals;
472}
473
475 const CpSolverResponse& initial_solution) const {
477 initial_solution);
478}
479
480std::vector<NeighborhoodGeneratorHelper::ActiveRectangle>
482 const CpSolverResponse& initial_solution) const {
483 const std::vector<int> active_intervals =
484 GetActiveIntervals(initial_solution);
485 const absl::flat_hash_set<int> active_intervals_set(active_intervals.begin(),
486 active_intervals.end());
487
488 absl::flat_hash_map<std::pair<int, int>, std::vector<int>> active_rectangles;
489 for (const int ct_index : TypeToConstraints(ConstraintProto::kNoOverlap2D)) {
491 model_proto_.constraints(ct_index).no_overlap_2d();
492 for (int i = 0; i < ct.x_intervals_size(); ++i) {
493 const int x_i = ct.x_intervals(i);
494 const int y_i = ct.y_intervals(i);
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);
498 }
499 }
500 }
501
502 std::vector<ActiveRectangle> results;
503 results.reserve(active_rectangles.size());
504 for (const auto& [rectangle, no_overlap_2d_constraints] : active_rectangles) {
505 ActiveRectangle& result = results.emplace_back();
506 result.x_interval = rectangle.first;
507 result.y_interval = rectangle.second;
508 result.no_overlap_2d_constraints = {no_overlap_2d_constraints.begin(),
509 no_overlap_2d_constraints.end()};
510 }
511 return results;
512}
513
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);
525 }
526 };
527 for (const int ct_index : TypeToConstraints(ConstraintProto::kNoOverlap)) {
528 add_interval_list_only_once(
529 model_proto_.constraints(ct_index).no_overlap().intervals());
530 }
531 for (const int ct_index : TypeToConstraints(ConstraintProto::kCumulative)) {
532 add_interval_list_only_once(
533 model_proto_.constraints(ct_index).cumulative().intervals());
534 }
535 for (const int ct_index : TypeToConstraints(ConstraintProto::kNoOverlap2D)) {
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());
540 }
541 return intervals_in_constraints;
542}
543
544namespace {
545
546int64_t GetLinearExpressionValue(const LinearExpressionProto& expr,
547 const CpSolverResponse& initial_solution) {
548 int64_t result = expr.offset();
549 for (int i = 0; i < expr.vars_size(); ++i) {
550 result += expr.coeffs(i) * initial_solution.solution(expr.vars(i));
551 }
552 return result;
553}
554
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));
562 const Domain domain =
563 ReadDomainFromProto(mutable_proto->variables(expr.vars(0)))
564 .IntersectionWith(implied_domain);
565 if (!domain.IsEmpty()) {
566 FillDomainInProto(domain, mutable_proto->mutable_variables(expr.vars(0)));
567 }
568}
569
570struct StartEndIndex {
571 int64_t start;
572 int64_t end;
573 int index_in_input_vector;
574 double noise;
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);
578 }
579};
580
581struct TimePartition {
582 std::vector<int> indices_before_selected;
583 std::vector<int> selected_indices;
584 std::vector<int> indices_after_selected;
585};
586
587// Selects all intervals in a random time window to meet the difficulty
588// requirement.
589TimePartition PartitionIndicesAroundRandomTimeWindow(
590 absl::Span<const int> intervals, const CpModelProto& model_proto,
591 const CpSolverResponse& initial_solution, double difficulty,
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)});
603 }
604
605 if (start_end_indices.empty()) return {};
606
607 std::sort(start_end_indices.begin(), start_end_indices.end());
608 const int relaxed_size = std::floor(difficulty * start_end_indices.size());
609
610 std::uniform_int_distribution<int> random_var(
611 0, start_end_indices.size() - relaxed_size - 1);
612 // TODO(user): Consider relaxing more than one time window
613 // intervals. This seems to help with Giza models.
614 const int random_start_index = random_var(random);
615
616 // We want to minimize the time window relaxed, so we now sort the interval
617 // after the first selected intervals by end value.
618 // TODO(user): We could do things differently (include all tasks <= some
619 // end). The difficulty is that the number of relaxed tasks will differ from
620 // the target. We could also tie break tasks randomly.
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);
626 });
627 TimePartition result;
628 int i = 0;
629 for (; i < random_start_index; ++i) {
630 result.indices_before_selected.push_back(
631 start_end_indices[i].index_in_input_vector);
632 }
633 for (; i < random_start_index + relaxed_size; ++i) {
634 result.selected_indices.push_back(
635 start_end_indices[i].index_in_input_vector);
636 }
637 for (; i < start_end_indices.size(); ++i) {
638 result.indices_after_selected.push_back(
639 start_end_indices[i].index_in_input_vector);
640 }
641 return result;
642}
643
644struct Demand {
645 int interval_index;
646 int64_t start;
647 int64_t end;
648 int64_t height;
649
650 // Because of the binary splitting of the capacity in the procedure used to
651 // extract precedences out of a cumulative constraint, processing bigger
652 // heights first will decrease its probability of being split across the 2
653 // halves of the current split.
654 bool operator<(const Demand& other) const {
655 return std::tie(start, height, end) <
656 std::tie(other.start, other.height, other.end);
657 }
658
659 std::string DebugString() const {
660 return absl::StrCat("{i=", interval_index, " span=[", start, ",", end, "]",
661 " d=", height, "}");
662 }
663};
664
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);
670 precedences->insert(
671 {demands[i].interval_index, demands[i + 1].interval_index});
672 }
673}
674
675bool IsPresent(const ConstraintProto& interval_ct,
676 const CpSolverResponse& initial_solution) {
677 if (interval_ct.enforcement_literal().size() != 1) return true;
678
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);
682 return RefIsPositive(enforcement_ref) == (value == 1);
683}
684
685void InsertNoOverlapPrecedences(
686 const absl::flat_hash_set<int>& ignored_intervals,
687 const CpSolverResponse& initial_solution, const CpModelProto& model_proto,
688 int no_overlap_index,
689 absl::flat_hash_set<std::pair<int, int>>* precedences) {
690 std::vector<Demand> demands;
691 const NoOverlapConstraintProto& no_overlap =
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;
695 const ConstraintProto& interval_ct =
696 model_proto.constraints(interval_index);
697 if (!IsPresent(interval_ct, initial_solution)) continue;
698
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});
705 }
706
707 // TODO(user): We actually only need interval_index, start.
708 // No need to fill the other fields here.
709 std::sort(demands.begin(), demands.end());
710 InsertPrecedencesFromSortedListOfNonOverlapingIntervals(demands, precedences);
711}
712
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;
719
720 // Checks if any pairs of tasks cannot overlap.
721 int64_t sum_of_min_two_capacities = 2;
722 if (capacity > 1) {
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) {
727 min2 = min1;
728 min1 = demand.height;
729 } else if (demand.height < min2) {
730 min2 = demand.height;
731 }
732 }
733 sum_of_min_two_capacities = min1 + min2;
734 }
735
736 DCHECK_GT(sum_of_min_two_capacities, 1);
737 if (sum_of_min_two_capacities > capacity) {
738 InsertPrecedencesFromSortedListOfNonOverlapingIntervals(demands,
739 precedences);
740 return;
741 }
742
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);
748 }
749 }
750 DCHECK(std::is_sorted(unique_starts.begin(), unique_starts.end()));
751 const int num_points = unique_starts.size();
752
753 // Split the capacity in 2 and dispatch all demands on the 2 parts.
754 const int64_t capacity1 = capacity / 2;
755 std::vector<int64_t> usage1(num_points);
756 std::vector<Demand> demands1;
757
758 const int64_t capacity2 = capacity - capacity1;
759 std::vector<int64_t> usage2(num_points);
760 std::vector<Demand> demands2;
761
762 int usage_index = 0;
763 for (const Demand& d : demands) {
764 // Since we process demand by increasing start, the usage_index only
765 // need to increase.
766 while (usage_index < num_points && unique_starts[usage_index] < d.start) {
767 usage_index++;
768 }
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];
773
774 // We differ from the ICAPS article. If it fits in both sub-cumulatives, We
775 // choose the smallest slack. If it fits into at most one, we choose the
776 // biggest slack. If both slacks are equal, we choose randomly.
777 const bool prefer2 =
778 slack1 == slack2
779 ? absl::Bernoulli(random, 0.5)
780 : (d.height <= std::min(slack1, slack2) ? slack2 < slack1
781 : slack2 > slack1);
782
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;
788
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;
794 }
795 selected_demands.push_back(
796 {d.interval_index, d.start, d.end, assigned_to_selected});
797
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;
805 }
806 residual_demands.push_back({d.interval_index, d.start, d.end, residual});
807 }
808 }
809
810 if (demands1.size() > 1) {
811 to_process->emplace_back(std::move(demands1), capacity1);
812 }
813 if (demands2.size() > 1) {
814 to_process->emplace_back(std::move(demands2), capacity2);
815 }
816}
817
818void InsertCumulativePrecedences(
819 const absl::flat_hash_set<int>& ignored_intervals,
820 const CpSolverResponse& initial_solution, const CpModelProto& model_proto,
821 int cumulative_index, absl::BitGenRef random,
822 absl::flat_hash_set<std::pair<int, int>>* precedences) {
823 const CumulativeConstraintProto& cumulative =
824 model_proto.constraints(cumulative_index).cumulative();
825
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;
830 const ConstraintProto& interval_ct =
831 model_proto.constraints(interval_index);
832 if (!IsPresent(interval_ct, initial_solution)) continue;
833
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;
841
842 demands.push_back({interval_index, start_value, end_value, demand_value});
843 }
844 std::sort(demands.begin(), demands.end());
845
846 const int64_t capacity_value =
847 GetLinearExpressionValue(cumulative.capacity(), initial_solution);
848 DCHECK_GT(capacity_value, 0);
849
850 // Copying all these demands is memory intensive. Let's be careful here.
851 std::deque<std::pair<std::vector<Demand>, int64_t>> to_process;
852 to_process.emplace_back(std::move(demands), capacity_value);
853
854 while (!to_process.empty()) {
855 auto& next_task = to_process.front();
856 ProcessDemandListFromCumulativeConstraint(next_task.first,
857 /*capacity=*/next_task.second,
858 &to_process, random, precedences);
859 to_process.pop_front();
860 }
861}
862
863struct IndexedRectangle {
864 int interval_index;
865 Rectangle r;
866
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);
869 }
870};
871
872void InsertRectanglePredecences(
873 absl::Span<const IndexedRectangle> rectangles,
874 absl::flat_hash_set<std::pair<int, int>>* precedences) {
875 // TODO(user): Refine set of interesting points.
876 std::vector<IntegerValue> interesting_points;
877 for (const IndexedRectangle& idx_r : rectangles) {
878 interesting_points.push_back(idx_r.r.y_max - 1);
879 }
880 gtl::STLSortAndRemoveDuplicates(&interesting_points);
881 std::vector<Demand> demands;
882 for (const IntegerValue t : interesting_points) {
883 demands.clear();
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});
888 }
889 std::sort(demands.begin(), demands.end());
890 InsertPrecedencesFromSortedListOfNonOverlapingIntervals(demands,
891 precedences);
892 }
893}
894
895void InsertNoOverlap2dPrecedences(
896 const absl::flat_hash_set<int>& ignored_intervals,
897 const CpSolverResponse& initial_solution, const CpModelProto& model_proto,
898 int no_overlap_2d_index,
899 absl::flat_hash_set<std::pair<int, int>>* precedences) {
900 std::vector<Demand> demands;
901 const NoOverlap2DConstraintProto& no_overlap_2d =
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) {
906 // Ignore unperformed rectangles.
907 const int x_interval_index = no_overlap_2d.x_intervals(i);
908 if (ignored_intervals.contains(x_interval_index)) continue;
909 const ConstraintProto& x_interval_ct =
910 model_proto.constraints(x_interval_index);
911 if (!IsPresent(x_interval_ct, initial_solution)) continue;
912
913 const int y_interval_index = no_overlap_2d.y_intervals(i);
914 if (ignored_intervals.contains(y_interval_index)) continue;
915 const ConstraintProto& y_interval_ct =
916 model_proto.constraints(y_interval_index);
917 if (!IsPresent(y_interval_ct, initial_solution)) continue;
918
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);
927
928 // Ignore rectangles with zero area.
929 if (x_start_value == x_end_value || y_start_value == y_end_value) continue;
930
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}});
941 }
942
943 if (x_main.empty() || y_main.empty()) return;
944
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);
949}
950
951} // namespace
952
953// TODO(user): We could scan for model precedences and add them to the list
954// of precedences. This could enable more simplifications in the transitive
955// reduction phase.
956std::vector<std::pair<int, int>>
958 const absl::flat_hash_set<int>& ignored_intervals,
959 const CpSolverResponse& initial_solution, absl::BitGenRef random) const {
960 absl::flat_hash_set<std::pair<int, int>> precedences;
962 InsertNoOverlapPrecedences(ignored_intervals, initial_solution,
963 ModelProto(), c, &precedences);
964 }
966 InsertCumulativePrecedences(ignored_intervals, initial_solution,
967 ModelProto(), c, random, &precedences);
968 }
970 InsertNoOverlap2dPrecedences(ignored_intervals, initial_solution,
971 ModelProto(), c, &precedences);
972 }
973
974 // TODO(user): Reduce precedence graph
975 std::vector<std::pair<int, int>> result(precedences.begin(),
976 precedences.end());
977 std::sort(result.begin(), result.end());
978 return result;
979}
980
981std::vector<std::vector<int>>
983 const CpSolverResponse& initial_solution) const {
984 struct HeadAndArcBooleanVariable {
985 int head;
986 int bool_var;
987 };
988
989 std::vector<std::vector<int>> result;
990 absl::flat_hash_map<int, HeadAndArcBooleanVariable>
991 tail_to_head_and_arc_bool_var;
992
995
996 // Collect arcs.
997 int min_node = std::numeric_limits<int>::max();
998 tail_to_head_and_arc_bool_var.clear();
999 for (int i = 0; i < ct.literals_size(); ++i) {
1000 const int literal = ct.literals(i);
1001 const int head = ct.heads(i);
1002 const int tail = ct.tails(i);
1003 const int bool_var = PositiveRef(literal);
1004 const int64_t value = initial_solution.solution(bool_var);
1005 // Skip unselected arcs.
1006 if (RefIsPositive(literal) == (value == 0)) continue;
1007 // Ignore self loops.
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);
1011 }
1012 if (tail_to_head_and_arc_bool_var.empty()) continue;
1013
1014 // Unroll the path.
1015 int current_node = min_node;
1016 std::vector<int> path;
1017 do {
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));
1024 }
1025
1026 std::vector<HeadAndArcBooleanVariable> route_starts;
1027 for (const int i : TypeToConstraints(ConstraintProto::kRoutes)) {
1029 tail_to_head_and_arc_bool_var.clear();
1030 route_starts.clear();
1031
1032 // Collect route starts and arcs.
1033 for (int i = 0; i < ct.literals_size(); ++i) {
1034 const int literal = ct.literals(i);
1035 const int head = ct.heads(i);
1036 const int tail = ct.tails(i);
1037 const int bool_var = PositiveRef(literal);
1038 const int64_t value = initial_solution.solution(bool_var);
1039 // Skip unselected arcs.
1040 if (RefIsPositive(literal) == (value == 0)) continue;
1041 // Ignore self loops.
1042 if (head == tail) continue;
1043 if (tail == 0) {
1044 route_starts.push_back({head, bool_var});
1045 } else {
1046 tail_to_head_and_arc_bool_var[tail] = {head, bool_var};
1047 }
1048 }
1049
1050 // Unroll all routes.
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);
1055 do {
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));
1062 }
1063 }
1064
1065 return result;
1066}
1067
1069 const CpSolverResponse& base_solution,
1070 const Bitset64<int>& variables_to_fix) const {
1071 const int num_variables = variables_to_fix.size();
1072 Neighborhood neighborhood(num_variables);
1073 neighborhood.delta.mutable_variables()->Reserve(num_variables);
1074
1075 // TODO(user): Maybe relax all variables in the objective when the number
1076 // is small or negligible compared to the number of variables.
1077 const int unique_objective_variable =
1078 model_proto_.has_objective() && model_proto_.objective().vars_size() == 1
1079 ? model_proto_.objective().vars(0)
1080 : -1;
1081
1082 // Fill in neighborhood.delta all variable domains.
1083 int num_fixed = 0;
1084 {
1085 absl::ReaderMutexLock domain_lock(&domain_mutex_);
1086 for (int i = 0; i < num_variables; ++i) {
1087 const IntegerVariableProto& current_var =
1088 model_proto_with_only_variables_.variables(i);
1089 IntegerVariableProto* new_var = neighborhood.delta.add_variables();
1090
1091 // We only copy the name in debug mode.
1092 if (DEBUG_MODE) new_var->set_name(current_var.name());
1093
1094 if (variables_to_fix[i] && i != unique_objective_variable) {
1095 ++num_fixed;
1096
1097 // Note the use of DomainInProtoContains() instead of
1098 // ReadDomainFromProto() as the later is slower and allocate memory.
1099 const int64_t base_value = base_solution.solution(i);
1100 if (DomainInProtoContains(current_var, base_value)) {
1101 new_var->add_domain(base_value);
1102 new_var->add_domain(base_value);
1103 } else {
1104 // If under the updated domain, the base solution is no longer valid,
1105 // We should probably regenerate this neighborhood. But for now we
1106 // just do a best effort and take the closest value.
1107 const Domain domain = ReadDomainFromProto(current_var);
1108 int64_t closest_value = domain.Min();
1109 int64_t closest_dist = std::abs(closest_value - base_value);
1110 for (const ClosedInterval interval : domain) {
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;
1116 }
1117 }
1118 }
1119 FillDomainInProto(Domain(closest_value, closest_value), new_var);
1120 }
1121 } else {
1122 *new_var->mutable_domain() = current_var.domain();
1123 }
1124 }
1125 }
1126
1127 // Fill some statistic fields and detect if we cover a full component.
1128 //
1129 // TODO(user): If there is just one component, we can skip some computation.
1130 {
1131 absl::ReaderMutexLock graph_lock(&graph_mutex_);
1132 std::vector<int> count(components_.size(), 0);
1133 const int num_variables = neighborhood.delta.variables().size();
1134 for (int var = 0; var < num_variables; ++var) {
1135 const auto& domain = neighborhood.delta.variables(var).domain();
1136 if (domain.size() != 2 || domain[0] != domain[1]) {
1137 ++neighborhood.num_relaxed_variables;
1138 if (is_in_objective_[var]) {
1140 }
1141 const int c = var_to_component_index_[var];
1142 if (c != -1) count[c]++;
1143 }
1144 }
1145
1146 for (int i = 0; i < components_.size(); ++i) {
1147 if (count[i] == components_[i].size()) {
1150 components_[i].begin(), components_[i].end());
1151 }
1152 }
1153 }
1154
1155 // If the objective domain might cut the optimal solution, we cannot exploit
1156 // the connected components. We compute this outside the mutex to avoid
1157 // any deadlock risk.
1158 //
1159 // TODO(user): We could handle some complex domain (size > 2).
1160 if (model_proto_.has_objective() &&
1161 (model_proto_.objective().domain().size() != 2 ||
1162 shared_response_->GetInnerObjectiveLowerBound() <
1163 model_proto_.objective().domain(0))) {
1165 }
1166
1167 const int num_relaxed = num_variables - num_fixed;
1168 neighborhood.delta.mutable_solution_hint()->mutable_vars()->Reserve(
1169 num_relaxed);
1170 neighborhood.delta.mutable_solution_hint()->mutable_values()->Reserve(
1171 num_relaxed);
1172 AddSolutionHinting(base_solution, &neighborhood.delta);
1173
1174 neighborhood.is_generated = true;
1175 neighborhood.is_reduced = num_fixed > 0;
1176 neighborhood.is_simple = true;
1177
1178 // TODO(user): force better objective? Note that this is already done when the
1179 // hint above is successfully loaded (i.e. if it passes the presolve
1180 // correctly) since the solver will try to find better solution than the
1181 // current one.
1182 return neighborhood;
1183}
1184
1186 const CpSolverResponse& initial_solution, CpModelProto* model_proto) const {
1187 // Set the current solution as a hint.
1188 model_proto->clear_solution_hint();
1189 const auto is_fixed = [model_proto](int var) {
1190 const IntegerVariableProto& var_proto = model_proto->variables(var);
1191 return var_proto.domain_size() == 2 &&
1192 var_proto.domain(0) == var_proto.domain(1);
1193 };
1194 for (int var = 0; var < model_proto->variables_size(); ++var) {
1195 if (is_fixed(var)) continue;
1196
1197 model_proto->mutable_solution_hint()->add_vars(var);
1198 model_proto->mutable_solution_hint()->add_values(
1199 initial_solution.solution(var));
1200 }
1201}
1202
1204 const CpSolverResponse& initial_solution,
1205 absl::Span<const int> relaxed_variables) const {
1206 Bitset64<int> fixed_variables(NumVariables());
1207 {
1208 absl::ReaderMutexLock graph_lock(&graph_mutex_);
1209 for (const int i : active_variables_) {
1210 fixed_variables.Set(i);
1211 }
1212 }
1213 for (const int var : relaxed_variables) fixed_variables.Clear(var);
1214 return FixGivenVariables(initial_solution, fixed_variables);
1215}
1216
1218 const CpSolverResponse& initial_solution) const {
1219 Bitset64<int> fixed_variables(NumVariables());
1220 {
1221 absl::ReaderMutexLock graph_lock(&graph_mutex_);
1222 for (const int i : active_variables_) {
1223 fixed_variables.Set(i);
1224 }
1225 }
1226 return FixGivenVariables(initial_solution, fixed_variables);
1227}
1228
1230 CpModelProto updated_model = model_proto_;
1231 {
1232 absl::MutexLock domain_lock(&domain_mutex_);
1233 *updated_model.mutable_variables() =
1234 model_proto_with_only_variables_.variables();
1235 }
1236 return updated_model;
1237}
1238
1240 return (helper_.shared_response().SolutionsRepository().NumSolutions() > 0);
1241}
1242
1243double NeighborhoodGenerator::GetUCBScore(int64_t total_num_calls) const {
1244 absl::ReaderMutexLock mutex_lock(&generator_mutex_);
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_);
1248}
1249
1250absl::Span<const double> NeighborhoodGenerator::Synchronize() {
1251 absl::MutexLock mutex_lock(&generator_mutex_);
1252
1253 // To make the whole update process deterministic, we currently sort the
1254 // SolveData.
1255 std::sort(solve_data_.begin(), solve_data_.end());
1256
1257 // This will be used to update the difficulty of this neighborhood.
1258 int num_fully_solved_in_batch = 0;
1259 int num_not_fully_solved_in_batch = 0;
1260
1261 tmp_dtimes_.clear();
1262 for (const SolveData& data : solve_data_) {
1263 ++num_calls_;
1264
1265 // INFEASIBLE or OPTIMAL means that we "fully solved" the local problem.
1266 // If we didn't, then we cannot be sure that there is no improving solution
1267 // in that neighborhood.
1268 if (data.status == CpSolverStatus::INFEASIBLE ||
1269 data.status == CpSolverStatus::OPTIMAL) {
1270 ++num_fully_solved_calls_;
1271 ++num_fully_solved_in_batch;
1272 } else {
1273 ++num_not_fully_solved_in_batch;
1274 }
1275
1276 // It seems to make more sense to compare the new objective to the base
1277 // solution objective, not the best one. However this causes issue in the
1278 // logic below because on some problems the neighborhood can always lead
1279 // to a better "new objective" if the base solution wasn't the best one.
1280 //
1281 // This might not be a final solution, but it does work ok for now.
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;
1287 } else {
1288 ++num_consecutive_non_improving_calls_;
1289 }
1290
1291 // Confusing: this one is however comparing to the base solution objective.
1292 if (data.base_objective > data.new_objective) {
1293 ++num_improving_calls_;
1294 }
1295
1296 // TODO(user): Weight more recent data.
1297 // degrade the current average to forget old learnings.
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_;
1303 } else {
1304 current_average_ = 0.9 * current_average_ + 0.1 * gain_per_time_unit;
1305 }
1306
1307 tmp_dtimes_.push_back(data.deterministic_time);
1308 }
1309
1310 // Update the difficulty.
1311 difficulty_.Update(/*num_decreases=*/num_not_fully_solved_in_batch,
1312 /*num_increases=*/num_fully_solved_in_batch);
1313
1314 // Bump the time limit if we saw no better solution in the last few calls.
1315 // This means that as the search progress, we likely spend more and more time
1316 // trying to solve individual neighborhood.
1317 //
1318 // TODO(user): experiment with resetting the time limit if a solution is
1319 // found.
1320 if (num_consecutive_non_improving_calls_ > next_time_limit_bump_) {
1321 next_time_limit_bump_ = num_consecutive_non_improving_calls_ + 50;
1322 deterministic_limit_ *= 1.02;
1323
1324 // We do not want the limit to go to high. Intuitively, the goal is to try
1325 // out a lot of neighborhoods, not just spend a lot of time on a few.
1327 }
1328
1329 solve_data_.clear();
1330 return tmp_dtimes_;
1331}
1332
1333std::vector<int>
1335 const CpSolverResponse& initial_solution) const {
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];
1344 } else {
1345 at_best_value =
1346 initial_solution.solution(var) == domain[domain.size() - 1];
1347 }
1348 if (!at_best_value) result.push_back(var);
1349 }
1350 return result;
1351}
1352
1353namespace {
1354
1355template <class T>
1356void GetRandomSubset(double relative_size, std::vector<T>* base,
1357 absl::BitGenRef random) {
1358 if (base->empty()) return;
1359
1360 // TODO(user): we could generate this more efficiently than using random
1361 // shuffle.
1362 std::shuffle(base->begin(), base->end(), random);
1363 const int target_size = std::round(relative_size * base->size());
1364 base->resize(target_size);
1365}
1366
1367} // namespace
1368
1370 const CpSolverResponse& initial_solution, SolveData& data,
1371 absl::BitGenRef random) {
1372 std::vector<int> fixed_variables = helper_.ActiveVariables();
1373 GetRandomSubset(1.0 - data.difficulty, &fixed_variables, random);
1374
1375 Bitset64<int> to_fix(helper_.NumVariables());
1376 for (const int var : fixed_variables) to_fix.Set(var);
1377 return helper_.FixGivenVariables(initial_solution, to_fix);
1378}
1379
1381 const CpSolverResponse& initial_solution, SolveData& data,
1382 absl::BitGenRef random) {
1383 if (helper_.DifficultyMeansFullNeighborhood(data.difficulty)) {
1384 return helper_.FullNeighborhood();
1385 }
1386
1387 std::vector<int> relaxed_variables;
1388 {
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;
1394 }
1395 std::shuffle(active_constraints.begin(), active_constraints.end(), random);
1396
1397 const int num_model_vars = helper_.ModelProto().variables_size();
1398 std::vector<bool> visited_variables_set(num_model_vars, false);
1399
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();
1404 // TODO(user): Clean-up when target_size == 0.
1405
1406 for (const int constraint_index : active_constraints) {
1407 // TODO(user): randomize order of variable addition when close to the
1408 // limit.
1409 for (const int var : helper_.ConstraintToVar()[constraint_index]) {
1410 if (visited_variables_set[var]) continue;
1411 visited_variables_set[var] = true;
1412 if (helper_.IsActive(var)) {
1413 relaxed_variables.push_back(var);
1414 if (relaxed_variables.size() >= target_size) break;
1415 }
1416 }
1417 if (relaxed_variables.size() >= target_size) break;
1418 }
1419 }
1420
1421 return helper_.RelaxGivenVariables(initial_solution, relaxed_variables);
1422}
1423
1424// Note that even if difficulty means full neighborhood, we go through the
1425// generation process to never get out of a connected components.
1427 const CpSolverResponse& initial_solution, SolveData& data,
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;
1433
1434 // It is important complexity wise to never scan a constraint twice!
1435 const int num_model_constraints = helper_.ModelProto().constraints_size();
1436 std::vector<bool> scanned_constraints(num_model_constraints, false);
1437
1438 std::vector<int> random_variables;
1439 {
1440 absl::ReaderMutexLock graph_lock(&helper_.graph_mutex_);
1441
1442 std::vector<int> initial_vars =
1443 helper_.ImprovableObjectiveVariablesWhileHoldingLock(initial_solution);
1444 if (initial_vars.empty()) {
1445 initial_vars = helper_.ActiveVariablesWhileHoldingLock();
1446 }
1447 // The number of active variables can decrease asynchronously.
1448 // We read the exact number while locked.
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();
1453
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);
1459
1460 for (int i = 0; i < visited_variables.size(); ++i) {
1461 random_variables.clear();
1462 // Collect all the variables that appears in the same constraints as
1463 // visited_variables[i].
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);
1471 }
1472 }
1473 // We always randomize to change the partial subgraph explored
1474 // afterwards.
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);
1479 if (helper_.IsActive(var)) {
1480 relaxed_variables.push_back(var);
1481 }
1482 } else {
1483 break;
1484 }
1485 }
1486 if (relaxed_variables.size() >= target_size) break;
1487 }
1488 }
1489
1490 return helper_.RelaxGivenVariables(initial_solution, relaxed_variables);
1491}
1492
1493// Note that even if difficulty means full neighborhood, we go through the
1494// generation process to never get out of a connected components.
1496 const CpSolverResponse& initial_solution, SolveData& data,
1497 absl::BitGenRef random) {
1498 const int num_model_vars = helper_.ModelProto().variables_size();
1499 if (num_model_vars == 0) return helper_.NoNeighborhood();
1500
1501 // We copy the full graph var <-> constraints so that we can:
1502 // - reduce it in place
1503 // - not hold the mutex too long.
1504 // TODO(user): should we compress it or use a different representation ?
1505 CompactVectorVector<int, int> vars_to_constraints;
1506 CompactVectorVector<int, int> constraints_to_vars;
1507 int num_active_vars = 0;
1508 std::vector<int> active_objective_vars;
1509 {
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();
1516 }
1517
1518 const int target_size = std::ceil(data.difficulty * num_active_vars);
1519 if (target_size == 0) return helper_.NoNeighborhood();
1520
1521 // We pick a variable from the objective.
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)];
1526
1527 std::vector<bool> relaxed_variables_set(num_model_vars, false);
1528 std::vector<int> relaxed_variables;
1529 // Active vars are relaxed variables with some unexplored neighbors.
1530 std::vector<int> active_vars;
1531
1532 relaxed_variables_set[first_var] = true;
1533 relaxed_variables.push_back(first_var);
1534 active_vars.push_back(first_var);
1535
1536 while (relaxed_variables.size() < target_size) {
1537 if (active_vars.empty()) break; // We have exhausted our component.
1538
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];
1550
1551 // We remove the variable as it is either already relaxed, or will be
1552 // relaxed.
1553 constraints_to_vars.RemoveBySwap(ct, pos_var);
1554 if (!relaxed_variables_set[candidate]) {
1555 head_var = candidate;
1556 }
1557 }
1558 if (constraints_to_vars[ct].empty()) {
1559 // This constraint has no more un-relaxed variables.
1560 vars_to_constraints.RemoveBySwap(tail_var, pos_ct);
1561 }
1562 }
1563
1564 // Variable is no longer active ?
1565 if (vars_to_constraints[tail_var].empty()) {
1566 std::swap(active_vars[tail_index], active_vars.back());
1567 active_vars.pop_back();
1568 }
1569
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);
1574 }
1575 }
1576 return helper_.RelaxGivenVariables(initial_solution, relaxed_variables);
1577}
1578
1579// Note that even if difficulty means full neighborhood, we go through the
1580// generation process to never get out of a connected components.
1582 const CpSolverResponse& initial_solution, SolveData& data,
1583 absl::BitGenRef random) {
1584 const int num_model_constraints = helper_.ModelProto().constraints_size();
1585 if (num_model_constraints == 0) {
1586 return helper_.FullNeighborhood();
1587 }
1588
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;
1592
1593 std::vector<bool> added_constraints(num_model_constraints, false);
1594 std::vector<int> next_constraints;
1595
1596 std::vector<int> random_variables;
1597 {
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();
1603
1604 // Start from a random active constraint.
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;
1610
1611 while (relaxed_variables.size() < target_size) {
1612 // Stop if we have a full connected component.
1613 if (next_constraints.empty()) break;
1614
1615 // Pick a random unprocessed constraint.
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();
1620
1621 // Add all the variable of this constraint and increase the set of next
1622 // possible constraints.
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;
1631 if (helper_.IsActive(var)) {
1632 relaxed_variables.push_back(var);
1633 }
1634 if (relaxed_variables.size() >= target_size) break;
1635
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);
1640 }
1641 }
1642 }
1643 }
1644
1645 return helper_.RelaxGivenVariables(initial_solution, relaxed_variables);
1646}
1647
1649 const CpSolverResponse& initial_solution, SolveData& data,
1650 absl::BitGenRef random) {
1651 int max_width = 0;
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;
1656
1657 // Note(user): The algo is slower than the other graph generator, so we
1658 // might not want to lock the graph for so long? it is just a reader lock
1659 // though.
1660 {
1661 absl::ReaderMutexLock graph_lock(&helper_.graph_mutex_);
1662
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();
1667
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();
1672 }
1673
1674 // We will grow this incrementally.
1675 // Index in the graph are first variables then constraints.
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);
1679
1680 // We will process var/constraint node by minimum "score".
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;
1686 }
1687
1688 int index;
1689 int score = 0;
1690 double tie_break = 0.0;
1691 };
1692 std::vector<QueueElement> elements(num_nodes);
1694
1695 // Initialize elements.
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);
1699 }
1700
1701 // We start from a random active variable.
1702 //
1703 // Note that while num_vars contains all variables, all the fixed variables
1704 // will have no associated constraint, so we don't want to start from a
1705 // random variable.
1706 //
1707 // TODO(user): Does starting by a constraint make sense too?
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;
1714
1715 // Pop max-degree from queue and update.
1716 std::vector<int> to_update;
1717 while (!pq.IsEmpty() && relaxed_variables.size() < target_size) {
1718 // Just for logging.
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();
1722 }
1723
1724 const int index = pq.Top().index;
1725 const int score = pq.Top().score;
1726 pq.Pop();
1727 added[index] = true;
1728
1729 // When the score is zero, we don't need to update anything since the
1730 // frontier does not grow.
1731 if (score == 0) {
1732 if (index < num_vars) relaxed_variables.push_back(index);
1733 ++num_zero_score;
1734 continue;
1735 }
1736
1737 // Note that while it might looks bad, the overall complexity of this is
1738 // in O(num_edge) since we scan each index once and each newly connected
1739 // vertex once.
1740 int num_added = 0;
1741 to_update.clear();
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;
1747 ++num_added;
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--;
1755 } else {
1756 elements[c_index].score++;
1757 }
1758 }
1759 }
1760 } else {
1761 for (const int v : helper_.ConstraintToVar()[index - num_vars]) {
1762 if (added_or_connected[v]) continue;
1763 ++num_added;
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);
1771 } else {
1772 elements[v].score++;
1773 }
1774 }
1775 }
1776 }
1777
1778 // The score is exactly the frontier increase in size.
1779 // This is the same as the min-degree heuristic for the elimination order.
1780 // Except we only consider connected nodes.
1781 CHECK_EQ(num_added, score);
1782
1784 for (const int index : to_update) {
1785 DCHECK(!added[index]);
1786 if (pq.Contains(index)) {
1787 pq.ChangePriority(elements[index]);
1788 } else {
1789 pq.Add(elements[index]);
1790 }
1791 }
1792
1793 max_width = std::max(max_width, pq.Size());
1794 }
1795
1796 // Just for logging.
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();
1800 }
1801
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();
1807 }
1808
1809 return helper_.RelaxGivenVariables(initial_solution, relaxed_variables);
1810}
1811
1812namespace {
1813
1814// Create a constraint sum (X - LB) + sum (UB - X) <= rhs.
1815ConstraintProto DistanceToBoundsSmallerThanConstraint(
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) {
1819 DCHECK_GE(rhs, 0);
1820 ConstraintProto new_constraint;
1821 LinearConstraintProto* linear = new_constraint.mutable_linear();
1822 int64_t lhs_constant_value = 0;
1823 for (const auto [var, lb] : dist_to_lower_bound) {
1824 // We add X - LB
1825 linear->add_coeffs(1);
1826 linear->add_vars(var);
1827 lhs_constant_value -= lb;
1828 }
1829 for (const auto [var, ub] : dist_to_upper_bound) {
1830 // We add UB - X
1831 lhs_constant_value += ub;
1832 linear->add_coeffs(-1);
1833 linear->add_vars(var);
1834 }
1835 linear->add_domain(std::numeric_limits<int64_t>::min());
1836 linear->add_domain(rhs - lhs_constant_value);
1837 return new_constraint;
1838}
1839
1840} // namespace
1841
1843 const CpSolverResponse& initial_solution, SolveData& data,
1844 absl::BitGenRef random) {
1845 const std::vector<int> active_variables = helper_.ActiveVariables();
1846 if (active_variables.empty()) return helper_.NoNeighborhood();
1847
1848 {
1849 // Quick corner case in case the difficulty is too high. This is mainly
1850 // useful when testing with only that kind of LNS to abort early on
1851 // super-easy problems.
1852 const int size = active_variables.size();
1853 if (static_cast<int>(std::ceil(data.difficulty * size)) == size) {
1854 return helper_.FullNeighborhood();
1855 }
1856 }
1857
1858 // These are candidate for relaxation. The score will be filled later. Active
1859 // variable not kept in candidate will be added to other_variables.
1860 std::vector<std::pair<int, double>> candidates_with_score;
1861 std::vector<int> other_variables;
1862
1863 // Our extra relaxation constraint will be: sums of distance to the respective
1864 // bound smaller than a constant that depends on the difficulty.
1865 std::vector<std::pair<int, int64_t>> dist_to_lower_bound;
1866 std::vector<std::pair<int, int64_t>> dist_to_upper_bound;
1867
1868 // For the "easy" part of the extra constraint, we either look only at the
1869 // binary variables. Or we extend that to all variables at their bound.
1870 const bool only_look_at_binary = absl::Bernoulli(random, 0.5);
1871
1872 // We copy the model early to have access to reduced domains.
1873 // TODO(user): that might not be the most efficient if we abort just below.
1874 CpModelProto local_cp_model = helper_.UpdatedModelProtoCopy();
1875
1876 // Loop over active variables.
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());
1881 const IntegerVariableProto& var_proto = local_cp_model.variables(var);
1882 const int64_t base_value = initial_solution.solution(var);
1883 const bool is_binary = var_proto.domain_size() == 2 &&
1884 var_proto.domain(0) == 0 && var_proto.domain(1) == 1;
1885 if (only_look_at_binary && !is_binary) {
1886 other_variables.push_back(var);
1887 continue;
1888 }
1889
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});
1901 } else {
1902 other_variables.push_back(var);
1903 }
1904 }
1905
1906 bool use_hamming_for_others = false;
1907 if (!other_variables.empty() && absl::Bernoulli(random, 0.5)) {
1908 use_hamming_for_others = true;
1909 }
1910 if (!use_hamming_for_others && candidates_with_score.empty()) {
1911 return helper_.NoNeighborhood();
1912 }
1913
1914 // With this option, we will create a bunch of Boolean variable
1915 // and add the constraints : "bool==0 => var == value_in_base_solution".
1916 if (use_hamming_for_others) {
1917 for (const int var : other_variables) {
1918 const int indicator = local_cp_model.variables().size();
1919 auto* var_proto = local_cp_model.add_variables();
1920 var_proto->add_domain(0);
1921 var_proto->add_domain(1);
1922 auto* new_ct = local_cp_model.add_constraints();
1923 new_ct->add_enforcement_literal(NegatedRef(indicator));
1924
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);
1930
1931 // Add it to the distance constraint.
1932 dist_to_lower_bound.push_back({indicator, 0});
1933 candidates_with_score.push_back({var, 0.0});
1934 }
1935
1936 // Clear other_variables so that they are not added at the end.
1937 other_variables.clear();
1938 }
1939
1940 // Constrain the distance to the bounds.
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);
1946
1947 Model model("lb_relax_lns_lp");
1948 auto* const params = model.GetOrCreate<SatParameters>();
1949
1950 // Parameters to enable solving the LP only.
1951 params->set_num_workers(1);
1952 params->set_linearization_level(2);
1953 params->set_stop_after_root_propagation(true);
1954 params->set_add_lp_constraints_lazily(false);
1955
1956 // Parameters to attempt to speed up solve.
1957 params->set_cp_model_presolve(false);
1958 params->set_cp_model_probing_level(0);
1959
1960 // Parameters to limit time spent in the solve. The max number of iterations
1961 // is relaxed from the default since we rely more on deterministic time.
1962 params->set_root_lp_iterations(100000);
1963
1964 // TODO(user): This is a lot longer than a normal LNS, so it might cause
1965 // issue with the current round-robbin selection based on number of calls.
1966 params->set_max_deterministic_time(10);
1967 model.GetOrCreate<TimeLimit>()->ResetLimitFromParameters(*params);
1968 if (global_time_limit_ != nullptr) {
1969 global_time_limit_->UpdateLocalLimit(model.GetOrCreate<TimeLimit>());
1970 }
1971
1972 // Tricky: we want the inner_objective_lower_bound in the response to be in
1973 // term of the current problem, not the user facing one.
1974 if (local_cp_model.has_objective()) {
1975 local_cp_model.mutable_objective()->set_integer_before_offset(0);
1976 local_cp_model.mutable_objective()->set_integer_after_offset(0);
1977 local_cp_model.mutable_objective()->set_integer_scaling_factor(0);
1978 }
1979
1980 // Dump?
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 << "'.";
1986 CHECK(WriteModelProtoToFile(local_cp_model, dump_name));
1987 }
1988
1989 // Solve.
1990 //
1991 // TODO(user): Shall we pass the objective upper bound so we have more
1992 // chance to fix variable via reduced cost fixing.
1993 //
1994 // TODO(user): Does the current solution can provide a warm-start for the
1995 // LP?
1996 auto* response_manager = model.GetOrCreate<SharedResponseManager>();
1997 {
1998 response_manager->InitializeObjective(local_cp_model);
1999 LoadCpModel(local_cp_model, &model);
2000 SolveLoadedCpModel(local_cp_model, &model);
2001 }
2002
2003 // Update dtime.
2004 data.deterministic_time +=
2005 model.GetOrCreate<TimeLimit>()->GetElapsedDeterministicTime();
2006
2007 // Analyze the status of this first "solve".
2008 //
2009 // TODO(user): If we run into this case, it also means that every other LNS
2010 // that tries to more variable than here will never be able to improve.
2011 if (local_cp_model.has_objective()) {
2012 const CpSolverResponse response = response_manager->GetResponse();
2013 if (response.status() == CpSolverStatus::INFEASIBLE) {
2015 AddSolveData(data);
2016 return helper_.NoNeighborhood();
2017 }
2018
2019 const int64_t inner_lb = response.inner_objective_lower_bound();
2020 const int64_t current_inner_obj = ComputeInnerObjective(
2021 local_cp_model.objective(), initial_solution.solution());
2022 if (inner_lb >= current_inner_obj) {
2023 // In this case, we cannot improve on the base solution.
2024 // We could try to find a different solution for diversity, but we do have
2025 // other neighborhood for that. Lets abort early.
2026 data.status = CpSolverStatus::OPTIMAL; // We cannot improve.
2027 AddSolveData(data);
2028 return helper_.NoNeighborhood();
2029 }
2030 }
2031
2032 // Compute differences between LP solution and initial solution, with a small
2033 // random noise for tie breaking.
2034 const auto var_mapping = model.GetOrCreate<CpModelMapping>();
2035 const auto lp_solution = model.GetOrCreate<ModelLpValues>();
2036 if (lp_solution->empty()) {
2037 // We likely didn't solve the LP at all, so lets not use this neighborhood.
2038 return helper_.NoNeighborhood();
2039 }
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)) -
2046 initial_solution.solution(var));
2047 score = difference + absl::Uniform<double>(random, 0.0, 1e-6);
2048 }
2049
2050 // Take the target_size variables with largest differences.
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;
2054 });
2055
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);
2061 }
2062
2063 // We will also relax all "other variables". We assume their values are likely
2064 // tied to the other ones.
2065 vars_to_relax.insert(vars_to_relax.end(), other_variables.begin(),
2066 other_variables.end());
2067 Neighborhood result =
2068 helper_.RelaxGivenVariables(initial_solution, vars_to_relax);
2069
2070 // Lets the name reflect the type.
2071 //
2072 // TODO(user): Unfortunately like this we have a common difficulty for all
2073 // variant, we should probably fix that.
2074 result.source_info = "lb_relax_lns";
2075 absl::StrAppend(&result.source_info,
2076 some_non_binary_at_bound ? "_int" : "_bool");
2077 if (use_hamming_for_others) {
2078 absl::StrAppend(&result.source_info, "_h");
2079 }
2080
2081 return result;
2082}
2083
2084namespace {
2085
2086void AddPrecedence(const LinearExpressionProto& before,
2087 const LinearExpressionProto& after, CpModelProto* model) {
2089 linear->add_domain(std::numeric_limits<int64_t>::min());
2090 linear->add_domain(after.offset() - before.offset());
2091 for (int i = 0; i < before.vars_size(); ++i) {
2092 linear->add_vars(before.vars(i));
2093 linear->add_coeffs(before.coeffs(i));
2094 }
2095 for (int i = 0; i < after.vars_size(); ++i) {
2096 linear->add_vars(after.vars(i));
2097 linear->add_coeffs(-after.coeffs(i));
2098 }
2099}
2100
2101} // namespace
2102
2104 const absl::Span<const std::pair<int, int>> precedences,
2105 const CpSolverResponse& initial_solution,
2106 const NeighborhoodGeneratorHelper& helper) {
2107 Neighborhood neighborhood = helper.FullNeighborhood();
2108
2109 neighborhood.is_reduced = !precedences.empty();
2110 if (!neighborhood.is_reduced) { // Returns the full neighborhood.
2111 helper.AddSolutionHinting(initial_solution, &neighborhood.delta);
2112 neighborhood.is_generated = true;
2113 return neighborhood;
2114 }
2115
2116 // Collect seen intervals.
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);
2121 }
2122
2123 // Fix the presence/absence of unseen intervals.
2124 bool enforcement_literals_fixed = false;
2125 for (const int i : helper.TypeToConstraints(ConstraintProto::kInterval)) {
2126 if (seen_intervals.contains(i)) continue;
2127
2128 const ConstraintProto& interval_ct = helper.ModelProto().constraints(i);
2129 if (interval_ct.enforcement_literal().empty()) continue;
2130
2131 DCHECK_EQ(interval_ct.enforcement_literal().size(), 1);
2132 const int enforcement_ref = interval_ct.enforcement_literal(0);
2133 const int enforcement_var = PositiveRef(enforcement_ref);
2134 const int value = initial_solution.solution(enforcement_var);
2135
2136 // If the interval is not enforced, we just relax it. If it belongs to an
2137 // exactly one constraint, and the enforced interval is not relaxed, then
2138 // propagation will force this interval to stay not enforced. Otherwise,
2139 // LNS will be able to change which interval will be enforced among all
2140 // alternatives.
2141 if (RefIsPositive(enforcement_ref) == (value == 0)) continue;
2142
2143 // Fix the value.
2144 neighborhood.delta.mutable_variables(enforcement_var)->clear_domain();
2145 neighborhood.delta.mutable_variables(enforcement_var)->add_domain(value);
2146 neighborhood.delta.mutable_variables(enforcement_var)->add_domain(value);
2147 enforcement_literals_fixed = true;
2148 }
2149
2150 for (const std::pair<int, int>& prec : precedences) {
2151 const LinearExpressionProto& before_end =
2152 helper.ModelProto().constraints(prec.first).interval().end();
2153 const LinearExpressionProto& after_start =
2154 helper.ModelProto().constraints(prec.second).interval().start();
2155 DCHECK_LE(GetLinearExpressionValue(before_end, initial_solution),
2156 GetLinearExpressionValue(after_start, initial_solution));
2157 AddPrecedence(before_end, after_start, &neighborhood.delta);
2158 }
2159
2160 // Set the current solution as a hint.
2161 helper.AddSolutionHinting(initial_solution, &neighborhood.delta);
2162 neighborhood.is_generated = true;
2163
2164 return neighborhood;
2165}
2166
2168 absl::Span<const int> intervals_to_relax,
2169 absl::Span<const int> variables_to_fix,
2170 const CpSolverResponse& initial_solution, absl::BitGenRef random,
2171 const NeighborhoodGeneratorHelper& helper) {
2172 Neighborhood neighborhood = helper.FullNeighborhood();
2173
2174 // We will extend the set with some interval that we cannot fix.
2175 absl::flat_hash_set<int> ignored_intervals(intervals_to_relax.begin(),
2176 intervals_to_relax.end());
2177
2178 // Fix the presence/absence of non-relaxed intervals.
2179 for (const int i : helper.TypeToConstraints(ConstraintProto::kInterval)) {
2180 DCHECK_GE(i, 0);
2181 if (ignored_intervals.contains(i)) continue;
2182
2183 const ConstraintProto& interval_ct = helper.ModelProto().constraints(i);
2184 if (interval_ct.enforcement_literal().empty()) continue;
2185
2186 DCHECK_EQ(interval_ct.enforcement_literal().size(), 1);
2187 const int enforcement_ref = interval_ct.enforcement_literal(0);
2188 const int enforcement_var = PositiveRef(enforcement_ref);
2189 const int value = initial_solution.solution(enforcement_var);
2190
2191 // If the interval is not enforced, we just relax it. If it belongs to an
2192 // exactly one constraint, and the enforced interval is not relaxed, then
2193 // propagation will force this interval to stay not enforced. Otherwise,
2194 // LNS will be able to change which interval will be enforced among all
2195 // alternatives.
2196 if (RefIsPositive(enforcement_ref) == (value == 0)) {
2197 ignored_intervals.insert(i);
2198 continue;
2199 }
2200
2201 // Fix the value.
2202 neighborhood.delta.mutable_variables(enforcement_var)->clear_domain();
2203 neighborhood.delta.mutable_variables(enforcement_var)->add_domain(value);
2204 neighborhood.delta.mutable_variables(enforcement_var)->add_domain(value);
2205 }
2206
2207 if (ignored_intervals.size() >=
2209 .size()) { // Returns the full neighborhood.
2210 helper.AddSolutionHinting(initial_solution, &neighborhood.delta);
2211 neighborhood.is_generated = true;
2212 return neighborhood;
2213 }
2214
2215 neighborhood.is_reduced = true;
2216
2217 // We differ from the ICAPS05 paper as we do not consider ignored intervals
2218 // when generating the precedence graph, instead of building the full graph,
2219 // then removing intervals, and reconstructing the precedence graph
2220 // heuristically after that.
2221 const std::vector<std::pair<int, int>> precedences =
2222 helper.GetSchedulingPrecedences(ignored_intervals, initial_solution,
2223 random);
2224 for (const std::pair<int, int>& prec : precedences) {
2225 const LinearExpressionProto& before_end =
2226 helper.ModelProto().constraints(prec.first).interval().end();
2227 const LinearExpressionProto& after_start =
2228 helper.ModelProto().constraints(prec.second).interval().start();
2229 DCHECK_LE(GetLinearExpressionValue(before_end, initial_solution),
2230 GetLinearExpressionValue(after_start, initial_solution));
2231 AddPrecedence(before_end, after_start, &neighborhood.delta);
2232 }
2233
2234 // fix the extra variables passed as parameters.
2235 for (const int var : variables_to_fix) {
2236 const int value = initial_solution.solution(var);
2237 neighborhood.delta.mutable_variables(var)->clear_domain();
2238 neighborhood.delta.mutable_variables(var)->add_domain(value);
2239 neighborhood.delta.mutable_variables(var)->add_domain(value);
2240 }
2241
2242 // Set the current solution as a hint.
2243 helper.AddSolutionHinting(initial_solution, &neighborhood.delta);
2244 neighborhood.is_generated = true;
2245
2246 return neighborhood;
2247}
2248
2250 const CpSolverResponse& initial_solution, SolveData& data,
2251 absl::BitGenRef random) {
2252 std::vector<int> intervals_to_relax =
2253 helper_.GetActiveIntervals(initial_solution);
2254 GetRandomSubset(data.difficulty, &intervals_to_relax, random);
2255
2257 intervals_to_relax, {}, initial_solution, random, helper_);
2258}
2259
2261 const CpSolverResponse& initial_solution, SolveData& data,
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_);
2268}
2269
2270namespace {
2271void AppendVarsFromAllIntervalIndices(absl::Span<const int> indices,
2272 absl::Span<const int> all_intervals,
2273 const CpModelProto& model_proto,
2274 std::vector<int>* variables) {
2275 for (const int index : indices) {
2276 const std::vector<int> vars =
2277 UsedVariables(model_proto.constraints(all_intervals[index]));
2278 variables->insert(variables->end(), vars.begin(), vars.end());
2279 }
2280}
2281} // namespace
2282
2284 const CpSolverResponse& initial_solution, SolveData& data,
2285 absl::BitGenRef random) {
2286 const std::vector<int> active_intervals =
2287 helper_.GetActiveIntervals(initial_solution);
2288
2289 if (active_intervals.empty()) return helper_.FullNeighborhood();
2290
2291 const TimePartition partition = PartitionIndicesAroundRandomTimeWindow(
2292 active_intervals, helper_.ModelProto(), initial_solution, data.difficulty,
2293 random);
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());
2300
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(),
2307 &variables_to_fix);
2308 }
2309
2310 gtl::STLSortAndRemoveDuplicates(&intervals_to_relax);
2311 gtl::STLSortAndRemoveDuplicates(&variables_to_fix);
2313 intervals_to_relax, variables_to_fix, initial_solution, random, helper_);
2314}
2315
2317 const CpSolverResponse& initial_solution, SolveData& data,
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,
2326 data.difficulty, random);
2327 intervals_to_relax.insert(intervals_to_relax.end(),
2328 partition.selected_indices.begin(),
2329 partition.selected_indices.end());
2330
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(),
2337 &variables_to_fix);
2338 }
2339 }
2340
2341 if (intervals_to_relax.empty() && variables_to_fix.empty()) {
2342 return helper_.FullNeighborhood();
2343 }
2344
2345 gtl::STLSortAndRemoveDuplicates(&intervals_to_relax);
2346 gtl::STLSortAndRemoveDuplicates(&variables_to_fix);
2348 intervals_to_relax, variables_to_fix, initial_solution, random, helper_);
2349}
2350
2352 const CpSolverResponse& initial_solution, SolveData& data,
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);
2357
2358 Bitset64<int> variables_to_freeze(helper_.NumVariables());
2359 for (const ActiveRectangle& rectangle : rectangles_to_freeze) {
2360 InsertVariablesFromInterval(helper_.ModelProto(), rectangle.x_interval,
2361 variables_to_freeze);
2362 InsertVariablesFromInterval(helper_.ModelProto(), rectangle.y_interval,
2363 variables_to_freeze);
2364 }
2365 return helper_.FixGivenVariables(initial_solution, variables_to_freeze);
2366}
2367
2369 const CpSolverResponse& initial_solution, SolveData& data,
2370 absl::BitGenRef random) {
2371 // First pick one rectangle.
2372 const std::vector<ActiveRectangle> all_active_rectangles =
2373 helper_.GetActiveRectangles(initial_solution);
2374 if (all_active_rectangles.size() <= 1) return helper_.FullNeighborhood();
2375
2376 const ActiveRectangle& base_rectangle =
2377 all_active_rectangles[absl::Uniform<int>(random, 0,
2378 all_active_rectangles.size())];
2379
2380 const auto get_rectangle = [&initial_solution, helper = &helper_](
2381 const ActiveRectangle& rectangle) {
2382 const int x_interval_idx = rectangle.x_interval;
2383 const int y_interval_idx = rectangle.y_interval;
2384 const ConstraintProto& x_interval_ct =
2385 helper->ModelProto().constraints(x_interval_idx);
2386 const ConstraintProto& y_interval_ct =
2387 helper->ModelProto().constraints(y_interval_idx);
2388 return Rectangle{.x_min = GetLinearExpressionValue(
2389 x_interval_ct.interval().start(), initial_solution),
2390 .x_max = GetLinearExpressionValue(
2391 x_interval_ct.interval().end(), initial_solution),
2392 .y_min = GetLinearExpressionValue(
2393 y_interval_ct.interval().start(), initial_solution),
2394 .y_max = GetLinearExpressionValue(
2395 y_interval_ct.interval().end(), initial_solution)};
2396 };
2397
2398 const Rectangle center_rect = get_rectangle(base_rectangle);
2399
2400 // Now compute a neighborhood around that rectangle. In this neighborhood
2401 // we prefer a "Square" region around the initial rectangle center rather than
2402 // a circle.
2403 //
2404 // Note that we only consider two rectangles as potential neighbors if they
2405 // are part of the same no_overlap_2d constraint.
2406 Bitset64<int> variables_to_freeze(helper_.NumVariables());
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) {
2410 const ActiveRectangle& rectangle = all_active_rectangles[i];
2411 InsertVariablesFromInterval(helper_.ModelProto(), rectangle.x_interval,
2412 variables_to_freeze);
2413 InsertVariablesFromInterval(helper_.ModelProto(), rectangle.y_interval,
2414 variables_to_freeze);
2415
2416 const Rectangle rect = get_rectangle(rectangle);
2417 const bool same_no_overlap_as_center_rect = absl::c_any_of(
2418 base_rectangle.no_overlap_2d_constraints, [&rectangle](const int c) {
2419 return rectangle.no_overlap_2d_constraints.contains(c);
2420 });
2421 if (same_no_overlap_as_center_rect) {
2422 distances.push_back(
2423 {i, CenterToCenterLInfinityDistance(center_rect, rect)});
2424 }
2425 }
2426 std::stable_sort(
2427 distances.begin(), distances.end(),
2428 [](const auto& a, const auto& b) { return a.second < b.second; });
2429
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);
2439 }
2440
2441 // Heuristic: we relax a bit the bounding box in order to allow some
2442 // movements, this is needed to not have a trivial neighborhood if we relax a
2443 // single box for instance.
2444 const IntegerValue x_size = relaxed_bounding_box.SizeX();
2445 const IntegerValue y_size = relaxed_bounding_box.SizeY();
2446 relaxed_bounding_box.x_min = CapSubI(relaxed_bounding_box.x_min, x_size / 2);
2447 relaxed_bounding_box.x_max = CapAddI(relaxed_bounding_box.x_max, x_size / 2);
2448 relaxed_bounding_box.y_min = CapSubI(relaxed_bounding_box.y_min, y_size / 2);
2449 relaxed_bounding_box.y_max = CapAddI(relaxed_bounding_box.y_max, y_size / 2);
2450
2451 for (const int b : boxes_to_relax) {
2452 const ActiveRectangle& rectangle = all_active_rectangles[b];
2453 RemoveVariablesFromInterval(helper_.ModelProto(), rectangle.x_interval,
2454 variables_to_freeze);
2455 RemoveVariablesFromInterval(helper_.ModelProto(), rectangle.y_interval,
2456 variables_to_freeze);
2457 }
2458 Neighborhood neighborhood =
2459 helper_.FixGivenVariables(initial_solution, variables_to_freeze);
2460
2461 neighborhood.is_simple = false;
2462 neighborhood.is_reduced = true;
2464
2465 // The call above add the relaxed variables to the neighborhood using the
2466 // current bounds at level 0. For big problems, this might create a hard model
2467 // with a large complicated landscape of fixed boxes with a lot of potential
2468 // places to place the relaxed boxes. Therefore we update the domain so the
2469 // boxes can only stay around the area we decided to relax.
2470 for (const int b : boxes_to_relax) {
2471 {
2472 const IntervalConstraintProto& x_interval =
2473 helper_.ModelProto()
2474 .constraints(all_active_rectangles[b].x_interval)
2475 .interval();
2476 const Domain x_domain = Domain(relaxed_bounding_box.x_min.value(),
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);
2481 }
2482 {
2483 const IntervalConstraintProto& y_interval =
2484 helper_.ModelProto()
2485 .constraints(all_active_rectangles[b].y_interval)
2486 .interval();
2487 const Domain y_domain = Domain(relaxed_bounding_box.y_min.value(),
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);
2492 }
2493 }
2494 return neighborhood;
2495}
2496
2498 const CpSolverResponse& initial_solution, SolveData& data,
2499 absl::BitGenRef random) {
2500 // First pick a pair of rectangles.
2501 std::vector<ActiveRectangle> all_active_rectangles =
2502 helper_.GetActiveRectangles(initial_solution);
2503 if (all_active_rectangles.size() <= 2) return helper_.FullNeighborhood();
2504
2505 const int first_idx =
2506 absl::Uniform<int>(random, 0, all_active_rectangles.size());
2507 int second_idx =
2508 absl::Uniform<int>(random, 0, all_active_rectangles.size() - 1);
2509 if (second_idx >= first_idx) {
2510 second_idx++;
2511 }
2512
2513 const ActiveRectangle& chosen_rectangle_1 = all_active_rectangles[first_idx];
2514 const ActiveRectangle& chosen_rectangle_2 = all_active_rectangles[second_idx];
2515
2516 const auto get_rectangle = [&initial_solution, helper = &helper_](
2517 const ActiveRectangle& rectangle) {
2518 const int x_interval_idx = rectangle.x_interval;
2519 const int y_interval_idx = rectangle.y_interval;
2520 const ConstraintProto& x_interval_ct =
2521 helper->ModelProto().constraints(x_interval_idx);
2522 const ConstraintProto& y_interval_ct =
2523 helper->ModelProto().constraints(y_interval_idx);
2524 return Rectangle{.x_min = GetLinearExpressionValue(
2525 x_interval_ct.interval().start(), initial_solution),
2526 .x_max = GetLinearExpressionValue(
2527 x_interval_ct.interval().end(), initial_solution),
2528 .y_min = GetLinearExpressionValue(
2529 y_interval_ct.interval().start(), initial_solution),
2530 .y_max = GetLinearExpressionValue(
2531 y_interval_ct.interval().end(), initial_solution)};
2532 };
2533
2534 const Rectangle rect1 = get_rectangle(chosen_rectangle_1);
2535 const Rectangle rect2 = get_rectangle(chosen_rectangle_2);
2536
2537 // Now compute a neighborhood around each rectangle. Note that we only
2538 // consider two rectangles as potential neighbors if they are part of the same
2539 // no_overlap_2d constraint.
2540 //
2541 // TODO(user): This computes the distance between the center of the
2542 // rectangles. We could use the real distance between the closest points, but
2543 // not sure it is worth the extra complexity.
2544 Bitset64<int> variables_to_freeze(helper_.NumVariables());
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) {
2550 const ActiveRectangle& rectangle = all_active_rectangles[i];
2551 InsertVariablesFromInterval(helper_.ModelProto(), rectangle.x_interval,
2552 variables_to_freeze);
2553 InsertVariablesFromInterval(helper_.ModelProto(), rectangle.y_interval,
2554 variables_to_freeze);
2555
2556 const Rectangle rect = get_rectangle(rectangle);
2557 const bool same_no_overlap_as_rect1 =
2558 absl::c_any_of(chosen_rectangle_1.no_overlap_2d_constraints,
2559 [&rectangle](const int c) {
2560 return rectangle.no_overlap_2d_constraints.contains(c);
2561 });
2562 const bool same_no_overlap_as_rect2 =
2563 absl::c_any_of(chosen_rectangle_2.no_overlap_2d_constraints,
2564 [&rectangle](const int c) {
2565 return rectangle.no_overlap_2d_constraints.contains(c);
2566 });
2567 if (same_no_overlap_as_rect1) {
2568 distances1.push_back({i, CenterToCenterL2Distance(rect1, rect)});
2569 }
2570 if (same_no_overlap_as_rect2) {
2571 distances2.push_back({i, CenterToCenterL2Distance(rect2, rect)});
2572 }
2573 }
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);
2583 ++i) {
2584 const int rectangle_idx = samples[i].first;
2585 const ActiveRectangle& rectangle = all_active_rectangles[rectangle_idx];
2586 RemoveVariablesFromInterval(helper_.ModelProto(), rectangle.x_interval,
2587 variables_to_freeze);
2588 RemoveVariablesFromInterval(helper_.ModelProto(), rectangle.y_interval,
2589 variables_to_freeze);
2590 }
2591 }
2592
2593 return helper_.FixGivenVariables(initial_solution, variables_to_freeze);
2594}
2595
2597 const CpSolverResponse& initial_solution, SolveData& data,
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;
2603 for (const ActiveRectangle& rect : rectangles_to_relax) {
2604 intervals_to_relax.push_back(rect.x_interval);
2605 intervals_to_relax.push_back(rect.y_interval);
2606 }
2607 gtl::STLSortAndRemoveDuplicates(&intervals_to_relax);
2608
2610 intervals_to_relax, {}, initial_solution, random, helper_);
2611}
2612
2614 const CpSolverResponse& initial_solution, SolveData& data,
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());
2621 for (const ActiveRectangle& rect : active_rectangles) {
2622 projected_intervals.push_back(use_first_dimension ? rect.x_interval
2623 : rect.y_interval);
2624 }
2625
2626 const TimePartition partition = PartitionIndicesAroundRandomTimeWindow(
2627 projected_intervals, helper_.ModelProto(), initial_solution,
2628 data.difficulty, random);
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;
2632 }
2633
2634 Bitset64<int> variables_to_freeze(helper_.NumVariables());
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);
2643 }
2644 }
2645
2646 return helper_.FixGivenVariables(initial_solution, variables_to_freeze);
2647}
2648
2650 const CpSolverResponse& initial_solution, SolveData& data,
2651 absl::BitGenRef random) {
2652 const std::vector<std::vector<int>> all_paths =
2653 helper_.GetRoutingPathBooleanVariables(initial_solution);
2654
2655 // Collect all unique variables.
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());
2659 }
2660 gtl::STLSortAndRemoveDuplicates(&variables_to_fix);
2661 GetRandomSubset(1.0 - data.difficulty, &variables_to_fix, random);
2662
2663 Bitset64<int> to_fix(helper_.NumVariables());
2664 for (const int var : variables_to_fix) to_fix.Set(var);
2665 return helper_.FixGivenVariables(initial_solution, to_fix);
2666}
2667
2669 const CpSolverResponse& initial_solution, SolveData& data,
2670 absl::BitGenRef random) {
2671 std::vector<std::vector<int>> all_paths =
2672 helper_.GetRoutingPathBooleanVariables(initial_solution);
2673
2674 // Remove a corner case where all paths are empty.
2675 if (all_paths.empty()) {
2676 return helper_.NoNeighborhood();
2677 }
2678
2679 // Collect all unique variables.
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();
2684 }
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(),
2688 path.end());
2689 }
2690 gtl::STLSortAndRemoveDuplicates(&all_path_variables);
2691
2692 // Select target number of variables to relax.
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;
2696
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]);
2708 }
2709
2710 // Remove segment and clean up empty paths.
2711 path.erase(path.begin() + segment_start,
2712 path.begin() + segment_start + segment_length);
2713 if (path.empty()) {
2714 std::swap(all_paths[path_index], all_paths.back());
2715 all_paths.pop_back();
2716 }
2717 }
2718
2719 // Compute the set of variables to fix.
2720 Bitset64<int> to_fix(helper_.NumVariables());
2721 for (const int var : all_path_variables) {
2722 if (!relaxed_variables.contains(var)) to_fix.Set(var);
2723 }
2724 return helper_.FixGivenVariables(initial_solution, to_fix);
2725}
2726
2728 const CpSolverResponse& initial_solution, SolveData& data,
2729 absl::BitGenRef random) {
2730 std::vector<std::vector<int>> all_paths =
2731 helper_.GetRoutingPathBooleanVariables(initial_solution);
2732
2733 // Remove a corner case where all paths are empty.
2734 if (all_paths.empty()) {
2735 return helper_.NoNeighborhood();
2736 }
2737
2738 // Collect all unique variables.
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();
2743 }
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(),
2747 path.end());
2748 }
2749 gtl::STLSortAndRemoveDuplicates(&all_path_variables);
2750
2751 // Select target number of variables to relax.
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;
2755
2756 // Relax the start and end of each path to ease relocation.
2757 // TODO(user): Restrict this if the difficulty is very low.
2758 for (const auto& path : all_paths) {
2759 relaxed_variables.insert(path.front());
2760 relaxed_variables.insert(path.back());
2761 }
2762
2763 // Relax all variables, if possible, of one random path.
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(),
2766 random);
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();
2771 }
2772
2773 // Relax more variables until the target is reached.
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();
2779 }
2780 }
2781
2782 // Compute the set of variables to fix.
2783 Bitset64<int> to_fix(helper_.NumVariables());
2784 for (const int var : all_path_variables) {
2785 if (!relaxed_variables.contains(var)) to_fix.Set(var);
2786 }
2787 return helper_.FixGivenVariables(initial_solution, to_fix);
2788}
2789
2791 return (incomplete_solutions_->HasSolution() ||
2792 lp_solutions_->NumSolutions() > 0);
2793}
2794
2796 const CpSolverResponse& /*initial_solution*/, SolveData& data,
2797 absl::BitGenRef random) {
2798 Neighborhood neighborhood = helper_.FullNeighborhood();
2799 neighborhood.is_generated = false;
2800
2801 const ReducedDomainNeighborhood reduced_domains =
2802 GetRinsRensNeighborhood(response_manager_, lp_solutions_,
2803 incomplete_solutions_, data.difficulty, random);
2804
2805 if (reduced_domains.fixed_vars.empty() &&
2806 reduced_domains.reduced_domain_vars.empty()) {
2807 return neighborhood;
2808 }
2809 neighborhood.source_info = reduced_domains.source_info;
2810
2811 absl::ReaderMutexLock graph_lock(&helper_.graph_mutex_);
2812 // Fix the variables in the local model.
2813 for (const std::pair</*model_var*/ int, /*value*/ int64_t>& fixed_var :
2814 reduced_domains.fixed_vars) {
2815 const int var = fixed_var.first;
2816 const int64_t value = fixed_var.second;
2817 if (var >= neighborhood.delta.variables_size()) continue;
2818 if (!helper_.IsActive(var)) continue;
2819
2820 if (!DomainInProtoContains(neighborhood.delta.variables(var), value)) {
2821 // TODO(user): Instead of aborting, pick the closest point in the domain?
2822 return neighborhood;
2823 }
2824
2825 neighborhood.delta.mutable_variables(var)->clear_domain();
2826 neighborhood.delta.mutable_variables(var)->add_domain(value);
2827 neighborhood.delta.mutable_variables(var)->add_domain(value);
2828 neighborhood.is_reduced = true;
2829 }
2830
2831 for (const std::pair</*model_var*/ int,
2832 /*domain*/ std::pair<int64_t, int64_t>>& reduced_var :
2833 reduced_domains.reduced_domain_vars) {
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;
2837 if (var >= neighborhood.delta.variables_size()) continue;
2838 if (!helper_.IsActive(var)) continue;
2839 const Domain domain =
2840 ReadDomainFromProto(neighborhood.delta.variables(var));
2841 Domain new_domain = domain.IntersectionWith(Domain(lb, ub));
2842 if (new_domain.IsEmpty()) {
2843 new_domain = Domain::FromValues(
2844 {domain.ClosestValue(lb), domain.ClosestValue(ub)});
2845 }
2846 FillDomainInProto(domain, neighborhood.delta.mutable_variables(var));
2847 neighborhood.is_reduced = true;
2848 }
2849 neighborhood.is_generated = true;
2850 return neighborhood;
2851}
2852
2853} // namespace sat
2854} // namespace operations_research
bool AddEdge(int node1, int node2)
IndexType size() const
Returns how many bits this Bitset64 can hold.
Definition bitset.h:463
void Clear(IndexType i)
Sets the bit at position i to 0.
Definition bitset.h:505
void Set(IndexType i)
Sets the bit at position i to 1.
Definition bitset.h:543
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
int Size() const
Returns the number of elements currently present.
Definition integer_pq.h:56
bool Contains(int index) const
Returns true if the element with given index is currently in the queue.
Definition integer_pq.h:67
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
int literals_size() const
repeated int32 literals = 5;
void RemoveBySwap(K key, int index)
Definition util.h:141
Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random) final
::int32_t enforcement_literal(int index) const
const ::operations_research::sat::IntervalConstraintProto & interval() const
const ::operations_research::sat::RoutesConstraintProto & routes() const
::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
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
::operations_research::sat::CpSolverStatus status() 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;
void set_name(Arg_ &&arg, Args_... args)
const ::operations_research::sat::LinearExpressionProto & size() const
const ::operations_research::sat::LinearExpressionProto & end() const
const ::operations_research::sat::LinearExpressionProto & start() 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.
Definition util.h:354
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 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
std::vector< std::vector< int > > GetUniqueIntervalSets() const
std::vector< ActiveRectangle > GetActiveRectangles(const CpSolverResponse &initial_solution) 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 GetUCBScore(int64_t total_num_calls) const
const NeighborhoodGeneratorHelper & helper_
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()
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.
int literals_size() const
repeated int32 literals = 3;
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
SubSolver(absl::string_view name, SubsolverType type)
Definition subsolver.h:48
SubsolverType type() const
Returns the type of the subsolver.
Definition subsolver.h:98
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)
Definition stl_util.h:55
void SolveLoadedCpModel(const CpModelProto &model_proto, Model *model)
void RemoveVariablesFromInterval(const CpModelProto &model_proto, int index, Bitset64< int > &output)
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)
Definition rins.cc:176
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)
Definition diffn_util.h:145
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.
Definition diffn_util.h:135
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)
const bool DEBUG_MODE
Definition radix_sort.h:266
ClosedInterval::Iterator begin(ClosedInterval interval)
Definition model.h:51
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.
Neighborhood returned by Neighborhood generators.
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)
Definition diffn_util.h:50
std::vector< std::pair< int, std::pair< int64_t, int64_t > > > reduced_domain_vars
Definition rins.h:41
std::vector< std::pair< int, int64_t > > fixed_vars
A variable will appear only once and not in both vectors.
Definition rins.h:38