Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
util.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_SAT_UTIL_H_
15#define OR_TOOLS_SAT_UTIL_H_
16
17#include <algorithm>
18#include <cmath>
19#include <cstddef>
20#include <cstdint>
21#include <deque>
22#include <limits>
23#include <memory>
24#include <string>
25#include <type_traits>
26#include <utility>
27#include <vector>
28
29#include "absl/container/btree_set.h"
30#include "absl/log/check.h"
31#include "absl/log/log_streamer.h"
32#include "absl/numeric/int128.h"
33#include "absl/random/bit_gen_ref.h"
34#include "absl/random/random.h"
35#include "absl/strings/str_cat.h"
36#include "absl/strings/string_view.h"
37#include "absl/types/span.h"
39#include "ortools/sat/model.h"
41#include "ortools/sat/sat_parameters.pb.h"
46
47namespace operations_research {
48namespace sat {
49
50// A simple class with always IdentityMap[t] == t.
51// This is to avoid allocating vector with std::iota() in some Apis.
52template <typename T>
54 public:
55 T operator[](T t) const { return t; }
56};
57
58// Small utility class to store a vector<vector<>> where one can only append new
59// vector and never change previously added ones. This allows to store a static
60// key -> value(s) mapping.
61//
62// This is a lot more compact memorywise and thus faster than vector<vector<>>.
63// Note that we implement a really small subset of the vector<vector<>> API.
64//
65// We support int and StrongType for key K and any copyable type for value V.
66template <typename K = int, typename V = int>
68 public:
69 using value_type = V;
70
71 // Size of the "key" space, always in [0, size()).
72 size_t size() const;
73 bool empty() const;
74 size_t num_entries() const { return buffer_.size(); }
75
76 // Getters, either via [] or via a wrapping to be compatible with older api.
77 //
78 // Warning: Spans are only valid until the next modification!
79 absl::Span<V> operator[](K key);
80 absl::Span<const V> operator[](K key) const;
81 std::vector<absl::Span<const V>> AsVectorOfSpan() const;
82
83 // Restore to empty vector<vector<>>.
84 void clear();
85
86 // Reserve memory if it is already known or tightly estimated.
87 void reserve(int size) {
88 starts_.reserve(size);
89 sizes_.reserve(size);
90 }
91 void reserve(int size, int num_entries) {
93 buffer_.reserve(num_entries);
94 }
95
96 // Given a flat mapping (keys[i] -> values[i]) with two parallel vectors, not
97 // necessarily sorted by key, regroup the same key so that
98 // CompactVectorVector[key] list all values in the order in which they appear.
99 //
100 // We only check keys.size(), so this can be used with IdentityMap() as
101 // second argument.
102 template <typename Keys, typename Values>
103 void ResetFromFlatMapping(Keys keys, Values values);
104
105 // Same as above but for any collections of std::pair<K, V>, or, more
106 // generally, any iterable collection of objects that have a `first` and a
107 // `second` members.
108 template <typename Collection>
109 void ResetFromPairs(const Collection& pairs, int minimum_num_nodes = 0);
110
111 // Initialize this vector from the transpose of another.
112 // IMPORTANT: This cannot be called with the vector itself.
113 //
114 // If min_transpose_size is given, then the transpose will have at least this
115 // size even if some of the last keys do not appear in other.
116 //
117 // If this is called twice in a row, then it has the side effect of sorting
118 // all inner vectors by values !
120 int min_transpose_size = 0);
121
122 // Append a new entry.
123 // Returns the previous size() as this is convenient for how we use it.
124 int Add(absl::Span<const V> values);
125 void AppendToLastVector(const V& value);
126
127 // Hacky: same as Add() but for sat::Literal or any type from which we can get
128 // a value type V via L.Index().value().
129 template <typename L>
130 int AddLiterals(const std::vector<L>& wrapped_values);
131
132 // We lied when we said this is a pure read-only class :)
133 // It is possible to shrink inner vectors with not much cost.
134 //
135 // Removes the element at index from this[key] by swapping it with
136 // this[key].back() and then decreasing this key size. It is an error to
137 // call this on an empty inner vector.
138 void RemoveBySwap(K key, int index) {
139 DCHECK_GE(index, 0);
140 DCHECK_LT(index, sizes_[key]);
141 const int start = starts_[key];
142 std::swap(buffer_[start + index], buffer_[start + sizes_[key] - 1]);
143 sizes_[key]--;
144 }
145
146 // Replace the values at the given key.
147 // This will crash if there are more values than before.
148 void ReplaceValuesBySmallerSet(K key, absl::Span<const V> values);
149
150 // Interface so this can be used as an output of
151 // FindStronglyConnectedComponents().
152 void emplace_back(V const* begin, V const* end) {
153 Add(absl::MakeSpan(begin, end - begin));
154 }
155
156 private:
157 // Convert int and StrongInt to normal int.
158 static int InternalKey(K key);
159
160 std::vector<int> starts_;
161 std::vector<int> sizes_;
162 std::vector<V> buffer_;
163};
164
165// We often have a vector with fixed capacity reserved outside the hot loops.
166// Using this class instead save the capacity but most importantly link a lot
167// less code for the push_back() calls which allow more inlining.
168//
169// TODO(user): Add more functions and unit-test.
170template <typename T>
172 public:
173 void ClearAndReserve(size_t size) {
174 size_ = 0;
175 data_.reset(new T[size]);
176 }
177
178 T* data() const { return data_.get(); }
179 T* begin() const { return data_.get(); }
180 T* end() const { return data_.get() + size_; }
181 size_t size() const { return size_; }
182 bool empty() const { return size_ == 0; }
183
184 T operator[](int i) const { return data_[i]; }
185 T& operator[](int i) { return data_[i]; }
186
187 T back() const { return data_[size_ - 1]; }
188 T& back() { return data_[size_ - 1]; }
189
190 void clear() { size_ = 0; }
191 void resize(size_t size) { size_ = size; }
192 void pop_back() { --size_; }
193 void push_back(T t) { data_[size_++] = t; }
194
195 private:
196 int size_ = 0;
197 std::unique_ptr<T[]> data_ = nullptr;
198};
199
200// Prints a positive number with separators for easier reading (ex: 1'348'065).
201std::string FormatCounter(int64_t num);
202
203// This is used to format our table first row entry.
204inline std::string FormatName(absl::string_view name) {
205 return absl::StrCat("'", name, "':");
206}
207
208// Display tabular data by auto-computing cell width. Note that we right align
209// everything but the first row/col that is assumed to be the table name and is
210// left aligned.
211std::string FormatTable(std::vector<std::vector<std::string>>& table,
212 int spacing = 2);
213
214// Returns a in [0, m) such that a * x = 1 modulo m.
215// If gcd(x, m) != 1, there is no inverse, and it returns 0.
216//
217// This DCHECK that x is in [0, m).
218// This is integer overflow safe.
219//
220// Note(user): I didn't find this in a easily usable standard library.
221int64_t ModularInverse(int64_t x, int64_t m);
222
223// Just returns x % m but with a result always in [0, m).
224int64_t PositiveMod(int64_t x, int64_t m);
225
226// If we know that X * coeff % mod = rhs % mod, this returns c such that
227// PositiveMod(X, mod) = c.
228//
229// This requires coeff != 0, mod !=0 and gcd(coeff, mod) == 1.
230// The result will be in [0, mod) but there is no other condition on the sign or
231// magnitude of a and b.
232//
233// This is overflow safe, and when rhs == 0 or abs(mod) == 1, it returns 0.
234int64_t ProductWithModularInverse(int64_t coeff, int64_t mod, int64_t rhs);
235
236// Returns true if the equation a * X + b * Y = cte has some integer solutions.
237// For now, we check that a and b are different from 0 and from int64_t min.
238//
239// There is actually always a solution if cte % gcd(|a|, |b|) == 0. And because
240// a, b and cte fit on an int64_t, if there is a solution, there is one with X
241// and Y fitting on an int64_t.
242//
243// We will divide everything by gcd(a, b) first, so it is why we take reference
244// and the equation can change.
245//
246// If there are solutions, we return one of them (x0, y0).
247// From any such solution, the set of all solutions is given for Z integer by:
248// X = x0 + b * Z;
249// Y = y0 - a * Z;
250//
251// Given a domain for X and Y, it is possible to compute the "exact" domain of Z
252// with our Domain functions. Note however that this will only compute solution
253// where both x-x0 and y-y0 do fit on an int64_t:
254// DomainOf(x).SubtractionWith(x0).InverseMultiplicationBy(b).IntersectionWith(
255// DomainOf(y).SubtractionWith(y0).InverseMultiplicationBy(-a))
256bool SolveDiophantineEquationOfSizeTwo(int64_t& a, int64_t& b, int64_t& cte,
257 int64_t& x0, int64_t& y0);
258
259// Returns true if the equation a * X + b * Y = cte has some integer solutions
260// in the domain of X and Y.
262 const Domain& y, int64_t b,
263 int64_t cte);
264
265// The argument must be non-negative.
266int64_t FloorSquareRoot(int64_t a);
267int64_t CeilSquareRoot(int64_t a);
268
269// Converts a double to int64_t and cap large magnitudes at kint64min/max.
270// We also arbitrarily returns 0 for NaNs.
271//
272// Note(user): This is similar to SaturatingFloatToInt(), but we use our own
273// since we need to open source it and the code is simple enough.
274int64_t SafeDoubleToInt64(double value);
275
276// Returns the multiple of base closest to value. If there is a tie, we return
277// the one closest to zero. This way we have ClosestMultiple(x) =
278// -ClosestMultiple(-x) which is important for how this is used.
279int64_t ClosestMultiple(int64_t value, int64_t base);
280
281// Assuming n "literal" in [0, n), and a graph such that graph[i] list the
282// literal in [0, n) implied to false when the literal with index i is true,
283// this returns an heuristic decomposition of the literals into disjoint at most
284// ones.
285//
286// Note(user): Symmetrize the matrix if not already, maybe rephrase in term
287// of undirected graph, and clique decomposition.
288std::vector<absl::Span<int>> AtMostOneDecomposition(
289 const std::vector<std::vector<int>>& graph, absl::BitGenRef random,
290 std::vector<int>* buffer);
291
292// Given a linear equation "sum coeff_i * X_i <= rhs. We can rewrite it using
293// ClosestMultiple() as "base * new_terms + error <= rhs" where error can be
294// bounded using the provided bounds on each variables. This will return true if
295// the error can be ignored and this equation is completely equivalent to
296// new_terms <= new_rhs.
297//
298// This is useful for cases like 9'999 X + 10'0001 Y <= 155'000 where we have
299// weird coefficient (maybe due to scaling). With a base of 10K, this is
300// equivalent to X + Y <= 15.
301//
302// Preconditions: All coeffs are assumed to be positive. You can easily negate
303// all the negative coeffs and corresponding bounds before calling this.
305 int64_t base, absl::Span<const int64_t> coeffs,
306 absl::Span<const int64_t> lbs, absl::Span<const int64_t> ubs, int64_t rhs,
307 int64_t* new_rhs);
308
309// The model "singleton" random engine used in the solver.
310//
311// In test, we usually set use_absl_random() so that the sequence is changed at
312// each invocation. This way, clients do not relly on the wrong assumption that
313// a particular optimal solution will be returned if they are many equivalent
314// ones.
315class ModelRandomGenerator : public absl::BitGenRef {
316 public:
317 // We seed the strategy at creation only. This should be enough for our use
318 // case since the SatParameters is set first before the solver is created. We
319 // also never really need to change the seed afterwards, it is just used to
320 // diversify solves with identical parameters on different Model objects.
321 explicit ModelRandomGenerator(const SatParameters& params)
322 : absl::BitGenRef(deterministic_random_) {
323 deterministic_random_.seed(params.random_seed());
324 if (params.use_absl_random()) {
325 absl_random_ = absl::BitGen(absl::SeedSeq({params.random_seed()}));
326 absl::BitGenRef::operator=(absl::BitGenRef(absl_random_));
327 }
328 }
330 : ModelRandomGenerator(*model->GetOrCreate<SatParameters>()) {}
331
332 // This is just used to display ABSL_RANDOM_SALT_OVERRIDE in the log so that
333 // it is possible to reproduce a failure more easily while looking at a solver
334 // log.
335 //
336 // TODO(user): I didn't find a cleaner way to log this.
337 void LogSalt() const {}
338
339 private:
340 random_engine_t deterministic_random_;
341 absl::BitGen absl_random_;
342};
343
344// The model "singleton" shared time limit.
346 public:
348 : SharedTimeLimit(model->GetOrCreate<TimeLimit>()) {}
349};
350
351// Randomizes the decision heuristic of the given SatParameters.
352void RandomizeDecisionHeuristic(absl::BitGenRef random,
353 SatParameters* parameters);
354
355// This is equivalent of
356// absl::discrete_distribution<std::size_t>(input.begin(), input.end())(random)
357// but does no allocations. It is a lot faster when you need to pick just one
358// elements from a distribution for instance.
359int WeightedPick(absl::Span<const double> input, absl::BitGenRef random);
360
361// Context: this function is not really generic, but required to be unit-tested.
362// It is used in a clause minimization algorithm when we try to detect if any of
363// the clause literals can be propagated by a subset of the other literal being
364// false. For that, we want to enqueue in the solver all the subset of size n-1.
365//
366// This moves one of the unprocessed literal from literals to the last position.
367// The function tries to do that while preserving the longest possible prefix of
368// literals "amortized" through the calls assuming that we want to move each
369// literal to the last position once.
370//
371// For a vector of size n, if we want to call this n times so that each literal
372// is last at least once, the sum of the size of the changed suffixes will be
373// O(n log n). If we were to use a simpler algorithm (like moving the last
374// unprocessed literal to the last position), this sum would be O(n^2).
375//
376// Returns the size of the common prefix of literals before and after the move,
377// or -1 if all the literals are already processed. The argument
378// relevant_prefix_size is used as a hint when keeping more that this prefix
379// size do not matter. The returned value will always be lower or equal to
380// relevant_prefix_size.
381int MoveOneUnprocessedLiteralLast(
382 const absl::btree_set<LiteralIndex>& processed, int relevant_prefix_size,
383 std::vector<Literal>* literals);
384
385// Simple DP to compute the maximum reachable value of a "subset sum" under
386// a given bound (inclusive). Note that we abort as soon as the computation
387// become too important.
388//
389// Precondition: Both bound and all added values must be >= 0.
391 public:
392 MaxBoundedSubsetSum() : max_complexity_per_add_(/*default=*/50) { Reset(0); }
393 explicit MaxBoundedSubsetSum(int64_t bound, int max_complexity_per_add = 50)
394 : max_complexity_per_add_(max_complexity_per_add) {
395 Reset(bound);
396 }
397
398 // Resets to an empty set of values.
399 // We look for the maximum sum <= bound.
400 void Reset(int64_t bound);
401
402 // Returns the updated max if value was added to the subset-sum.
403 int64_t MaxIfAdded(int64_t candidate) const;
404
405 // Add a value to the base set for which subset sums will be taken.
406 void Add(int64_t value);
407
408 // Add a choice of values to the base set for which subset sums will be taken.
409 // Note that even if this doesn't include zero, not taking any choices will
410 // also be an option.
411 void AddChoices(absl::Span<const int64_t> choices);
412
413 // Adds [0, coeff, 2 * coeff, ... max_value * coeff].
414 void AddMultiples(int64_t coeff, int64_t max_value);
415
416 // Returns an upper bound (inclusive) on the maximum sum <= bound_.
417 // This might return bound_ if we aborted the computation.
418 int64_t CurrentMax() const { return current_max_; }
419
420 int64_t Bound() const { return bound_; }
421
422 private:
423 // This assumes filtered values.
424 void AddChoicesInternal(absl::Span<const int64_t> values);
425
426 // Max_complexity we are willing to pay on each Add() call.
427 const int max_complexity_per_add_;
428 int64_t gcd_;
429 int64_t bound_;
430 int64_t current_max_;
431 std::vector<int64_t> sums_;
432 std::vector<bool> expanded_sums_;
433 std::vector<int64_t> filtered_values_;
434};
435
436// Simple DP to keep the set of the first n reachable value (n > 1).
437//
438// TODO(user): Maybe modulo some prime number we can keep more info.
439// TODO(user): Another common case is a bunch of really small values and larger
440// ones, so we could bound the sum of the small values and keep the first few
441// reachable by the big ones. This is similar to some presolve transformations.
442template <int n>
444 public:
446 : reachable_(new int64_t[n]), new_reachable_(new int64_t[n]) {
447 Reset();
448 }
449
450 void Reset() {
451 for (int i = 0; i < n; ++i) {
452 reachable_[i] = std::numeric_limits<int64_t>::max();
453 }
454 reachable_[0] = 0;
455 new_reachable_[0] = 0;
456 }
457
458 // We assume the given positive value can be added as many time as wanted.
459 //
460 // TODO(user): Implement Add() with an upper bound on the multiplicity.
461 void Add(const int64_t positive_value) {
462 DCHECK_GT(positive_value, 0);
463 const int64_t* reachable = reachable_.get();
464 if (positive_value >= reachable[n - 1]) return;
465
466 // We copy from reachable_[i] to new_reachable_[j].
467 // The position zero is already copied.
468 int i = 1;
469 int j = 1;
470 int64_t* new_reachable = new_reachable_.get();
471 for (int base = 0; j < n && base < n; ++base) {
472 const int64_t candidate = CapAdd(new_reachable[base], positive_value);
473 while (j < n && i < n && reachable[i] < candidate) {
474 new_reachable[j++] = reachable[i++];
475 }
476 if (j < n) {
477 // Eliminate duplicates.
478 while (i < n && reachable[i] == candidate) i++;
479
480 // insert candidate in its final place.
481 new_reachable[j++] = candidate;
482 }
483 }
484 std::swap(reachable_, new_reachable_);
485 }
486
487 // Returns true iff sum might be expressible as a weighted sum of the added
488 // value. Any sum >= LastValue() is always considered potentially reachable.
489 bool MightBeReachable(int64_t sum) const {
490 if (sum >= reachable_[n - 1]) return true;
491 return std::binary_search(&reachable_[0], &reachable_[0] + n, sum);
492 }
493
494 int64_t LastValue() const { return reachable_[n - 1]; }
495
496 absl::Span<const int64_t> reachable() {
497 return absl::MakeSpan(reachable_.get(), n);
498 }
499
500 private:
501 std::unique_ptr<int64_t[]> reachable_;
502 std::unique_ptr<int64_t[]> new_reachable_;
503};
504
505// Yet another variant of FirstFewValues or MaxBoundedSubsetSum.
507 public:
508 // Computes all the possible subset sums in [0, maximum_sum].
509 // Returns them sorted. All elements must be non-negative.
510 //
511 // If abort_if_maximum_reached is true, we might not return all possible
512 // subset sums as we stop the exploration as soon as a subset sum is equal to
513 // maximum_sum. When this happen, we guarantee that the last element returned
514 // will be maximum_sum though.
515 //
516 // Worst case complexity is in O(2^num_elements) if maximum_sum is large or
517 // O(maximum_sum * num_elements) if that is lower.
518 //
519 // TODO(user): We could optimize even further the case of a small maximum_sum.
520 absl::Span<const int64_t> Compute(absl::Span<const int64_t> elements,
521 int64_t maximum_sum,
522 bool abort_if_maximum_reached = false);
523
524 // Returns the possible subset sums sorted.
525 absl::Span<const int64_t> SortedSums() const { return sums_; }
526
527 private:
528 std::vector<int64_t> sums_;
529 std::vector<int64_t> new_sums_;
530};
531
532// Similar to MaxBoundedSubsetSum() above but use a different algo.
534 public:
535 // If we pack the given elements into a bin of size 'bin_size', returns
536 // largest possible sum that can be reached.
537 //
538 // This implementation allow to solve this in O(2^(num_elements/2)) allowing
539 // to go easily to 30 or 40 elements. If bin_size is small, complexity is more
540 // like O(num_element * bin_size).
541 int64_t MaxSubsetSum(absl::Span<const int64_t> elements, int64_t bin_size);
542
543 // Returns an estimate of how many elementary operations
544 // MaxSubsetSum() is going to take.
545 double ComplexityEstimate(int num_elements, int64_t bin_size);
546
547 private:
548 // We use a class just to reuse the memory and not allocate it on each query.
549 SortedSubsetSums sums_a_;
550 SortedSubsetSums sums_b_;
551};
552
553// Use Dynamic programming to solve a single knapsack. This is used by the
554// presolver to simplify variables appearing in a single linear constraint.
555//
556// Complexity is the best of
557// - O(num_variables * num_relevant_values ^ 2) or
558// - O(num_variables * num_relevant_values * max_domain_size).
560 public:
561 // Solves the problem:
562 // - minimize sum costs * X[i]
563 // - subject to sum coeffs[i] * X[i] \in rhs, with X[i] \in Domain(i).
564 //
565 // Returns:
566 // - (solved = false) if complexity is too high.
567 // - (solved = true, infeasible = true) if proven infeasible.
568 // - (solved = true, infeasible = false, solution) otherwise.
569 struct Result {
570 bool solved = false;
571 bool infeasible = false;
572 std::vector<int64_t> solution;
573 };
574 Result Solve(absl::Span<const Domain> domains,
575 absl::Span<const int64_t> coeffs,
576 absl::Span<const int64_t> costs, const Domain& rhs);
577
578 private:
579 Result InternalSolve(int64_t num_values, const Domain& rhs);
580
581 // Canonicalized version.
582 std::vector<Domain> domains_;
583 std::vector<int64_t> coeffs_;
584 std::vector<int64_t> costs_;
585
586 // We only need to keep one state with the same activity.
587 struct State {
588 int64_t cost = std::numeric_limits<int64_t>::max();
589 int64_t value = 0;
590 };
591 std::vector<std::vector<State>> var_activity_states_;
592};
593
594// Manages incremental averages.
596 public:
597 // Initializes the average with 'initial_average' and number of records to 0.
598 explicit IncrementalAverage(double initial_average)
599 : average_(initial_average) {}
601
602 // Sets the number of records to 0 and average to 'reset_value'.
603 void Reset(double reset_value);
604
605 double CurrentAverage() const { return average_; }
606 int64_t NumRecords() const { return num_records_; }
607
608 void AddData(double new_record);
609
610 private:
611 double average_ = 0.0;
612 int64_t num_records_ = 0;
613};
614
615// Manages exponential moving averages defined as
616// new_average = decaying_factor * old_average
617// + (1 - decaying_factor) * new_record.
618// where 0 < decaying_factor < 1.
620 public:
621 explicit ExponentialMovingAverage(double decaying_factor)
622 : decaying_factor_(decaying_factor) {
623 DCHECK_GE(decaying_factor, 0.0);
624 DCHECK_LE(decaying_factor, 1.0);
625 }
626
627 // Returns exponential moving average for all the added data so far.
628 double CurrentAverage() const { return average_; }
629
630 // Returns the total number of added records so far.
631 int64_t NumRecords() const { return num_records_; }
632
633 void AddData(double new_record);
634
635 private:
636 double average_ = 0.0;
637 int64_t num_records_ = 0;
638 const double decaying_factor_;
639};
640
641// Utility to calculate percentile (First variant) for limited number of
642// records. Reference: https://en.wikipedia.org/wiki/Percentile
643//
644// After the vector is sorted, we assume that the element with index i
645// correspond to the percentile 100*(i+0.5)/size. For percentiles before the
646// first element (resp. after the last one) we return the first element (resp.
647// the last). And otherwise we do a linear interpolation between the two element
648// around the asked percentile.
650 public:
651 explicit Percentile(int record_limit) : record_limit_(record_limit) {}
652
653 void AddRecord(double record);
654
655 // Returns number of stored records.
656 int64_t NumRecords() const { return records_.size(); }
657
658 // Note that this runs in O(n) for n records.
659 double GetPercentile(double percent);
660
661 private:
662 std::deque<double> records_;
663 const int record_limit_;
664};
665
666// Keep the top n elements from a stream of elements.
667//
668// TODO(user): We could use gtl::TopN when/if it gets open sourced. Note that
669// we might be slighlty faster here since we use an indirection and don't move
670// the Element class around as much.
671template <typename Element, typename Score>
672class TopN {
673 public:
674 explicit TopN(int n) : n_(n) {}
675
676 void Clear() {
677 heap_.clear();
678 elements_.clear();
679 }
680
681 void Add(Element e, Score score) {
682 if (heap_.size() < n_) {
683 const int index = elements_.size();
684 heap_.push_back({index, score});
685 elements_.push_back(std::move(e));
686 if (heap_.size() == n_) {
687 // TODO(user): We could delay that on the n + 1 push.
688 std::make_heap(heap_.begin(), heap_.end());
689 }
690 } else {
691 if (score <= heap_.front().score) return;
692 const int index_to_replace = heap_.front().index;
693 elements_[index_to_replace] = std::move(e);
694
695 // If needed, we could be faster here with an update operation.
696 std::pop_heap(heap_.begin(), heap_.end());
697 heap_.back() = {index_to_replace, score};
698 std::push_heap(heap_.begin(), heap_.end());
699 }
700 }
701
702 bool empty() const { return elements_.empty(); }
703
704 const std::vector<Element>& UnorderedElements() const { return elements_; }
705 std::vector<Element>* MutableUnorderedElements() { return &elements_; }
706
707 private:
708 const int n_;
709
710 // We keep a heap of the n highest score.
711 struct HeapElement {
712 int index; // in elements_;
713 Score score;
714 bool operator<(const HeapElement& other) const {
715 return score > other.score;
716 }
717 };
718 std::vector<HeapElement> heap_;
719 std::vector<Element> elements_;
720};
721
722// ============================================================================
723// Implementation.
724// ============================================================================
725
726inline int64_t SafeDoubleToInt64(double value) {
727 if (std::isnan(value)) return 0;
728 if (value >= static_cast<double>(std::numeric_limits<int64_t>::max())) {
729 return std::numeric_limits<int64_t>::max();
730 }
731 if (value <= static_cast<double>(std::numeric_limits<int64_t>::min())) {
732 return std::numeric_limits<int64_t>::min();
733 }
734 return static_cast<int64_t>(value);
735}
736
737// Tells whether a int128 can be casted to a int64_t that can be negated.
738inline bool IsNegatableInt64(absl::int128 x) {
739 return x <= absl::int128(std::numeric_limits<int64_t>::max()) &&
740 x > absl::int128(std::numeric_limits<int64_t>::min());
741}
742
743template <typename K, typename V>
744inline int CompactVectorVector<K, V>::Add(absl::Span<const V> values) {
745 const int index = size();
746 starts_.push_back(buffer_.size());
747 sizes_.push_back(values.size());
748 buffer_.insert(buffer_.end(), values.begin(), values.end());
749 return index;
750}
751
752template <typename K, typename V>
753inline void CompactVectorVector<K, V>::AppendToLastVector(const V& value) {
754 sizes_.back()++;
755 buffer_.push_back(value);
756}
757
758template <typename K, typename V>
760 K key, absl::Span<const V> values) {
761 CHECK_LE(values.size(), sizes_[key]);
762 sizes_[key] = values.size();
763 if (values.empty()) return;
764 memcpy(&buffer_[starts_[key]], values.data(), sizeof(V) * values.size());
765}
766
767template <typename K, typename V>
768template <typename L>
770 const std::vector<L>& wrapped_values) {
771 const int index = size();
772 starts_.push_back(buffer_.size());
773 sizes_.push_back(wrapped_values.size());
774 for (const L wrapped_value : wrapped_values) {
775 buffer_.push_back(wrapped_value.Index().value());
776 }
777 return index;
778}
779
780// We need to support both StrongType and normal int.
781template <typename K, typename V>
782inline int CompactVectorVector<K, V>::InternalKey(K key) {
783 if constexpr (std::is_same_v<K, int>) {
784 return key;
785 } else {
786 return key.value();
787 }
788}
789
790template <typename K, typename V>
791inline absl::Span<const V> CompactVectorVector<K, V>::operator[](K key) const {
792 DCHECK_GE(key, 0);
793 DCHECK_LT(key, starts_.size());
794 DCHECK_LT(key, sizes_.size());
795 const int k = InternalKey(key);
796 const size_t size = static_cast<size_t>(sizes_.data()[k]);
797 if (size == 0) return {};
798 return {&buffer_.data()[starts_.data()[k]], size};
799}
800
801template <typename K, typename V>
802inline absl::Span<V> CompactVectorVector<K, V>::operator[](K key) {
803 DCHECK_GE(key, 0);
804 DCHECK_LT(key, starts_.size());
805 DCHECK_LT(key, sizes_.size());
806 const int k = InternalKey(key);
807 const size_t size = static_cast<size_t>(sizes_.data()[k]);
808 if (size == 0) return {};
809 return absl::MakeSpan(&buffer_.data()[starts_.data()[k]], size);
810}
811
812template <typename K, typename V>
813inline std::vector<absl::Span<const V>>
814CompactVectorVector<K, V>::AsVectorOfSpan() const {
815 std::vector<absl::Span<const V>> result(starts_.size());
816 for (int k = 0; k < starts_.size(); ++k) {
817 result[k] = (*this)[k];
818 }
819 return result;
820}
821
822template <typename K, typename V>
823inline void CompactVectorVector<K, V>::clear() {
824 starts_.clear();
825 sizes_.clear();
826 buffer_.clear();
827}
828
829template <typename K, typename V>
830inline size_t CompactVectorVector<K, V>::size() const {
831 return starts_.size();
833
834template <typename K, typename V>
835inline bool CompactVectorVector<K, V>::empty() const {
836 return starts_.empty();
838
839template <typename K, typename V>
840template <typename Keys, typename Values>
842 Values values) {
843 if (keys.empty()) return clear();
844
845 // Compute maximum index.
846 int max_key = 0;
847 for (const K key : keys) {
848 max_key = std::max(max_key, InternalKey(key) + 1);
849 }
850
851 // Compute sizes_;
852 sizes_.assign(max_key, 0);
853 for (const K key : keys) {
854 sizes_[InternalKey(key)]++;
855 }
856
857 // Compute starts_;
858 starts_.assign(max_key, 0);
859 for (int k = 1; k < max_key; ++k) {
860 starts_[k] = starts_[k - 1] + sizes_[k - 1];
861 }
862
863 // Copy data and uses starts as temporary indices.
864 buffer_.resize(keys.size());
865 for (int i = 0; i < keys.size(); ++i) {
866 buffer_[starts_[InternalKey(keys[i])]++] = values[i];
867 }
868
869 // Restore starts_.
870 for (int k = max_key - 1; k > 0; --k) {
871 starts_[k] = starts_[k - 1];
872 }
873 starts_[0] = 0;
874}
875
876// Similar to ResetFromFlatMapping().
877template <typename K, typename V>
878template <typename Collection>
879inline void CompactVectorVector<K, V>::ResetFromPairs(const Collection& pairs,
880 int minimum_num_nodes) {
881 // Compute maximum index.
882 int max_key = minimum_num_nodes;
883 for (const auto& [key, _] : pairs) {
884 max_key = std::max(max_key, InternalKey(key) + 1);
885 }
886
887 if (pairs.empty()) {
888 clear();
889 sizes_.assign(minimum_num_nodes, 0);
890 starts_.assign(minimum_num_nodes, 0);
891 return;
892 }
893
894 // Compute sizes_;
895 sizes_.assign(max_key, 0);
896 for (const auto& [key, _] : pairs) {
897 sizes_[InternalKey(key)]++;
898 }
899
900 // Compute starts_;
901 starts_.assign(max_key, 0);
902 for (int k = 1; k < max_key; ++k) {
903 starts_[k] = starts_[k - 1] + sizes_[k - 1];
904 }
905
906 // Copy data and uses starts as temporary indices.
907 buffer_.resize(pairs.size());
908 for (int i = 0; i < pairs.size(); ++i) {
909 const auto& [key, value] = pairs[i];
910 buffer_[starts_[InternalKey(key)]++] = value;
911 }
912
913 // Restore starts_.
914 for (int k = max_key - 1; k > 0; --k) {
915 starts_[k] = starts_[k - 1];
916 }
917 starts_[0] = 0;
918}
919
920// Similar to ResetFromFlatMapping().
921template <typename K, typename V>
922inline void CompactVectorVector<K, V>::ResetFromTranspose(
923 const CompactVectorVector<V, K>& other, int min_transpose_size) {
924 if (other.empty()) {
925 clear();
926 if (min_transpose_size > 0) {
927 starts_.assign(min_transpose_size, 0);
928 sizes_.assign(min_transpose_size, 0);
929 }
930 return;
931 }
932
933 // Compute maximum index.
934 int max_key = min_transpose_size;
935 for (V v = 0; v < other.size(); ++v) {
936 for (const K k : other[v]) {
937 max_key = std::max(max_key, InternalKey(k) + 1);
938 }
939 }
940
941 // Compute sizes_;
942 sizes_.assign(max_key, 0);
943 for (V v = 0; v < other.size(); ++v) {
944 for (const K k : other[v]) {
945 sizes_[InternalKey(k)]++;
946 }
947 }
948
949 // Compute starts_;
950 starts_.assign(max_key, 0);
951 for (int k = 1; k < max_key; ++k) {
952 starts_[k] = starts_[k - 1] + sizes_[k - 1];
953 }
954
955 // Copy data and uses starts as temporary indices.
956 buffer_.resize(other.buffer_.size());
957 for (V v = 0; v < other.size(); ++v) {
958 for (const K k : other[v]) {
959 buffer_[starts_[InternalKey(k)]++] = v;
960 }
961 }
962
963 // Restore starts_.
964 for (int k = max_key - 1; k > 0; --k) {
965 starts_[k] = starts_[k - 1];
966 }
967 starts_[0] = 0;
968}
969
970} // namespace sat
971} // namespace operations_research
972
973#endif // OR_TOOLS_SAT_UTIL_H_
SharedTimeLimit(TimeLimit *time_limit)
Definition time_limit.h:318
Result Solve(absl::Span< const Domain > domains, absl::Span< const int64_t > coeffs, absl::Span< const int64_t > costs, const Domain &rhs)
Definition util.cc:648
void ResetFromFlatMapping(Keys keys, Values values)
Definition util.h:843
void ResetFromTranspose(const CompactVectorVector< V, K > &other, int min_transpose_size=0)
Similar to ResetFromFlatMapping().
Definition util.h:924
void ResetFromPairs(const Collection &pairs, int minimum_num_nodes=0)
Similar to ResetFromFlatMapping().
Definition util.h:881
void reserve(int size, int num_entries)
Definition util.h:91
void clear()
Restore to empty vector<vector<>>.
Definition util.h:825
void emplace_back(V const *begin, V const *end)
Definition util.h:152
absl::Span< const V > operator[](K key) const
Definition util.h:793
void ReplaceValuesBySmallerSet(K key, absl::Span< const V > values)
Definition util.h:761
std::vector< absl::Span< const V > > AsVectorOfSpan() const
Definition util.h:816
void RemoveBySwap(K key, int index)
Definition util.h:138
int AddLiterals(const std::vector< L > &wrapped_values)
Definition util.h:771
size_t size() const
Size of the "key" space, always in [0, size()).
Definition util.h:832
void reserve(int size)
Reserve memory if it is already known or tightly estimated.
Definition util.h:87
void AppendToLastVector(const V &value)
Definition util.h:755
int Add(absl::Span< const V > values)
Definition util.h:746
double CurrentAverage() const
Returns exponential moving average for all the added data so far.
Definition util.h:628
int64_t NumRecords() const
Returns the total number of added records so far.
Definition util.h:631
ExponentialMovingAverage(double decaying_factor)
Definition util.h:621
absl::Span< const int64_t > reachable()
Definition util.h:496
bool MightBeReachable(int64_t sum) const
Definition util.h:489
void Add(const int64_t positive_value)
Definition util.h:461
void Reset(double reset_value)
Sets the number of records to 0 and average to 'reset_value'.
Definition util.cc:445
IncrementalAverage(double initial_average)
Initializes the average with 'initial_average' and number of records to 0.
Definition util.h:598
Similar to MaxBoundedSubsetSum() above but use a different algo.
Definition util.h:533
double ComplexityEstimate(int num_elements, int64_t bin_size)
Definition util.cc:968
int64_t MaxSubsetSum(absl::Span< const int64_t > elements, int64_t bin_size)
Definition util.cc:978
MaxBoundedSubsetSum(int64_t bound, int max_complexity_per_add=50)
Definition util.h:393
ModelRandomGenerator(const SatParameters &params)
Definition util.h:321
int64_t NumRecords() const
Returns number of stored records.
Definition util.h:656
Percentile(int record_limit)
Definition util.h:651
Yet another variant of FirstFewValues or MaxBoundedSubsetSum.
Definition util.h:506
absl::Span< const int64_t > Compute(absl::Span< const int64_t > elements, int64_t maximum_sum, bool abort_if_maximum_reached=false)
Definition util.cc:906
absl::Span< const int64_t > SortedSums() const
Returns the possible subset sums sorted.
Definition util.h:525
void Add(Element e, Score score)
Definition util.h:681
std::vector< Element > * MutableUnorderedElements()
Definition util.h:705
const std::vector< Element > & UnorderedElements() const
Definition util.h:704
int64_t ProductWithModularInverse(int64_t coeff, int64_t mod, int64_t rhs)
Definition util.cc:182
bool SolveDiophantineEquationOfSizeTwo(int64_t &a, int64_t &b, int64_t &cte, int64_t &x0, int64_t &y0)
Definition util.cc:204
int64_t FloorSquareRoot(int64_t a)
The argument must be non-negative.
Definition util.cc:300
int64_t CeilSquareRoot(int64_t a)
Definition util.cc:309
int64_t ModularInverse(int64_t x, int64_t m)
Definition util.cc:144
bool IsNegatableInt64(absl::int128 x)
Tells whether a int128 can be casted to a int64_t that can be negated.
Definition util.h:740
int64_t SafeDoubleToInt64(double value)
Definition util.h:728
std::string FormatCounter(int64_t num)
Prints a positive number with separators for easier reading (ex: 1'348'065).
Definition util.cc:44
bool DiophantineEquationOfSizeTwoHasSolutionInDomain(const Domain &x, int64_t a, const Domain &y, int64_t b, int64_t cte)
Definition util.cc:248
int64_t ClosestMultiple(int64_t value, int64_t base)
Definition util.cc:317
int64_t PositiveMod(int64_t x, int64_t m)
Just returns x % m but with a result always in [0, m).
Definition util.cc:177
bool LinearInequalityCanBeReducedWithClosestMultiple(int64_t base, absl::Span< const int64_t > coeffs, absl::Span< const int64_t > lbs, absl::Span< const int64_t > ubs, int64_t rhs, int64_t *new_rhs)
Definition util.cc:324
std::vector< absl::Span< int > > AtMostOneDecomposition(const std::vector< std::vector< int > > &graph, absl::BitGenRef random, std::vector< int > *buffer)
Definition util.cc:894
std::string FormatName(absl::string_view name)
This is used to format our table first row entry.
Definition util.h:204
std::string FormatTable(std::vector< std::vector< std::string > > &table, int spacing)
Definition util.cc:72
In SWIG mode, we don't want anything besides these top-level includes.
int64_t CapAdd(int64_t x, int64_t y)
std::mt19937_64 random_engine_t
if(!yyg->yy_init)
Definition parser.yy.cc:965
static int input(yyscan_t yyscanner)