Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
cp_model_lns.h
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
14#ifndef OR_TOOLS_SAT_CP_MODEL_LNS_H_
15#define OR_TOOLS_SAT_CP_MODEL_LNS_H_
16
17#include <cmath>
18#include <cstddef>
19#include <cstdint>
20#include <functional>
21#include <memory>
22#include <string>
23#include <tuple>
24#include <utility>
25#include <vector>
26
27#include "absl/base/thread_annotations.h"
28#include "absl/container/flat_hash_set.h"
29#include "absl/log/check.h"
30#include "absl/random/bit_gen_ref.h"
31#include "absl/strings/string_view.h"
32#include "absl/synchronization/mutex.h"
33#include "absl/types/span.h"
34#include "google/protobuf/arena.h"
35#include "ortools/sat/cp_model.pb.h"
38#include "ortools/sat/sat_parameters.pb.h"
41#include "ortools/sat/util.h"
43#include "ortools/util/bitset.h"
44
45namespace operations_research {
46namespace sat {
47
48// Neighborhood returned by Neighborhood generators.
50 static constexpr int kDefaultArenaSizePerVariable = 128;
51
52 explicit Neighborhood(int num_variables_hint = 10)
53 : arena(std::make_unique<google::protobuf::Arena>(
54 google::protobuf::ArenaOptions(
55 {.start_block_size = static_cast<size_t>(
56 kDefaultArenaSizePerVariable * num_variables_hint)}))),
57 delta(*google::protobuf::Arena::Create<CpModelProto>(arena.get())) {}
58
59 // True if neighborhood generator was able to generate a neighborhood.
60 bool is_generated = false;
61
62 // False if an optimal solution to the neighborhood is also an optimal
63 // solution to the original model.
64 bool is_reduced = false;
65
66 // True if this neighborhood was just obtained by fixing some variables.
67 bool is_simple = false;
68
69 // Specification of the delta between the initial model and the lns fragment.
70 // The delta will contains all variables from the initial model, potentially
71 // with updated domains.
72 // It can contains new variables and new constraints, and solution hinting.
73 std::unique_ptr<google::protobuf::Arena> arena;
74 CpModelProto& delta;
75
76 // Neighborhood Id. Used to identify the neighborhood by a generator.
77 // Currently only used by WeightedRandomRelaxationNeighborhoodGenerator.
78 // TODO(user): Make sure that the id is unique for each generated
79 // neighborhood for each generator.
80 int64_t id = 0;
81
82 // Overwrites the name of the neighborhood generator in the logs.
83 std::string source_info = "";
84
85 // Statistic, only filled when is_simple is true.
88
89 // Only filled when is_simple is true. If we solve the fragment to optimality,
90 // then we can just fix the variable listed here to that optimal solution.
91 //
92 // This can happen if the neighborhood fully cover some part that are
93 // completely independent from the rest of the model. Like for instance an
94 // unused but not yet fixed variable.
95 //
96 // WARNING: all such variables should be fixed at once in a lock-like manner,
97 // because they can be multiple optimal solutions on these variables.
99};
100
101// Contains pre-computed information about a given CpModelProto that is meant
102// to be used to generate LNS neighborhood. This class can be shared between
103// more than one generator in order to reduce memory usage.
104//
105// Note that its implement the SubSolver interface to be able to Synchronize()
106// the bounds of the base problem with the external world.
108 public:
109 NeighborhoodGeneratorHelper(CpModelProto const* model_proto,
110 SatParameters const* parameters,
112 ModelSharedTimeLimit* global_time_limit,
113 SharedBoundsManager* shared_bounds = nullptr);
114
115 // SubSolver interface.
116 bool TaskIsAvailable() override { return false; }
117 std::function<void()> GenerateTask(int64_t /*task_id*/) override {
118 return {};
119 }
120 void Synchronize() override;
121
122 int NumVariables() const { return model_proto_.variables().size(); }
123
124 // Returns the LNS fragment where the given variables are fixed to the value
125 // they take in the given solution.
126 Neighborhood FixGivenVariables(const CpSolverResponse& base_solution,
127 const Bitset64<int>& variables_to_fix) const;
128
129 // Returns the LNS fragment which will relax all inactive variables and all
130 // variables in relaxed_variables.
132 const CpSolverResponse& initial_solution,
133 absl::Span<const int> relaxed_variables) const;
134
135 // Returns a trivial model by fixing all active variables to the initial
136 // solution values.
137 Neighborhood FixAllVariables(const CpSolverResponse& initial_solution) const;
138
139 // Returns a neighborhood that correspond to the full problem.
141
142 // Returns a neighborhood that will just be skipped.
143 // It usually indicate that the generator failed to generated a neighborhood.
145
146 // Adds solution hinting to the neighborhood from the value of the initial
147 // solution.
148 void AddSolutionHinting(const CpSolverResponse& initial_solution,
149 CpModelProto* model_proto) const;
150
151 // Indicates if the variable can be frozen. It happens if the variable is non
152 // constant, and if it is a decision variable, or if
153 // focus_on_decision_variables is false.
154 bool IsActive(int var) const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_);
155
156 // Returns the list of "active" variables.
157 std::vector<int> ActiveVariables() const {
158 std::vector<int> result;
159 absl::ReaderMutexLock lock(&graph_mutex_);
160 result = active_variables_;
161 return result;
162 }
163
164 int NumActiveVariables() const {
165 absl::ReaderMutexLock lock(&graph_mutex_);
166 return active_variables_.size();
167 }
168
169 std::vector<int> ActiveObjectiveVariables() const {
170 std::vector<int> result;
171 absl::ReaderMutexLock lock(&graph_mutex_);
172 result = active_objective_variables_;
173 return result;
174 }
175
176 bool DifficultyMeansFullNeighborhood(double difficulty) const {
177 absl::ReaderMutexLock lock(&graph_mutex_);
178 const int target_size =
179 static_cast<int>(std::ceil(difficulty * active_variables_.size()));
180 return target_size == active_variables_.size();
181 }
182
183 // Returns the vector of active variables. The graph_mutex_ must be
184 // locked before calling this method.
185 const std::vector<int>& ActiveVariablesWhileHoldingLock() const
186 ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_) {
187 return active_variables_;
188 }
189
190 // Returns the vector of active objective variables. The graph_mutex_ must be
191 // locked before calling this method.
193 ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_) {
194 std::vector<int> result;
195 result = active_objective_variables_;
196 return result;
197 }
198
199 // Returns the vector of objective variables that are not already at their
200 // best possible value. The graph_mutex_ must be locked before calling this
201 // method.
203 const CpSolverResponse& initial_solution) const
204 ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
205 ABSL_LOCKS_EXCLUDED(domain_mutex_);
206
207 // Constraints <-> Variables graph.
208 // Important:
209 // - The constraint index is NOT related to the one in the cp_model.
210 // - Only non-constant var are listed in ConstraintToVar().
212 ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_) {
213 return constraint_to_var_;
214 }
216 ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_) {
217 return var_to_constraint_;
218 }
219
220 // Returns all the constraints indices of a given type.
221 absl::Span<const int> TypeToConstraints(
222 ConstraintProto::ConstraintCase type) const {
223 if (type >= type_to_constraints_.size()) return {};
224 return absl::MakeSpan(type_to_constraints_[type]);
225 }
226
227 // Filters a vector of intervals against the initial_solution, and returns
228 // only the active intervals.
229 std::vector<int> KeepActiveIntervals(
230 absl::Span<const int> unfiltered_intervals,
231 const CpSolverResponse& initial_solution) const;
232
233 // Returns the list of indices of active interval constraints according
234 // to the initial_solution and the parameter lns_focus_on_performed_intervals.
235 // If true, this method returns the list of performed intervals in the
236 // solution. If false, it returns all intervals of the model.
237 std::vector<int> GetActiveIntervals(
238 const CpSolverResponse& initial_solution) const;
239
240 // Returns the list of active rectangles appearing in no_overlap_2d
241 // constraints according to the initial_solution and the parameter
242 // lns_focus_on_performed_intervals. If true, this method returns the list of
243 // performed rectangles in the solution. If false, it returns all rectangles
244 // of the model.
248 // The set of no_overlap_2d constraints that both x_interval and y_interval
249 // are participating in.
250 absl::flat_hash_set<int> no_overlap_2d_constraints;
251 };
252 std::vector<ActiveRectangle> GetActiveRectangles(
253 const CpSolverResponse& initial_solution) const;
254
255 // Returns the set of unique intervals list appearing in a no_overlap,
256 // cumulative, or as a dimension of a no_overlap_2d constraint.
257 std::vector<std::vector<int>> GetUniqueIntervalSets() const;
258
259 // Returns one sub-vector per circuit or per individual vehicle circuit in a
260 // routes constraints. Each circuit is non empty, and does not contain any
261 // self-looping arcs. Path are sorted, starting from the arc with the lowest
262 // tail index, and going in sequence up to the last arc before the circuit is
263 // closed. Each entry correspond to the Boolean variable of the arc literal on
264 // the circuit.
265 std::vector<std::vector<int>> GetRoutingPathBooleanVariables(
266 const CpSolverResponse& initial_solution) const;
267
268 // Returns all precedences extracted from the scheduling constraint and the
269 // initial solution. The precedences will be sorted by the natural order
270 // the pairs of integers.
271 std::vector<std::pair<int, int>> GetSchedulingPrecedences(
272 const absl::flat_hash_set<int>& ignored_intervals,
273 const CpSolverResponse& initial_solution, absl::BitGenRef random) const;
274
275 // Returns a copy of the problem proto with updated domains.
276 CpModelProto UpdatedModelProtoCopy() const;
277
278 // The initial problem.
279 // Note that the domain of the variables are not updated here.
280 const CpModelProto& ModelProto() const { return model_proto_; }
281 const SatParameters& Parameters() const { return parameters_; }
282
284 return *shared_response_;
285 }
286
287 // TODO(user): Refactor the class to be thread-safe instead, it should be
288 // safer and more easily maintainable. Some complication with accessing the
289 // variable<->constraint graph efficiently though.
290
291 // Note: This mutex needs to be public for thread annotations.
292 mutable absl::Mutex graph_mutex_;
293
294 // TODO(user): Display LNS statistics through the StatisticsString()
295 // method.
296
297 private:
298 // Precompute stuff that will never change. During the execution, only the
299 // domain of the variable will change, so data that only depends on the
300 // constraints need to be computed just once.
301 void InitializeHelperData();
302
303 // Recompute most of the class member. This needs to be called when the
304 // domains of the variables are updated.
305 void RecomputeHelperData();
306
307 // Indicates if a variable is fixed in the model.
308 bool IsConstant(int var) const ABSL_SHARED_LOCKS_REQUIRED(domain_mutex_);
309
310 // Returns true if the domain on the objective is constraining and we might
311 // get a lower objective value at optimum without it.
312 bool ObjectiveDomainIsConstraining() const
313 ABSL_SHARED_LOCKS_REQUIRED(domain_mutex_);
314
315 // Checks if an interval is active w.r.t. the initial_solution.
316 // An interval is inactive if and only if it is either unperformed in the
317 // solution or constant in the model.
318 bool IntervalIsActive(int index,
319 const CpSolverResponse& initial_solution) const
320 ABSL_SHARED_LOCKS_REQUIRED(domain_mutex_);
321
322 const SatParameters& parameters_;
323 const CpModelProto& model_proto_;
324 int shared_bounds_id_;
325 SharedBoundsManager* shared_bounds_;
326 ModelSharedTimeLimit* global_time_limit_;
327 SharedResponseManager* shared_response_;
328
329 // Arena holding the memory of the CpModelProto* of this class. This saves the
330 // destruction cost that can take time on problem with millions of
331 // variables/constraints.
332 std::vector<char> local_arena_storage_;
333 std::unique_ptr<google::protobuf::Arena> local_arena_;
334
335 // This proto will only contain the field variables() with an updated version
336 // of the domains compared to model_proto_.variables(). We do it like this to
337 // reduce the memory footprint of the helper when the model is large.
338 //
339 // TODO(user): Use custom domain repository rather than a proto?
340 CpModelProto model_proto_with_only_variables_ ABSL_GUARDED_BY(domain_mutex_);
341
342 // Constraints by types. This never changes.
343 std::vector<std::vector<int>> type_to_constraints_;
344
345 // Whether a model_proto_ variable appears in the objective. This never
346 // changes.
347 std::vector<bool> is_in_objective_;
348 // If a model_proto_ variable has a positive coefficient in the objective.
349 // This never changes.
350 std::vector<bool> has_positive_objective_coefficient_;
351
352 // A copy of CpModelProto where we did some basic presolving to remove all
353 // constraint that are always true. The Variable-Constraint graph is based on
354 // this model. Note that only the constraints field is present here.
355 CpModelProto* simplified_model_proto_ ABSL_GUARDED_BY(graph_mutex_);
356
357 // Variable-Constraint graph.
358 // We replace an interval by its variables in the scheduling constraints.
359 //
360 // TODO(user): Note that the objective is not considered here. Which is fine
361 // except if the objective domain is constraining.
362 CompactVectorVector<int, int> constraint_to_var_
363 ABSL_GUARDED_BY(graph_mutex_);
364 CompactVectorVector<int, int> var_to_constraint_
365 ABSL_GUARDED_BY(graph_mutex_);
366
367 // Connected components of the variable-constraint graph. If a variable is
368 // constant, it will not appear in any component and
369 // var_to_component_index_[var] will be -1.
370 std::vector<std::vector<int>> components_ ABSL_GUARDED_BY(graph_mutex_);
371 std::vector<int> var_to_component_index_ ABSL_GUARDED_BY(graph_mutex_);
372
373 // The set of active variables which is currently the list of non-constant
374 // variables. It is stored both as a list and as a set (using a Boolean
375 // vector).
376 std::vector<bool> active_variables_set_ ABSL_GUARDED_BY(graph_mutex_);
377 std::vector<int> active_variables_ ABSL_GUARDED_BY(graph_mutex_);
378
379 // The list of non constant variables appearing in the objective.
380 std::vector<int> active_objective_variables_ ABSL_GUARDED_BY(graph_mutex_);
381
382 std::vector<int> tmp_row_;
383
384 mutable absl::Mutex domain_mutex_ ABSL_ACQUIRED_AFTER(graph_mutex_);
385};
386
387// Base class for a CpModelProto neighborhood generator.
389 public:
390 NeighborhoodGenerator(absl::string_view name,
391 NeighborhoodGeneratorHelper const* helper)
392 : name_(name),
393 helper_(*helper),
395 helper->Parameters().lns_initial_deterministic_limit()),
396 difficulty_(helper->Parameters().lns_initial_difficulty()) {}
397 virtual ~NeighborhoodGenerator() = default;
398
400
401 // Adds solve data about one "solved" neighborhood.
402 struct SolveData {
403 // The status of the sub-solve.
404 CpSolverStatus status = CpSolverStatus::UNKNOWN;
405
406 // The difficulty when this neighborhood was generated.
407 double difficulty = 0.0;
408
409 // The deterministic time limit given to the solver for this neighborhood.
411
412 // The time it took to solve this neighborhood.
413 double deterministic_time = 0.0;
414
415 // Objective information. These only refer to the "internal" objective
416 // without scaling or offset so we are exact and it is always in the
417 // minimization direction.
418 // - The initial best objective is the one of the best known solution at the
419 // time the neighborhood was generated.
420 // - The base objective is the one of the base solution from which this
421 // neighborhood was generated.
422 // - The new objective is the objective of the best solution found by
423 // solving the neighborhood.
424 IntegerValue initial_best_objective = IntegerValue(0);
425 IntegerValue base_objective = IntegerValue(0);
426 IntegerValue new_objective = IntegerValue(0);
427
428 // For debugging.
429 int task_id = 0;
430
431 // This is just used to construct a deterministic order for the updates.
440 };
441
442 // Generates a "local" subproblem for the given seed.
443 //
444 // The data,difficulty will be in [0, 1] and is related to the asked
445 // neighborhood size (and thus local problem difficulty). A difficulty of 0.0
446 // means empty neighborhood and a difficulty of 1.0 means the full problem.
447 // The algorithm should try to generate a neighborhood according to this
448 // difficulty which will be dynamically adjusted depending on whether or not
449 // we can solve the subproblem in a given time limit.
450 //
451 // The given initial_solution should contain a feasible solution to the
452 // initial CpModelProto given to this class. Any solution to the returned
453 // CPModelProto should also be valid solution to the same initial model.
454 //
455 // This function should be thread-safe.
456 virtual Neighborhood Generate(const CpSolverResponse& initial_solution,
457 SolveData& data, absl::BitGenRef random) = 0;
458
459 // Returns true if the neighborhood generator can generate a neighborhood.
460 virtual bool ReadyToGenerate() const;
461
462 // Uses UCB1 algorithm to compute the score (Multi armed bandit problem).
463 // Details are at
464 // https://lilianweng.github.io/lil-log/2018/01/23/the-multi-armed-bandit-problem-and-its-solutions.html.
465 // 'total_num_calls' should be the sum of calls across all generators part of
466 // the multi armed bandit problem.
467 // If the generator is called less than 10 times then the method returns
468 // infinity as score in order to get more data about the generator
469 // performance.
470 double GetUCBScore(int64_t total_num_calls) const;
471
473 absl::MutexLock mutex_lock(&generator_mutex_);
474 solve_data_.push_back(data);
475 }
476
477 // Process all the recently added solve data and update this generator
478 // score and difficulty. This returns list of the deterministic time of
479 // each SolveData.
480 absl::Span<const double> Synchronize();
481
482 // Returns a short description of the generator.
483 std::string name() const { return name_; }
484
485 // Number of times this generator was called.
486 int64_t num_calls() const {
487 absl::MutexLock mutex_lock(&generator_mutex_);
488 return num_calls_;
489 }
490
491 // Number of time the neighborhood was fully solved (OPTIMAL/INFEASIBLE).
492 int64_t num_fully_solved_calls() const {
493 absl::MutexLock mutex_lock(&generator_mutex_);
494 return num_fully_solved_calls_;
495 }
496
497 // Out of num_calls(), how many improved the given solution.
498 int64_t num_improving_calls() const {
499 absl::MutexLock mutex_lock(&generator_mutex_);
500 return num_improving_calls_;
501 }
502
503 // Returns the number of the last calls to this generator that didn't improve
504 // the best solution. Note that this count improvement to the best known
505 // solution not the base one used to generate one neighborhood.
507 absl::MutexLock mutex_lock(&generator_mutex_);
508 return num_consecutive_non_improving_calls_;
509 }
510
511 // The current difficulty of this generator
512 double difficulty() const {
513 absl::MutexLock mutex_lock(&generator_mutex_);
514 return difficulty_.value();
515 }
516
517 // The current time limit that the sub-solve should use on this generator.
518 double deterministic_limit() const {
519 absl::MutexLock mutex_lock(&generator_mutex_);
521 }
522
523 protected:
524 const std::string name_;
526 mutable absl::Mutex generator_mutex_;
528
529 private:
530 std::vector<SolveData> solve_data_;
531 std::vector<double> tmp_dtimes_;
532
533 // Current parameters to be used when generating/solving a neighborhood with
534 // this generator. Only updated on Synchronize().
535 AdaptiveParameterValue difficulty_;
536
537 // Current statistics of the last solved neighborhood.
538 // Only updated on Synchronize().
539 int64_t num_calls_ = 0;
540 int64_t num_fully_solved_calls_ = 0;
541 int64_t num_improving_calls_ = 0;
542 int64_t num_consecutive_non_improving_calls_ = 0;
543 int64_t next_time_limit_bump_ = 50;
544 double current_average_ = 0.0;
545};
546
547// Pick a random subset of variables.
548//
549// TODO(user): In the presence of connected components, this should just work
550// on one of them.
552 public:
554 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
555 : NeighborhoodGenerator(name, helper) {}
556 Neighborhood Generate(const CpSolverResponse& initial_solution,
557 SolveData& data, absl::BitGenRef random) final;
558};
559
560// Pick a random subset of constraints and relax all the variables of these
561// constraints. Note that to satisfy the difficulty, we might not relax all the
562// variable of the "last" constraint.
563//
564// TODO(user): In the presence of connected components, this should just work
565// on one of them.
567 public:
569 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
570 : NeighborhoodGenerator(name, helper) {}
571 Neighborhood Generate(const CpSolverResponse& initial_solution,
572 SolveData& data, absl::BitGenRef random) final;
573};
574
575// Pick a random subset of variables that are constructed by a BFS in the
576// variable <-> constraint graph. That is, pick a random variable, then all the
577// variable connected by some constraint to the first one, and so on. The
578// variable of the last "level" are selected randomly.
579//
580// Note that in the presence of connected component, this works correctly
581// already.
583 public:
585 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
586 : NeighborhoodGenerator(name, helper) {}
587 Neighborhood Generate(const CpSolverResponse& initial_solution,
588 SolveData& data, absl::BitGenRef random) final;
589};
590
591// This randomly extend a working set of variable by one variable directly
592// connected to that set.
594 public:
596 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
597 : NeighborhoodGenerator(name, helper) {}
598 Neighborhood Generate(const CpSolverResponse& initial_solution,
599 SolveData& data, absl::BitGenRef random) final;
600};
601
602// Pick a random subset of constraint and relax all of their variables. We are a
603// bit smarter than this because after the first constraint is selected, we only
604// select constraints that share at least one variable with the already selected
605// constraints. The variable from the "last" constraint are selected randomly.
607 public:
609 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
610 : NeighborhoodGenerator(name, helper) {}
611 Neighborhood Generate(const CpSolverResponse& initial_solution,
612 SolveData& data, absl::BitGenRef random) final;
613};
614
615// The idea here is to try to generate a random neighborhood incrementally in
616// such a way that we have at various point a "minimum connection" in term of
617// constraints or variable to the outside world.
618//
619// This is inspired by what would be a good neighborhood if one where to use
620// a tree decomposition of the constraint-variable graph with small treewidth.
621//
622// TODO(user): Doing the full heuristic treewidth decomposition is probably
623// better because when we grow the current neighborhood, just using local
624// connection to the current candidate is probably not enough to orient the
625// search towards a good final neighborhood.
627 public:
629 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
630 : NeighborhoodGenerator(name, helper) {}
631 Neighborhood Generate(const CpSolverResponse& initial_solution,
632 SolveData& data, absl::BitGenRef random) final;
633};
634
635// Solves a local branching LP and greedily picks a set of variables with the
636// largest differences between the initial and local branching LP solutions,
637// breaking ties uniformly at random.
638//
639// This is based on Huang et al., "Local Branching Relaxation Heuristics for
640// Integer Linear Programs", 2023.
642 : public NeighborhoodGenerator {
643 public:
645 NeighborhoodGeneratorHelper const* helper, absl::string_view name,
646 ModelSharedTimeLimit* const global_time_limit, SharedClasses* shared)
647 : NeighborhoodGenerator(name, helper),
648 global_time_limit_(global_time_limit),
649 shared_(shared) {
650 // Given that we spend time generating a good neighborhood it sounds
651 // reasonable to spend a bit more time solving it too.
653 }
654
655 Neighborhood Generate(const CpSolverResponse& initial_solution,
656 SolveData& data, absl::BitGenRef random) final;
657
658 private:
659 ModelSharedTimeLimit* const global_time_limit_;
660 SharedClasses* const shared_;
661};
662
663// Helper method for the scheduling neighborhood generators. Returns a
664// neighborhood defined from the given set of intervals to relax. For each
665// scheduling constraint, it adds strict relation order between the non-relaxed
666// intervals.
668 absl::Span<const int> intervals_to_relax,
669 absl::Span<const int> variables_to_fix,
670 const CpSolverResponse& initial_solution, absl::BitGenRef random,
671 const NeighborhoodGeneratorHelper& helper);
672
673// Helper method for the scheduling neighborhood generators. Returns a
674// full neighborhood enriched with the set or precedences passed to the generate
675// method.
677 absl::Span<const std::pair<int, int>> precedences,
678 const CpSolverResponse& initial_solution,
679 const NeighborhoodGeneratorHelper& helper);
680
681// Only make sense for scheduling problem. This select a random set of interval
682// of the problem according to the difficulty. Then, for each scheduling
683// constraints, it adds strict relation order between the non-relaxed intervals.
685 : public NeighborhoodGenerator {
686 public:
688 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
689 : NeighborhoodGenerator(name, helper) {}
690
691 Neighborhood Generate(const CpSolverResponse& initial_solution,
692 SolveData& data, absl::BitGenRef random) final;
693};
694
695// Only make sense for scheduling problem. This select a random set of
696// precedences between intervals of the problem according to the difficulty.
697// These precedences are extracted from the scheduling constraints and their
698// configuration in the current solution. Then it adds the kept precedences to
699// the model.
701 : public NeighborhoodGenerator {
702 public:
704 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
705 : NeighborhoodGenerator(name, helper) {}
706
707 Neighborhood Generate(const CpSolverResponse& initial_solution,
708 SolveData& data, absl::BitGenRef random) final;
709};
710
711// Similar to SchedulingNeighborhoodGenerator except the set of intervals that
712// are relaxed are from a specific random time interval.
714 public:
716 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
717 : NeighborhoodGenerator(name, helper) {}
718
719 Neighborhood Generate(const CpSolverResponse& initial_solution,
720 SolveData& data, absl::BitGenRef random) final;
721};
722
723// Similar to SchedulingTimeWindowNeighborhoodGenerator except that it relaxes
724// one independent time window per resource (1 for each dimension in the
725// no_overlap_2d case).
727 : public NeighborhoodGenerator {
728 public:
730 NeighborhoodGeneratorHelper const* helper,
731 const std::vector<std::vector<int>>& intervals_in_constraints,
732 absl::string_view name)
733 : NeighborhoodGenerator(name, helper),
734 intervals_in_constraints_(intervals_in_constraints) {}
735
736 Neighborhood Generate(const CpSolverResponse& initial_solution,
737 SolveData& data, absl::BitGenRef random) final;
738
739 private:
740 const std::vector<std::vector<int>> intervals_in_constraints_;
741};
742
743// Only make sense for problems with no_overlap_2d constraints. This select a
744// random set of rectangles (i.e. a pair of intervals) of the problem according
745// to the difficulty. Then fix all variables in the selected intervals.
747 : public NeighborhoodGenerator {
748 public:
750 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
751 : NeighborhoodGenerator(name, helper) {}
752
753 Neighborhood Generate(const CpSolverResponse& initial_solution,
754 SolveData& data, absl::BitGenRef random) final;
755};
756
757// Only make sense for problems with no_overlap_2d constraints. This selects one
758// random rectangles and relax the closest rectangles to it.
760 : public NeighborhoodGenerator {
761 public:
763 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
764 : NeighborhoodGenerator(name, helper) {}
765
766 Neighborhood Generate(const CpSolverResponse& initial_solution,
767 SolveData& data, absl::BitGenRef random) final;
768};
769
770// Only make sense for problems with no_overlap_2d constraints. This selects two
771// random rectangles and relax them alongside the closest rectangles to each one
772// of them. The idea is that this will find a better solution when there is a
773// cost function that would be improved by swapping the two rectangles.
775 : public NeighborhoodGenerator {
776 public:
778 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
779 : NeighborhoodGenerator(name, helper) {}
780
781 Neighborhood Generate(const CpSolverResponse& initial_solution,
782 SolveData& data, absl::BitGenRef random) final;
783};
784
785// Only make sense for problems with no_overlap_2d constraints. This select a
786// random set of rectangles (i.e. a pair of intervals) of the problem according
787// to the difficulty. Then add all implied precedences from the current
788// positions of the rectangles in this selected subset.
790 : public NeighborhoodGenerator {
791 public:
793 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
794 : NeighborhoodGenerator(name, helper) {}
795
796 Neighborhood Generate(const CpSolverResponse& initial_solution,
797 SolveData& data, absl::BitGenRef random) final;
798};
799
800// Only make sense for problems with no_overlap_2d constraints. This select a
801// slice on one dimension, and fix the variables of all rectangles not strictly
802// included in this slice.
804 public:
806 NeighborhoodGeneratorHelper const* helper, absl::string_view name)
807 : NeighborhoodGenerator(name, helper) {}
808
809 Neighborhood Generate(const CpSolverResponse& initial_solution,
810 SolveData& data, absl::BitGenRef random) final;
811};
812
813// This routing based LNS generator will relax random arcs in all the paths of
814// the circuit or routes constraints.
816 public:
820
821 Neighborhood Generate(const CpSolverResponse& initial_solution,
822 SolveData& data, absl::BitGenRef random) final;
823};
824
825// This routing based LNS generator will relax small sequences of arcs randomly
826// chosen in all the paths of the circuit or routes constraints.
828 public:
830 absl::string_view name)
831 : NeighborhoodGenerator(name, helper) {}
832
833 Neighborhood Generate(const CpSolverResponse& initial_solution,
834 SolveData& data, absl::BitGenRef random) final;
835};
836
837// This routing based LNS generator aims at relaxing one full path, and make
838// some room on the other paths to absorb the nodes of the relaxed path.
839//
840// In order to do so, it will relax the first and the last arc of each path in
841// the circuit or routes constraints. Then it will relax all arc literals in one
842// random path. Then it will relax random arcs in the remaining paths until it
843// reaches the given difficulty.
845 public:
849
850 Neighborhood Generate(const CpSolverResponse& initial_solution,
851 SolveData& data, absl::BitGenRef random) final;
852};
853
854// Generates a neighborhood by fixing the variables to solutions reported in
855// various repositories. This is inspired from RINS published in "Exploring
856// relaxation induced neighborhoods to improve MIP solutions" 2004 by E. Danna
857// et.
858//
859// If incomplete_solutions is provided, this generates a neighborhood by fixing
860// the variable values to a solution in the SharedIncompleteSolutionManager and
861// ignores the other repositories.
862//
863// Otherwise, if response_manager is not provided, this generates a neighborhood
864// using only the linear/general relaxation values. The domain of the variables
865// are reduced to the integer values around their lp solution/relaxation
866// solution values. This was published in "RENS – The Relaxation Enforced
867// Neighborhood" 2009 by Timo Berthold.
869 public:
871 NeighborhoodGeneratorHelper const* helper,
872 const SharedResponseManager* response_manager,
873 const SharedLPSolutionRepository* lp_solutions,
874 SharedIncompleteSolutionManager* incomplete_solutions,
875 absl::string_view name)
876 : NeighborhoodGenerator(name, helper),
877 response_manager_(response_manager),
878 lp_solutions_(lp_solutions),
879 incomplete_solutions_(incomplete_solutions) {
880 CHECK(lp_solutions_ != nullptr);
881 CHECK(incomplete_solutions != nullptr);
882 }
883
884 // Both initial solution and difficulty values are ignored.
885 Neighborhood Generate(const CpSolverResponse& initial_solution,
886 SolveData& data, absl::BitGenRef random) final;
887
888 // Returns true if the required solutions are available.
889 bool ReadyToGenerate() const override;
890
891 private:
892 const SharedResponseManager* response_manager_;
893 const SharedLPSolutionRepository* lp_solutions_;
894 SharedIncompleteSolutionManager* incomplete_solutions_;
895};
896
897} // namespace sat
898} // namespace operations_research
899
900#endif // OR_TOOLS_SAT_CP_MODEL_LNS_H_
ArcGraphNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
ConstraintGraphNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
DecompositionGraphNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
LocalBranchingLpBasedNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name, ModelSharedTimeLimit *const global_time_limit, SharedClasses *shared)
The model "singleton" shared time limit.
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 std::vector< int > & ActiveVariablesWhileHoldingLock() const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
const CompactVectorVector< int, int > & VarToConstraint() const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
const SharedResponseManager & shared_response() const
Neighborhood RelaxGivenVariables(const CpSolverResponse &initial_solution, absl::Span< const int > relaxed_variables) const
std::vector< int > ActiveVariables() const
Returns the list of "active" variables.
std::vector< std::vector< int > > GetUniqueIntervalSets() const
const CompactVectorVector< int, int > & ConstraintToVar() const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
std::vector< ActiveRectangle > GetActiveRectangles(const CpSolverResponse &initial_solution) const
bool DifficultyMeansFullNeighborhood(double difficulty) const
void AddSolutionHinting(const CpSolverResponse &initial_solution, CpModelProto *model_proto) const
std::vector< int > ActiveObjectiveVariablesWhileHoldingLock() const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
std::function< void()> GenerateTask(int64_t) override
std::vector< int > GetActiveIntervals(const CpSolverResponse &initial_solution) const
std::vector< std::pair< int, int > > GetSchedulingPrecedences(const absl::flat_hash_set< int > &ignored_intervals, const CpSolverResponse &initial_solution, absl::BitGenRef random) const
absl::Span< const int > TypeToConstraints(ConstraintProto::ConstraintCase type) const
Returns all the constraints indices of a given type.
bool TaskIsAvailable() override
SubSolver interface.
NeighborhoodGeneratorHelper(CpModelProto const *model_proto, SatParameters const *parameters, SharedResponseManager *shared_response, ModelSharedTimeLimit *global_time_limit, SharedBoundsManager *shared_bounds=nullptr)
std::vector< int > KeepActiveIntervals(absl::Span< const int > unfiltered_intervals, const CpSolverResponse &initial_solution) const
NeighborhoodGeneratorHelper::ActiveRectangle ActiveRectangle
virtual bool ReadyToGenerate() const
Returns true if the neighborhood generator can generate a neighborhood.
double deterministic_limit() const
The current time limit that the sub-solve should use on this generator.
int64_t num_improving_calls() const
Out of num_calls(), how many improved the given solution.
std::string name() const
Returns a short description of the generator.
virtual Neighborhood Generate(const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random)=0
double difficulty() const
The current difficulty of this generator.
double GetUCBScore(int64_t total_num_calls) const
int64_t num_calls() const
Number of times this generator was called.
const NeighborhoodGeneratorHelper & helper_
int64_t num_fully_solved_calls() const
Number of time the neighborhood was fully solved (OPTIMAL/INFEASIBLE).
NeighborhoodGenerator(absl::string_view name, NeighborhoodGeneratorHelper const *helper)
RandomIntervalSchedulingNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RandomPrecedenceSchedulingNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RandomPrecedencesPackingNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RandomRectanglesPackingNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RectanglesPackingRelaxOneNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RectanglesPackingRelaxTwoNeighborhoodsGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RelaxRandomConstraintsGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RelaxRandomVariablesGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RelaxationInducedNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const SharedResponseManager *response_manager, const SharedLPSolutionRepository *lp_solutions, SharedIncompleteSolutionManager *incomplete_solutions, absl::string_view name)
RoutingFullPathNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RoutingPathNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
RoutingRandomNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
SchedulingResourceWindowsNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::vector< std::vector< int > > &intervals_in_constraints, absl::string_view name)
SchedulingTimeWindowNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
SlicePackingNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
SubSolver(absl::string_view name, SubsolverType type)
Definition subsolver.h:48
SubsolverType type() const
Returns the type of the subsolver.
Definition subsolver.h:98
VariableGraphNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, absl::string_view name)
Neighborhood GenerateSchedulingNeighborhoodFromIntervalPrecedences(const absl::Span< const std::pair< int, int > > precedences, const CpSolverResponse &initial_solution, const NeighborhoodGeneratorHelper &helper)
Neighborhood GenerateSchedulingNeighborhoodFromRelaxedIntervals(absl::Span< const int > intervals_to_relax, absl::Span< const int > variables_to_fix, const CpSolverResponse &initial_solution, absl::BitGenRef random, const NeighborhoodGeneratorHelper &helper)
In SWIG mode, we don't want anything besides these top-level includes.
STL namespace.
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.
double deterministic_limit
The deterministic time limit given to the solver for this neighborhood.
CpSolverStatus status
The status of the sub-solve.
bool operator<(const SolveData &o) const
This is just used to construct a deterministic order for the updates.
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.
Neighborhood(int num_variables_hint=10)
std::unique_ptr< google::protobuf::Arena > arena
bool is_generated
True if neighborhood generator was able to generate a neighborhood.
std::vector< int > variables_that_can_be_fixed_to_local_optimum
static constexpr int kDefaultArenaSizePerVariable