OR-Tools  8.2
cp_model_lns.h
Go to the documentation of this file.
1// Copyright 2010-2018 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 <vector>
18
19#include "absl/container/flat_hash_map.h"
20#include "absl/random/bit_gen_ref.h"
21#include "absl/synchronization/mutex.h"
22#include "absl/types/span.h"
24#include "ortools/sat/cp_model.pb.h"
25#include "ortools/sat/model.h"
29
30namespace operations_research {
31namespace sat {
32
33// Neighborhood returned by Neighborhood generators.
35 // True if neighborhood generator was able to generate a neighborhood.
36 bool is_generated = false;
37
38 // True if the CpModelProto below is not the same as the base model.
39 // This is not expected to happen often but allows to handle this case
40 // properly.
41 bool is_reduced = false;
42
43 // Relaxed model. Any feasible solution to this "local" model should be a
44 // feasible solution to the base model too.
45 CpModelProto cp_model;
46
47 // Neighborhood Id. Used to identify the neighborhood by a generator.
48 // Currently only used by WeightedRandomRelaxationNeighborhoodGenerator.
49 // TODO(user): Make sure that the id is unique for each generated
50 // neighborhood for each generator.
51 int64 id = 0;
52
53 // Used for identifying the source of the neighborhood if it is generated
54 // using solution repositories.
55 std::string source_info = "";
56};
57
58// Contains pre-computed information about a given CpModelProto that is meant
59// to be used to generate LNS neighborhood. This class can be shared between
60// more than one generator in order to reduce memory usage.
61//
62// Note that its implement the SubSolver interface to be able to Synchronize()
63// the bounds of the base problem with the external world.
65 public:
66 NeighborhoodGeneratorHelper(CpModelProto const* model_proto,
67 SatParameters const* parameters,
69 SharedTimeLimit* shared_time_limit = nullptr,
70 SharedBoundsManager* shared_bounds = nullptr);
71
72 // SubSolver interface.
73 bool TaskIsAvailable() override { return false; }
74 std::function<void()> GenerateTask(int64 task_id) override { return {}; }
75 void Synchronize() override;
76
77 // Returns the LNS fragment where the given variables are fixed to the value
78 // they take in the given solution.
80 const CpSolverResponse& initial_solution,
81 const std::vector<int>& variables_to_fix) const;
82
83 // Returns the neighborhood where the given constraints are removed.
85 const std::vector<int>& constraints_to_remove) const;
86
87 // Returns the LNS fragment which will relax all inactive variables and all
88 // variables in relaxed_variables.
90 const CpSolverResponse& initial_solution,
91 const std::vector<int>& relaxed_variables) const;
92
93 // Returns a trivial model by fixing all active variables to the initial
94 // solution values.
95 Neighborhood FixAllVariables(const CpSolverResponse& initial_solution) const;
96
97 // Return a neighborhood that correspond to the full problem.
99
100 // Indicates if the variable can be frozen. It happens if the variable is non
101 // constant, and if it is a decision variable, or if
102 // focus_on_decision_variables is false.
103 bool IsActive(int var) const;
104
105 // Returns the list of "active" variables.
106 const std::vector<int>& ActiveVariables() const { return active_variables_; }
107
108 // Constraints <-> Variables graph.
109 // Note that only non-constant variable are listed here.
110 const std::vector<std::vector<int>>& ConstraintToVar() const {
111 return constraint_to_var_;
112 }
113 const std::vector<std::vector<int>>& VarToConstraint() const {
114 return var_to_constraint_;
115 }
116
117 // Returns all the constraints indices of a given type.
118 const absl::Span<const int> TypeToConstraints(
119 ConstraintProto::ConstraintCase type) const {
120 if (type >= type_to_constraints_.size()) return {};
121 return absl::MakeSpan(type_to_constraints_[type]);
122 }
123
124 // Returns the list of indices of active interval constraints according
125 // to the initial_solution and the parameter lns_focus_on_performed_intervals.
126 // If true, this method returns the list of performed intervals in the
127 // solution. If false, it returns all intervals of the model.
128 std::vector<int> GetActiveIntervals(
129 const CpSolverResponse& initial_solution) const;
130
131 // The initial problem.
132 // Note that the domain of the variables are not updated here.
133 const CpModelProto& ModelProto() const { return model_proto_; }
134 const SatParameters& Parameters() const { return parameters_; }
135
136 // This mutex must be acquired before calling any of the function that access
137 // data that can be updated by Synchronize().
138 //
139 // TODO(user): Refactor the class to be thread-safe instead, it should be
140 // safer and more easily maintenable. Some complication with accessing the
141 // variable<->constraint graph efficiently though.
142 absl::Mutex* MutableMutex() const { return &mutex_; }
143
145 return *shared_response_;
146 }
147
148 private:
149 // Recompute most of the class member. This needs to be called when the
150 // domains of the variables are updated.
151 void RecomputeHelperData();
152
153 // Indicates if a variable is fixed in the model.
154 bool IsConstant(int var) const;
155
156 const SatParameters& parameters_;
157 const CpModelProto& model_proto_;
158 int shared_bounds_id_;
159 SharedTimeLimit* shared_time_limit_;
160 SharedBoundsManager* shared_bounds_;
161 SharedResponseManager* shared_response_;
162 SharedRelaxationSolutionRepository* shared_relaxation_solutions_;
163
164 // This proto will only contain the field variables() with an updated version
165 // of the domains compared to model_proto_.variables(). We do it like this to
166 // reduce the memory footprint of the helper when the model is large.
167 //
168 // TODO(user): Use custom domain repository rather than a proto?
169 CpModelProto model_proto_with_only_variables_;
170
171 mutable absl::Mutex mutex_;
172
173 // Constraints by types.
174 std::vector<std::vector<int>> type_to_constraints_;
175
176 // Variable-Constraint graph.
177 std::vector<std::vector<int>> constraint_to_var_;
178 std::vector<std::vector<int>> var_to_constraint_;
179
180 // The set of active variables, that is the list of non constant variables if
181 // parameters_.focus_on_decision_variables() is false, or the list of non
182 // constant decision variables otherwise. It is stored both as a list and as a
183 // set (using a Boolean vector).
184 std::vector<bool> active_variables_set_;
185 std::vector<int> active_variables_;
186};
187
188// Base class for a CpModelProto neighborhood generator.
190 public:
191 NeighborhoodGenerator(const std::string& name,
192 NeighborhoodGeneratorHelper const* helper)
193 : name_(name), helper_(*helper), difficulty_(0.5) {}
195
196 // Generates a "local" subproblem for the given seed.
197 //
198 // The difficulty will be in [0, 1] and is related to the asked neighborhood
199 // size (and thus local problem difficulty). A difficulty of 0.0 means empty
200 // neighborhood and a difficulty of 1.0 means the full problem. The algorithm
201 // should try to generate a neighborhood according to this difficulty which
202 // will be dynamically adjusted depending on whether or not we can solve the
203 // subproblem in a given time limit.
204 //
205 // The given initial_solution should contain a feasible solution to the
206 // initial CpModelProto given to this class. Any solution to the returned
207 // CPModelProto should also be valid solution to the same initial model.
208 //
209 // This function should be thread-safe.
210 virtual Neighborhood Generate(const CpSolverResponse& initial_solution,
211 double difficulty, absl::BitGenRef random) = 0;
212
213 // Returns true if the neighborhood generator can generate a neighborhood.
214 virtual bool ReadyToGenerate() const;
215
216 // Returns true if the neighborhood generator generates relaxation of the
217 // given problem.
218 virtual bool IsRelaxationGenerator() const { return false; }
219
220 // Uses UCB1 algorithm to compute the score (Multi armed bandit problem).
221 // Details are at
222 // https://lilianweng.github.io/lil-log/2018/01/23/the-multi-armed-bandit-problem-and-its-solutions.html.
223 // 'total_num_calls' should be the sum of calls across all generators part of
224 // the multi armed bandit problem.
225 // If the generator is called less than 10 times then the method returns
226 // infinity as score in order to get more data about the generator
227 // performance.
228 double GetUCBScore(int64 total_num_calls) const;
229
230 // Adds solve data about one "solved" neighborhood.
231 struct SolveData {
232 // Neighborhood Id. Used to identify the neighborhood by a generator.
233 // Currently only used by WeightedRandomRelaxationNeighborhoodGenerator.
235
236 // The status of the sub-solve.
237 CpSolverStatus status = CpSolverStatus::UNKNOWN;
238
239 // The difficulty when this neighborhood was generated.
240 double difficulty = 0.0;
241
242 // The determinitic time limit given to the solver for this neighborhood.
244
245 // The time it took to solve this neighborhood.
246 double deterministic_time = 0.0;
247
248 // Objective information. These only refer to the "internal" objective
249 // without scaling or offset so we are exact and it is always in the
250 // minimization direction.
251 // - The initial best objective is the one of the best known solution at the
252 // time the neighborhood was generated.
253 // - The base objective is the one of the base solution from which this
254 // neighborhood was generated.
255 // - The new objective is the objective of the best solution found by
256 // solving the neighborhood.
257 IntegerValue initial_best_objective = IntegerValue(0);
258 IntegerValue base_objective = IntegerValue(0);
259 IntegerValue new_objective = IntegerValue(0);
260
261 // Bounds data is only used by relaxation neighborhoods.
262 IntegerValue initial_best_objective_bound = IntegerValue(0);
263 IntegerValue new_objective_bound = IntegerValue(0);
264
265 // This is just used to construct a deterministic order for the updates.
266 bool operator<(const SolveData& o) const {
267 return std::tie(status, difficulty, deterministic_limit,
272 std::tie(o.status, o.difficulty, o.deterministic_limit,
277 }
278 };
280 absl::MutexLock mutex_lock(&mutex_);
281 solve_data_.push_back(data);
282 }
283
284 // Process all the recently added solve data and update this generator
285 // score and difficulty.
286 void Synchronize();
287
288 // Returns a short description of the generator.
289 std::string name() const { return name_; }
290
291 // Number of times this generator was called.
292 int64 num_calls() const {
293 absl::MutexLock mutex_lock(&mutex_);
294 return num_calls_;
295 }
296
297 // Number of time the neighborhood was fully solved (OPTIMAL/INFEASIBLE).
299 absl::MutexLock mutex_lock(&mutex_);
300 return num_fully_solved_calls_;
301 }
302
303 // The current difficulty of this generator
304 double difficulty() const {
305 absl::MutexLock mutex_lock(&mutex_);
306 return difficulty_.value();
307 }
308
309 // The current time limit that the sub-solve should use on this generator.
310 double deterministic_limit() const {
311 absl::MutexLock mutex_lock(&mutex_);
312 return deterministic_limit_;
313 }
314
315 // The sum of the deterministic time spent in this generator.
316 double deterministic_time() const {
317 absl::MutexLock mutex_lock(&mutex_);
318 return deterministic_time_;
319 }
320
321 protected:
322 // Triggered with each call to Synchronize() for each recently added
323 // SolveData. This is meant to be used for processing feedbacks by specific
324 // neighborhood generators to adjust the neighborhood generation process.
325 virtual void AdditionalProcessingOnSynchronize(const SolveData& solve_data) {}
326
327 const std::string name_;
329 mutable absl::Mutex mutex_;
330
331 private:
332 std::vector<SolveData> solve_data_;
333
334 // Current parameters to be used when generating/solving a neighborhood with
335 // this generator. Only updated on Synchronize().
336 AdaptiveParameterValue difficulty_;
337 double deterministic_limit_ = 0.1;
338
339 // Current statistics of the last solved neighborhood.
340 // Only updated on Synchronize().
341 int64 num_calls_ = 0;
342 int64 num_fully_solved_calls_ = 0;
343 int64 num_consecutive_non_improving_calls_ = 0;
344 double deterministic_time_ = 0.0;
345 double current_average_ = 0.0;
346};
347
348// Pick a random subset of variables.
350 public:
352 NeighborhoodGeneratorHelper const* helper, const std::string& name)
353 : NeighborhoodGenerator(name, helper) {}
354 Neighborhood Generate(const CpSolverResponse& initial_solution,
355 double difficulty, absl::BitGenRef random) final;
356};
357
358// Pick a random subset of constraints and relax all the variables of these
359// constraints. Note that to satisfy the difficulty, we might not relax all the
360// variable of the "last" constraint.
362 public:
364 NeighborhoodGeneratorHelper const* helper, const std::string& name)
365 : NeighborhoodGenerator(name, helper) {}
366 Neighborhood Generate(const CpSolverResponse& initial_solution,
367 double difficulty, absl::BitGenRef random) final;
368};
369
370// Pick a random subset of variables that are constructed by a BFS in the
371// variable <-> constraint graph. That is, pick a random variable, then all the
372// variable connected by some constraint to the first one, and so on. The
373// variable of the last "level" are selected randomly.
375 public:
377 NeighborhoodGeneratorHelper const* helper, const std::string& name)
378 : NeighborhoodGenerator(name, helper) {}
379 Neighborhood Generate(const CpSolverResponse& initial_solution,
380 double difficulty, absl::BitGenRef random) final;
381};
382
383// Pick a random subset of constraint and relax all of their variables. We are a
384// bit smarter than this because after the first constraint is selected, we only
385// select constraints that share at least one variable with the already selected
386// constraints. The variable from the "last" constraint are selected randomly.
388 public:
390 NeighborhoodGeneratorHelper const* helper, const std::string& name)
391 : NeighborhoodGenerator(name, helper) {}
392 Neighborhood Generate(const CpSolverResponse& initial_solution,
393 double difficulty, absl::BitGenRef random) final;
394};
395
396// Helper method for the scheduling neighborhood generators. Returns the model
397// as neighborhood for the given set of intervals to relax. For each no_overlap
398// constraints, it adds strict relation order between the non-relaxed intervals.
400 const absl::Span<const int> intervals_to_relax,
401 const CpSolverResponse& initial_solution,
402 const NeighborhoodGeneratorHelper& helper);
403
404// Only make sense for scheduling problem. This select a random set of interval
405// of the problem according to the difficulty. Then, for each no_overlap
406// constraints, it adds strict relation order between the non-relaxed intervals.
407//
408// TODO(user): Also deal with cumulative constraint.
410 public:
412 NeighborhoodGeneratorHelper const* helper, const std::string& name)
413 : NeighborhoodGenerator(name, helper) {}
414
415 Neighborhood Generate(const CpSolverResponse& initial_solution,
416 double difficulty, absl::BitGenRef random) final;
417};
418
419// Similar to SchedulingNeighborhoodGenerator except the set of intervals that
420// are relaxed are from a specific random time interval.
422 public:
424 NeighborhoodGeneratorHelper const* helper, const std::string& name)
425 : NeighborhoodGenerator(name, helper) {}
426
427 Neighborhood Generate(const CpSolverResponse& initial_solution,
428 double difficulty, absl::BitGenRef random) final;
429};
430
431// Generates a neighborhood by fixing the variables to solutions reported in
432// various repositories. This is inspired from RINS published in "Exploring
433// relaxation induced neighborhoods to improve MIP solutions" 2004 by E. Danna
434// et.
435//
436// If incomplete_solutions is provided, this generates a neighborhood by fixing
437// the variable values to a solution in the SharedIncompleteSolutionManager and
438// ignores the other repositories.
439//
440// Otherwise, if response_manager is not provided, this generates a neighborhood
441// using only the linear/general relaxation values. The domain of the variables
442// are reduced to the integer values around their lp solution/relaxation
443// solution values. This was published in "RENS – The Relaxation Enforced
444// Neighborhood" 2009 by Timo Berthold.
446 public:
448 NeighborhoodGeneratorHelper const* helper,
449 const SharedResponseManager* response_manager,
453 const std::string& name)
454 : NeighborhoodGenerator(name, helper),
455 response_manager_(response_manager),
456 relaxation_solutions_(relaxation_solutions),
457 lp_solutions_(lp_solutions),
458 incomplete_solutions_(incomplete_solutions) {
459 CHECK(lp_solutions_ != nullptr || relaxation_solutions_ != nullptr ||
460 incomplete_solutions != nullptr);
461 }
462
463 // Both initial solution and difficulty values are ignored.
464 Neighborhood Generate(const CpSolverResponse& initial_solution,
465 double difficulty, absl::BitGenRef random) final;
466
467 // Returns true if the required solutions are available.
468 bool ReadyToGenerate() const override;
469
470 private:
471 const SharedResponseManager* response_manager_;
472 const SharedRelaxationSolutionRepository* relaxation_solutions_;
473 const SharedLPSolutionRepository* lp_solutions_;
474 SharedIncompleteSolutionManager* incomplete_solutions_;
475};
476
477// Generates a relaxation of the original model by removing a consecutive span
478// of constraints starting at a random index. The number of constraints removed
479// is in sync with the difficulty passed to the generator.
481 : public NeighborhoodGenerator {
482 public:
484 NeighborhoodGeneratorHelper const* helper, const std::string& name)
485 : NeighborhoodGenerator(name, helper) {}
486 Neighborhood Generate(const CpSolverResponse& initial_solution,
487 double difficulty, absl::BitGenRef random) final;
488
489 bool IsRelaxationGenerator() const override { return true; }
490 bool ReadyToGenerate() const override { return true; }
491};
492
493// Generates a relaxation of the original model by removing some constraints
494// randomly with a given weight for each constraint that controls the
495// probability of constraint getting removed. The number of constraints removed
496// is in sync with the difficulty passed to the generator. Higher weighted
497// constraints are more likely to get removed.
499 : public NeighborhoodGenerator {
500 public:
502 NeighborhoodGeneratorHelper const* helper, const std::string& name);
503
504 // Generates the neighborhood as described above. Also stores the removed
505 // constraints indices for adjusting the weights.
506 Neighborhood Generate(const CpSolverResponse& initial_solution,
507 double difficulty, absl::BitGenRef random) final;
508
509 bool IsRelaxationGenerator() const override { return true; }
510 bool ReadyToGenerate() const override { return true; }
511
512 private:
513 // Adjusts the weights of the constraints removed to get the neighborhood
514 // based on the solve_data.
515 void AdditionalProcessingOnSynchronize(const SolveData& solve_data) override
516 ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
517
518 // Higher weighted constraints are more likely to get removed.
519 std::vector<double> constraint_weights_;
520 int num_removable_constraints_ = 0;
521
522 // Indices of the removed constraints per generated neighborhood.
523 absl::flat_hash_map<int64, std::vector<int>> removed_constraints_
524 ABSL_GUARDED_BY(mutex_);
525
526 // TODO(user): Move this to parent class if other generators start using
527 // feedbacks.
528 int64 next_available_id_ ABSL_GUARDED_BY(mutex_) = 0;
529};
530
531} // namespace sat
532} // namespace operations_research
533
534#endif // OR_TOOLS_SAT_CP_MODEL_LNS_H_
#define CHECK(condition)
Definition: base/logging.h:495
ConsecutiveConstraintsRelaxationNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
Definition: cp_model_lns.h:483
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
ConstraintGraphNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
Definition: cp_model_lns.h:389
NeighborhoodGeneratorHelper(CpModelProto const *model_proto, SatParameters const *parameters, SharedResponseManager *shared_response, SharedTimeLimit *shared_time_limit=nullptr, SharedBoundsManager *shared_bounds=nullptr)
Definition: cp_model_lns.cc:32
std::function< void()> GenerateTask(int64 task_id) override
Definition: cp_model_lns.h:74
Neighborhood FixAllVariables(const CpSolverResponse &initial_solution) const
Neighborhood FixGivenVariables(const CpSolverResponse &initial_solution, const std::vector< int > &variables_to_fix) const
const absl::Span< const int > TypeToConstraints(ConstraintProto::ConstraintCase type) const
Definition: cp_model_lns.h:118
const std::vector< int > & ActiveVariables() const
Definition: cp_model_lns.h:106
Neighborhood RelaxGivenVariables(const CpSolverResponse &initial_solution, const std::vector< int > &relaxed_variables) const
std::vector< int > GetActiveIntervals(const CpSolverResponse &initial_solution) const
const SharedResponseManager & shared_response() const
Definition: cp_model_lns.h:144
const std::vector< std::vector< int > > & ConstraintToVar() const
Definition: cp_model_lns.h:110
Neighborhood RemoveMarkedConstraints(const std::vector< int > &constraints_to_remove) const
const std::vector< std::vector< int > > & VarToConstraint() const
Definition: cp_model_lns.h:113
virtual Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random)=0
NeighborhoodGenerator(const std::string &name, NeighborhoodGeneratorHelper const *helper)
Definition: cp_model_lns.h:191
double GetUCBScore(int64 total_num_calls) const
virtual void AdditionalProcessingOnSynchronize(const SolveData &solve_data)
Definition: cp_model_lns.h:325
const NeighborhoodGeneratorHelper & helper_
Definition: cp_model_lns.h:328
RelaxationInducedNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const SharedResponseManager *response_manager, const SharedRelaxationSolutionRepository *relaxation_solutions, const SharedLPSolutionRepository *lp_solutions, SharedIncompleteSolutionManager *incomplete_solutions, const std::string &name)
Definition: cp_model_lns.h:447
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
SchedulingNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
Definition: cp_model_lns.h:411
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
SchedulingTimeWindowNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
Definition: cp_model_lns.h:423
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
SimpleConstraintNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
Definition: cp_model_lns.h:363
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
SimpleNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
Definition: cp_model_lns.h:351
VariableGraphNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
Definition: cp_model_lns.h:376
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
WeightedRandomRelaxationNeighborhoodGenerator(NeighborhoodGeneratorHelper const *helper, const std::string &name)
Neighborhood Generate(const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
SatParameters parameters
SharedRelaxationSolutionRepository * relaxation_solutions
SharedLPSolutionRepository * lp_solutions
CpModelProto const * model_proto
SharedIncompleteSolutionManager * incomplete_solutions
IntVar * var
Definition: expr_array.cc:1858
int64_t int64
Neighborhood GenerateSchedulingNeighborhoodForRelaxation(const absl::Span< const int > intervals_to_relax, const CpSolverResponse &initial_solution, const NeighborhoodGeneratorHelper &helper)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...