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"
26 #include "ortools/sat/subsolver.h"
29 
30 namespace operations_research {
31 namespace sat {
32 
33 // Neighborhood returned by Neighborhood generators.
34 struct Neighborhood {
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.
243  double deterministic_limit = 0.0;
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,
271  neighborhood_id) <
272  std::tie(o.status, o.difficulty, o.deterministic_limit,
276  o.neighborhood_id);
277  }
278  };
279  void AddSolveData(SolveData data) {
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
const SharedResponseManager & shared_response() const
Definition: cp_model_lns.h:144
const std::vector< std::vector< int > > & VarToConstraint() const
Definition: cp_model_lns.h:113
Neighborhood FixAllVariables(const CpSolverResponse &initial_solution) const
Neighborhood FixGivenVariables(const CpSolverResponse &initial_solution, const std::vector< int > &variables_to_fix) const
std::function< void()> GenerateTask(int64 task_id) override
Definition: cp_model_lns.h:74
const absl::Span< const int > TypeToConstraints(ConstraintProto::ConstraintCase type) const
Definition: cp_model_lns.h:118
Neighborhood RelaxGivenVariables(const CpSolverResponse &initial_solution, const std::vector< int > &relaxed_variables) const
std::vector< int > GetActiveIntervals(const CpSolverResponse &initial_solution) const
const std::vector< int > & ActiveVariables() const
Definition: cp_model_lns.h:106
Neighborhood RemoveMarkedConstraints(const std::vector< int > &constraints_to_remove) const
const std::vector< std::vector< int > > & ConstraintToVar() const
Definition: cp_model_lns.h:110
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...