OR-Tools  8.2
synchronization.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_SYNCHRONIZATION_H_
15 #define OR_TOOLS_SAT_SYNCHRONIZATION_H_
16 
17 #include <deque>
18 #include <string>
19 #include <vector>
20 
21 #include "absl/random/bit_gen_ref.h"
22 #include "absl/random/random.h"
23 #include "absl/synchronization/mutex.h"
25 #include "ortools/base/logging.h"
26 #include "ortools/base/stl_util.h"
27 #include "ortools/sat/cp_model.pb.h"
28 #include "ortools/sat/integer.h"
29 #include "ortools/sat/model.h"
30 #include "ortools/sat/sat_base.h"
31 #include "ortools/sat/sat_parameters.pb.h"
32 #include "ortools/util/bitset.h"
34 
35 namespace operations_research {
36 namespace sat {
37 
38 // Thread-safe. Keeps a set of n unique best solution found so far.
39 //
40 // TODO(user): Maybe add some criteria to only keep solution with an objective
41 // really close to the best solution.
42 template <typename ValueType>
44  public:
45  explicit SharedSolutionRepository(int num_solutions_to_keep)
46  : num_solutions_to_keep_(num_solutions_to_keep) {
48  }
49 
50  // The solution format used by this class.
51  struct Solution {
52  // Solution with lower "rank" will be preferred
53  //
54  // TODO(user): Some LNS code assume that for the SharedSolutionRepository
55  // this rank is actually the unscaled internal minimization objective.
56  // Remove this assumptions by simply recomputing this value since it is not
57  // too costly to do so.
59 
60  std::vector<ValueType> variable_values;
61 
62  // Number of time this was returned by GetRandomBiasedSolution(). We use
63  // this information during the selection process.
64  //
65  // Should be private: only SharedSolutionRepository should modify this.
66  mutable int num_selected = 0;
67 
68  bool operator==(const Solution& other) const {
69  return rank == other.rank && variable_values == other.variable_values;
70  }
71  bool operator<(const Solution& other) const {
72  if (rank != other.rank) {
73  return rank < other.rank;
74  }
75  return variable_values < other.variable_values;
76  }
77  };
78 
79  // Returns the number of current solution in the pool. This will never
80  // decrease.
81  int NumSolutions() const;
82 
83  // Returns the solution #i where i must be smaller than NumSolutions().
84  Solution GetSolution(int index) const;
85 
86  // Returns the variable value of variable 'var_index' from solution
87  // 'solution_index' where solution_index must be smaller than NumSolutions()
88  // and 'var_index' must be smaller than number of variables.
89  ValueType GetVariableValueInSolution(int var_index, int solution_index) const;
90 
91  // Returns a random solution biased towards good solutions.
92  Solution GetRandomBiasedSolution(absl::BitGenRef random) const;
93 
94  // Add a new solution. Note that it will not be added to the pool of solution
95  // right away. One must call Synchronize for this to happen.
96  //
97  // Works in O(num_solutions_to_keep_).
98  void Add(const Solution& solution);
99 
100  // Updates the current pool of solution with the one recently added. Note that
101  // we use a stable ordering of solutions, so the final pool will be
102  // independent on the order of the calls to AddSolution() provided that the
103  // set of added solutions is the same.
104  //
105  // Works in O(num_solutions_to_keep_).
106  void Synchronize();
107 
108  protected:
109  // Helper method for adding the solutions once the mutex is acquired.
110  void AddInternal(const Solution& solution)
111  ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
112 
114  mutable absl::Mutex mutex_;
115  int64 num_synchronization_ ABSL_GUARDED_BY(mutex_) = 0;
116 
117  // Our two solutions pools, the current one and the new one that will be
118  // merged into the current one on each Synchronize() calls.
119  mutable std::vector<int> tmp_indices_ ABSL_GUARDED_BY(mutex_);
120  std::vector<Solution> solutions_ ABSL_GUARDED_BY(mutex_);
121  std::vector<Solution> new_solutions_ ABSL_GUARDED_BY(mutex_);
122 };
123 
124 // This is currently only used to store feasible solution from our 'relaxation'
125 // LNS generators which in turn are used to generate some RINS neighborhood.
127  : public SharedSolutionRepository<int64> {
128  public:
129  explicit SharedRelaxationSolutionRepository(int num_solutions_to_keep)
130  : SharedSolutionRepository<int64>(num_solutions_to_keep) {}
131 
132  void NewRelaxationSolution(const CpSolverResponse& response);
133 };
134 
136  public:
137  explicit SharedLPSolutionRepository(int num_solutions_to_keep)
138  : SharedSolutionRepository<double>(num_solutions_to_keep) {}
139 
140  void NewLPSolution(std::vector<double> lp_solution);
141 };
142 
143 // Set of partly filled solutions. They are meant to be finished by some lns
144 // worker.
145 //
146 // The solutions are stored as a vector of doubles. The value at index i
147 // represents the solution value of model variable indexed i. Note that some
148 // values can be infinity which should be interpreted as 'unknown' solution
149 // value for that variable. These solutions can not necessarily be completed to
150 // complete feasible solutions.
152  public:
153  bool HasNewSolution() const;
154  std::vector<double> GetNewSolution();
155 
156  void AddNewSolution(const std::vector<double>& lp_solution);
157 
158  private:
159  // New solutions are added and removed from the back.
160  std::vector<std::vector<double>> solutions_;
161  mutable absl::Mutex mutex_;
162 };
163 
164 // Manages the global best response kept by the solver.
165 // All functions are thread-safe.
167  public:
168  // If log_updates is true, then all updates to the global "state" will be
169  // logged. This class is responsible for our solver log progress.
170  SharedResponseManager(bool log_updates, bool enumerate_all_solutions,
171  const CpModelProto* proto, const WallTimer* wall_timer,
172  SharedTimeLimit* shared_time_limit);
173 
174  // Reports OPTIMAL and stop the search if any gap limit are specified and
175  // crossed. By default, we only stop when we have the true optimal, which is
176  // well defined since we are solving our pure integer problem exactly.
177  void SetGapLimitsFromParameters(const SatParameters& parameters);
178 
179  // Returns the current solver response. That is the best known response at the
180  // time of the call with the best feasible solution and objective bounds.
181  //
182  // Note that the solver statistics correspond to the last time a better
183  // solution was found or SetStatsFromModel() was called.
184  CpSolverResponse GetResponse();
185 
186  // Adds a callback that will be called on each new solution (for
187  // statisfiablity problem) or each improving new solution (for an optimization
188  // problem). Returns its id so it can be unregistered if needed.
189  //
190  // Note that currently the class is waiting for the callback to finish before
191  // accepting any new updates. That could be changed if needed.
193  std::function<void(const CpSolverResponse&)> callback);
194  void UnregisterCallback(int callback_id);
195 
196  // The "inner" objective is the CpModelProto objective without scaling/offset.
197  // Note that these bound correspond to valid bound for the problem of finding
198  // a strictly better objective than the current one. Thus the lower bound is
199  // always a valid bound for the global problem, but the upper bound is NOT.
200  IntegerValue GetInnerObjectiveLowerBound();
201  IntegerValue GetInnerObjectiveUpperBound();
202 
203  // These functions return the same as the non-synchronized() version but
204  // only the values at the last time Synchronize() was called.
205  void Synchronize();
208 
209  // Returns the current best solution inner objective value or kInt64Max if
210  // there is no solution.
211  IntegerValue BestSolutionInnerObjectiveValue();
212 
213  // Returns the integral of the log of the absolute gap over deterministic
214  // time. This is mainly used to compare how fast the gap closes on a
215  // particular instance. Or to evaluate how efficient our LNS code is improving
216  // solution.
217  //
218  // Note: The integral will start counting on the first UpdatePrimalIntegral()
219  // call, since before the difference is assumed to be zero.
220  //
221  // Important: To report a proper deterministic integral, we only update it
222  // on UpdatePrimalIntegral() which should be called in the main subsolver
223  // synchronization loop.
224  //
225  // Note(user): In the litterature, people use the relative gap to the optimal
226  // solution (or the best known one), but this is ill defined in many case
227  // (like if the optimal cost is zero), so I prefer this version.
228  double PrimalIntegral() const;
229  void UpdatePrimalIntegral();
230 
231  // Sets this to true to have the "real" but non-deterministic primal integral.
232  // If this is true, then there is no need to manually call
233  // UpdatePrimalIntegral() but it is not an issue to do so.
235 
236  // Updates the inner objective bounds.
237  void UpdateInnerObjectiveBounds(const std::string& update_info,
238  IntegerValue lb, IntegerValue ub);
239 
240  // Reads the new solution from the response and update our state. For an
241  // optimization problem, we only do something if the solution is strictly
242  // improving.
243  //
244  // TODO(user): Only the following fields from response are accessed here, we
245  // might want a tighter API:
246  // - solution_info
247  // - solution
248  // - solution_lower_bounds and solution_upper_bounds.
249  void NewSolution(const CpSolverResponse& response, Model* model);
250 
251  // Changes the solution to reflect the fact that the "improving" problem is
252  // infeasible. This means that if we have a solution, we have proven
253  // optimality, otherwise the global problem is infeasible.
254  //
255  // Note that this shouldn't be called before the solution is actually
256  // reported. We check for this case in NewSolution().
257  void NotifyThatImprovingProblemIsInfeasible(const std::string& worker_info);
258 
259  // Adds to the shared response a subset of assumptions that are enough to
260  // make the problem infeasible.
261  void AddUnsatCore(const std::vector<int>& core);
262 
263  // Sets the statistics in the response to the one of the solver inside the
264  // given in-memory model. This does nothing if the model is nullptr.
265  //
266  // TODO(user): Also support merging statistics together.
268 
269  // Returns true if we found the optimal solution or the problem was proven
270  // infeasible. Note that if the gap limit is reached, we will also report
271  // OPTIMAL and consider the problem solved.
272  bool ProblemIsSolved() const;
273 
274  // Returns the underlying solution repository where we keep a set of best
275  // solutions.
277  return solutions_;
278  }
280  return &solutions_;
281  }
282 
283  // This should be called after the model is loaded. It will read the file
284  // specified by --cp_model_load_debug_solution and properly fill the
285  // model->Get<DebugSolution>() vector.
286  //
287  // TODO(user): Note that for now, only the IntegerVariable value are loaded,
288  // not the value of the pure Booleans variables.
289  void LoadDebugSolution(Model*);
290 
291  // Debug only. Set dump prefix for solutions written to file.
292  void set_dump_prefix(const std::string& dump_prefix) {
293  dump_prefix_ = dump_prefix;
294  }
295 
296  // Display improvement stats.
298 
299  private:
300  void TestGapLimitsIfNeeded() ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
301  void FillObjectiveValuesInBestResponse()
302  ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
303  void SetStatsFromModelInternal(Model* model)
304  ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
305  void UpdatePrimalIntegralInternal() ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
306 
307  void RegisterSolutionFound(const std::string& improvement_info)
308  ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
309  void RegisterObjectiveBoundImprovement(const std::string& improvement_info)
310  ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
311 
312  const bool log_updates_;
313  const bool enumerate_all_solutions_;
314  const CpModelProto& model_proto_;
315  const WallTimer& wall_timer_;
316  SharedTimeLimit* shared_time_limit_;
317 
318  mutable absl::Mutex mutex_;
319 
320  // Gap limits.
321  double absolute_gap_limit_ ABSL_GUARDED_BY(mutex_) = 0.0;
322  double relative_gap_limit_ ABSL_GUARDED_BY(mutex_) = 0.0;
323 
324  CpSolverResponse best_response_ ABSL_GUARDED_BY(mutex_);
325  SharedSolutionRepository<int64> solutions_ ABSL_GUARDED_BY(mutex_);
326 
327  int num_solutions_ ABSL_GUARDED_BY(mutex_) = 0;
328  int64 inner_objective_lower_bound_ ABSL_GUARDED_BY(mutex_) = kint64min;
329  int64 inner_objective_upper_bound_ ABSL_GUARDED_BY(mutex_) = kint64max;
330  int64 best_solution_objective_value_ ABSL_GUARDED_BY(mutex_) = kint64max;
331 
332  IntegerValue synchronized_inner_objective_lower_bound_
333  ABSL_GUARDED_BY(mutex_) = IntegerValue(kint64min);
334  IntegerValue synchronized_inner_objective_upper_bound_
335  ABSL_GUARDED_BY(mutex_) = IntegerValue(kint64max);
336 
337  bool update_integral_on_each_change_ ABSL_GUARDED_BY(mutex_) = false;
338  double primal_integral_ ABSL_GUARDED_BY(mutex_) = 0.0;
339  double last_absolute_gap_ ABSL_GUARDED_BY(mutex_) = 0.0;
340  double last_primal_integral_time_stamp_ ABSL_GUARDED_BY(mutex_) = 0.0;
341 
342  int next_callback_id_ ABSL_GUARDED_BY(mutex_) = 0;
343  std::vector<std::pair<int, std::function<void(const CpSolverResponse&)>>>
344  callbacks_ ABSL_GUARDED_BY(mutex_);
345 
346  // Dump prefix.
347  std::string dump_prefix_;
348 
349  // Used for statistics of the improvements found by workers.
350  std::map<std::string, int> primal_improvements_count_ ABSL_GUARDED_BY(mutex_);
351  std::map<std::string, int> dual_improvements_count_ ABSL_GUARDED_BY(mutex_);
352 };
353 
354 // This class manages a pool of lower and upper bounds on a set of variables in
355 // a parallel context.
357  public:
358  explicit SharedBoundsManager(const CpModelProto& model_proto);
359 
360  // Reports a set of locally improved variable bounds to the shared bounds
361  // manager. The manager will compare these bounds changes against its
362  // global state, and incorporate the improving ones.
363  void ReportPotentialNewBounds(const CpModelProto& model_proto,
364  const std::string& worker_name,
365  const std::vector<int>& variables,
366  const std::vector<int64>& new_lower_bounds,
367  const std::vector<int64>& new_upper_bounds);
368 
369  // Returns a new id to be used in GetChangedBounds(). This is just an ever
370  // increasing sequence starting from zero. Note that the class is not designed
371  // to have too many of these.
372  int RegisterNewId();
373 
374  // When called, returns the set of bounds improvements since
375  // the last time this method was called with the same id.
376  void GetChangedBounds(int id, std::vector<int>* variables,
377  std::vector<int64>* new_lower_bounds,
378  std::vector<int64>* new_upper_bounds);
379 
380  // Publishes any new bounds so that GetChangedBounds() will reflect the latest
381  // state.
382  void Synchronize();
383 
384  private:
385  const int num_variables_;
386  const CpModelProto& model_proto_;
387 
388  absl::Mutex mutex_;
389 
390  // These are always up to date.
391  std::vector<int64> lower_bounds_ ABSL_GUARDED_BY(mutex_);
392  std::vector<int64> upper_bounds_ ABSL_GUARDED_BY(mutex_);
393  SparseBitset<int64> changed_variables_since_last_synchronize_
394  ABSL_GUARDED_BY(mutex_);
395 
396  // These are only updated on Synchronize().
397  std::vector<int64> synchronized_lower_bounds_ ABSL_GUARDED_BY(mutex_);
398  std::vector<int64> synchronized_upper_bounds_ ABSL_GUARDED_BY(mutex_);
399  std::deque<SparseBitset<int64>> id_to_changed_variables_
400  ABSL_GUARDED_BY(mutex_);
401 };
402 
403 template <typename ValueType>
405  absl::MutexLock mutex_lock(&mutex_);
406  return solutions_.size();
407 }
408 
409 template <typename ValueType>
412  absl::MutexLock mutex_lock(&mutex_);
413  return solutions_[i];
414 }
415 
416 template <typename ValueType>
418  int var_index, int solution_index) const {
419  absl::MutexLock mutex_lock(&mutex_);
420  return solutions_[solution_index].variable_values[var_index];
421 }
422 
423 // TODO(user): Experiments on the best distribution.
424 template <typename ValueType>
427  absl::BitGenRef random) const {
428  absl::MutexLock mutex_lock(&mutex_);
429  const int64 best_rank = solutions_[0].rank;
430 
431  // As long as we have solution with the best objective that haven't been
432  // explored too much, we select one uniformly. Otherwise, we select a solution
433  // from the pool uniformly.
434  //
435  // Note(user): Because of the increase of num_selected, this is dependent on
436  // the order of call. It should be fine for "determinism" because we do
437  // generate the task of a batch always in the same order.
438  const int kExplorationThreshold = 100;
439 
440  // Select all the best solution with a low enough selection count.
441  tmp_indices_.clear();
442  for (int i = 0; i < solutions_.size(); ++i) {
443  const auto& solution = solutions_[i];
444  if (solution.rank == best_rank &&
445  solution.num_selected <= kExplorationThreshold) {
446  tmp_indices_.push_back(i);
447  }
448  }
449 
450  int index = 0;
451  if (tmp_indices_.empty()) {
452  index = absl::Uniform<int>(random, 0, solutions_.size());
453  } else {
454  index = tmp_indices_[absl::Uniform<int>(random, 0, tmp_indices_.size())];
455  }
456  solutions_[index].num_selected++;
457  return solutions_[index];
458 }
459 
460 template <typename ValueType>
462  absl::MutexLock mutex_lock(&mutex_);
463  AddInternal(solution);
464 }
465 
466 template <typename ValueType>
468  const Solution& solution) {
469  int worse_solution_index = 0;
470  for (int i = 0; i < new_solutions_.size(); ++i) {
471  // Do not add identical solution.
472  if (new_solutions_[i] == solution) return;
473  if (new_solutions_[worse_solution_index] < new_solutions_[i]) {
474  worse_solution_index = i;
475  }
476  }
477  if (new_solutions_.size() < num_solutions_to_keep_) {
478  new_solutions_.push_back(solution);
479  } else if (solution < new_solutions_[worse_solution_index]) {
480  new_solutions_[worse_solution_index] = solution;
481  }
482 }
483 
484 template <typename ValueType>
486  absl::MutexLock mutex_lock(&mutex_);
487  solutions_.insert(solutions_.end(), new_solutions_.begin(),
488  new_solutions_.end());
489  new_solutions_.clear();
490 
491  // We use a stable sort to keep the num_selected count for the already
492  // existing solutions.
493  //
494  // TODO(user): Intoduce a notion of orthogonality to diversify the pool?
496  if (solutions_.size() > num_solutions_to_keep_) {
497  solutions_.resize(num_solutions_to_keep_);
498  }
499  num_synchronization_++;
500 }
501 
502 } // namespace sat
503 } // namespace operations_research
504 
505 #endif // OR_TOOLS_SAT_SYNCHRONIZATION_H_
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
void AddNewSolution(const std::vector< double > &lp_solution)
void NewLPSolution(std::vector< double > lp_solution)
void NewRelaxationSolution(const CpSolverResponse &response)
SharedResponseManager(bool log_updates, bool enumerate_all_solutions, const CpModelProto *proto, const WallTimer *wall_timer, SharedTimeLimit *shared_time_limit)
const SharedSolutionRepository< int64 > & SolutionsRepository() const
SharedSolutionRepository< int64 > * MutableSolutionsRepository()
void set_dump_prefix(const std::string &dump_prefix)
void NewSolution(const CpSolverResponse &response, Model *model)
void NotifyThatImprovingProblemIsInfeasible(const std::string &worker_info)
void AddUnsatCore(const std::vector< int > &core)
void SetGapLimitsFromParameters(const SatParameters &parameters)
int AddSolutionCallback(std::function< void(const CpSolverResponse &)> callback)
void UpdateInnerObjectiveBounds(const std::string &update_info, IntegerValue lb, IntegerValue ub)
Solution GetRandomBiasedSolution(absl::BitGenRef random) const
std::vector< int > tmp_indices_ ABSL_GUARDED_BY(mutex_)
int64 num_synchronization_ ABSL_GUARDED_BY(mutex_)=0
std::vector< Solution > new_solutions_ ABSL_GUARDED_BY(mutex_)
void AddInternal(const Solution &solution) ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_)
ValueType GetVariableValueInSolution(int var_index, int solution_index) const
std::vector< Solution > solutions_ ABSL_GUARDED_BY(mutex_)
SatParameters parameters
CpModelProto proto
CpModelProto const * model_proto
SharedResponseManager * response
WallTimer * wall_timer
GRBmodel * model
MPCallback * callback
static const int64 kint64max
int64_t int64
static const int64 kint64min
Definition: cleanup.h:22
void STLStableSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
Definition: stl_util.h:75
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int index
Definition: pack.cc:508