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"
27#include "ortools/sat/cp_model.pb.h"
28#include "ortools/sat/integer.h"
29#include "ortools/sat/model.h"
31#include "ortools/sat/sat_parameters.pb.h"
32#include "ortools/util/bitset.h"
34
35namespace operations_research {
36namespace 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.
42template <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_).
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;
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.
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
403template <typename ValueType>
405 absl::MutexLock mutex_lock(&mutex_);
406 return solutions_.size();
407}
408
409template <typename ValueType>
412 absl::MutexLock mutex_lock(&mutex_);
413 return solutions_[i];
414}
415
416template <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.
424template <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
460template <typename ValueType>
462 absl::MutexLock mutex_lock(&mutex_);
463 AddInternal(solution);
464}
465
466template <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
484template <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)
void set_dump_prefix(const std::string &dump_prefix)
const SharedSolutionRepository< int64 > & SolutionsRepository() const
SharedSolutionRepository< int64 > * MutableSolutionsRepository()
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)
std::vector< Solution > new_solutions_ ABSL_GUARDED_BY(mutex_)
Solution GetRandomBiasedSolution(absl::BitGenRef random) const
int64 num_synchronization_ ABSL_GUARDED_BY(mutex_)=0
std::vector< int > tmp_indices_ ABSL_GUARDED_BY(mutex_)
std::vector< Solution > solutions_ ABSL_GUARDED_BY(mutex_)
void AddInternal(const Solution &solution) ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_)
ValueType GetVariableValueInSolution(int var_index, int solution_index) const
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...
STL namespace.
int index
Definition: pack.cc:508