Google OR-Tools v9.14
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 <iterator>
23#include <limits>
24#include <memory>
25#include <string>
26#include <type_traits>
27#include <utility>
28#include <vector>
29
30#include "absl/base/attributes.h"
31#include "absl/container/btree_set.h"
32#include "absl/log/check.h"
33#include "absl/log/log_streamer.h"
34#include "absl/numeric/int128.h"
35#include "absl/random/bit_gen_ref.h"
36#include "absl/random/random.h"
37#include "absl/strings/str_cat.h"
38#include "absl/strings/string_view.h"
39#include "absl/types/span.h"
41#include "ortools/sat/model.h"
43#include "ortools/sat/sat_parameters.pb.h"
48
49namespace operations_research {
50namespace sat {
51
52// A simple class with always IdentityMap[t] == t.
53// This is to avoid allocating vector with std::iota() in some Apis.
54template <typename T>
56 public:
57 T operator[](T t) const { return t; }
58};
59
60// Small utility class to store a vector<vector<>> where one can only append new
61// vector and never change previously added ones. This allows to store a static
62// key -> value(s) mapping.
63//
64// This is a lot more compact memorywise and thus faster than vector<vector<>>.
65// Note that we implement a really small subset of the vector<vector<>> API.
66//
67// We support int and StrongType for key K and any copyable type for value V.
68template <typename K = int, typename V = int>
70 public:
71 using value_type = V;
72
73 // Size of the "key" space, always in [0, size()).
74 size_t size() const;
75 bool empty() const;
76 size_t num_entries() const { return buffer_.size(); }
77
78 // Getters, either via [] or via a wrapping to be compatible with older api.
79 //
80 // Warning: Spans are only valid until the next modification!
81 absl::Span<V> operator[](K key);
82 absl::Span<const V> operator[](K key) const;
83 std::vector<absl::Span<const V>> AsVectorOfSpan() const;
84
85 // Restore to empty vector<vector<>>.
86 void clear();
87
88 // Reserve memory if it is already known or tightly estimated.
89 void reserve(int size) {
90 starts_.reserve(size);
91 sizes_.reserve(size);
92 }
93 void reserve(int size, int num_entries) {
95 buffer_.reserve(num_entries);
96 }
97
98 // Given a flat mapping (keys[i] -> values[i]) with two parallel vectors, not
99 // necessarily sorted by key, regroup the same key so that
100 // CompactVectorVector[key] list all values in the order in which they appear.
101 //
102 // We only check keys.size(), so this can be used with IdentityMap() as
103 // second argument.
104 template <typename Keys, typename Values>
105 void ResetFromFlatMapping(Keys keys, Values values,
106 int minimum_num_nodes = 0);
107
108 // Same as above but for any collections of std::pair<K, V>, or, more
109 // generally, any iterable collection of objects that have a `first` and a
110 // `second` members.
111 template <typename Collection>
112 void ResetFromPairs(const Collection& pairs, int minimum_num_nodes = 0);
113
114 // Initialize this vector from the transpose of another.
115 // IMPORTANT: This cannot be called with the vector itself.
116 //
117 // If min_transpose_size is given, then the transpose will have at least this
118 // size even if some of the last keys do not appear in other.
119 //
120 // If this is called twice in a row, then it has the side effect of sorting
121 // all inner vectors by values !
123 int min_transpose_size = 0);
124
125 // Append a new entry.
126 // Returns the previous size() as this is convenient for how we use it.
127 int Add(absl::Span<const V> values);
128 void AppendToLastVector(const V& value);
129
130 // Hacky: same as Add() but for sat::Literal or any type from which we can get
131 // a value type V via L.Index().value().
132 template <typename L>
133 int AddLiterals(const std::vector<L>& wrapped_values);
134
135 // We lied when we said this is a pure read-only class :)
136 // It is possible to shrink inner vectors with not much cost.
137 //
138 // Removes the element at index from this[key] by swapping it with
139 // this[key].back() and then decreasing this key size. It is an error to
140 // call this on an empty inner vector.
141 void RemoveBySwap(K key, int index) {
142 DCHECK_GE(index, 0);
143 DCHECK_LT(index, sizes_[key]);
144 const int start = starts_[key];
145 std::swap(buffer_[start + index], buffer_[start + sizes_[key] - 1]);
146 sizes_[key]--;
147 }
148
149 // Replace the values at the given key.
150 // This will crash if there are more values than before.
151 void ReplaceValuesBySmallerSet(K key, absl::Span<const V> values);
152
153 // Interface so this can be used as an output of
154 // FindStronglyConnectedComponents().
155 void emplace_back(V const* begin, V const* end) {
156 Add(absl::MakeSpan(begin, end - begin));
157 }
158
159 private:
160 // Convert int and StrongInt to normal int.
161 static int InternalKey(K key);
162
163 std::vector<int> starts_;
164 std::vector<int> sizes_;
165 std::vector<V> buffer_;
166};
167
168// We often have a vector with fixed capacity reserved outside the hot loops.
169// Using this class instead save the capacity but most importantly link a lot
170// less code for the push_back() calls which allow more inlining.
171//
172// TODO(user): Add more functions and unit-test.
173template <typename T>
175 public:
176 void ClearAndReserve(size_t size) {
177 size_ = 0;
178 data_.reset(new T[size]);
179 }
180
181 T* data() const { return data_.get(); }
182 T* begin() const { return data_.get(); }
183 T* end() const { return data_.get() + size_; }
184 size_t size() const { return size_; }
185 bool empty() const { return size_ == 0; }
186
187 T operator[](int i) const { return data_[i]; }
188 T& operator[](int i) { return data_[i]; }
189
190 T back() const { return data_[size_ - 1]; }
191 T& back() { return data_[size_ - 1]; }
192
193 void clear() { size_ = 0; }
194 void resize(size_t size) { size_ = size; }
195 void pop_back() { --size_; }
196 void push_back(T t) { data_[size_++] = t; }
197
198 private:
199 int size_ = 0;
200 std::unique_ptr<T[]> data_ = nullptr;
201};
202
203// Prints a positive number with separators for easier reading (ex: 1'348'065).
204std::string FormatCounter(int64_t num);
205
206// This is used to format our table first row entry.
207inline std::string FormatName(absl::string_view name) {
208 return absl::StrCat("'", name, "':");
209}
210
211// Display tabular data by auto-computing cell width. Note that we right align
212// everything but the first row/col that is assumed to be the table name and is
213// left aligned.
214std::string FormatTable(std::vector<std::vector<std::string>>& table,
215 int spacing = 2);
216
217// Returns a in [0, m) such that a * x = 1 modulo m.
218// If gcd(x, m) != 1, there is no inverse, and it returns 0.
219//
220// This DCHECK that x is in [0, m).
221// This is integer overflow safe.
222//
223// Note(user): I didn't find this in a easily usable standard library.
224int64_t ModularInverse(int64_t x, int64_t m);
225
226// Just returns x % m but with a result always in [0, m).
227int64_t PositiveMod(int64_t x, int64_t m);
228
229// If we know that X * coeff % mod = rhs % mod, this returns c such that
230// PositiveMod(X, mod) = c.
231//
232// This requires coeff != 0, mod !=0 and gcd(coeff, mod) == 1.
233// The result will be in [0, mod) but there is no other condition on the sign or
234// magnitude of a and b.
235//
236// This is overflow safe, and when rhs == 0 or abs(mod) == 1, it returns 0.
237int64_t ProductWithModularInverse(int64_t coeff, int64_t mod, int64_t rhs);
238
239// Returns true if the equation a * X + b * Y = cte has some integer solutions.
240// For now, we check that a and b are different from 0 and from int64_t min.
241//
242// There is actually always a solution if cte % gcd(|a|, |b|) == 0. And because
243// a, b and cte fit on an int64_t, if there is a solution, there is one with X
244// and Y fitting on an int64_t.
245//
246// We will divide everything by gcd(a, b) first, so it is why we take reference
247// and the equation can change.
248//
249// If there are solutions, we return one of them (x0, y0).
250// From any such solution, the set of all solutions is given for Z integer by:
251// X = x0 + b * Z;
252// Y = y0 - a * Z;
253//
254// Given a domain for X and Y, it is possible to compute the "exact" domain of Z
255// with our Domain functions. Note however that this will only compute solution
256// where both x-x0 and y-y0 do fit on an int64_t:
257// DomainOf(x).SubtractionWith(x0).InverseMultiplicationBy(b).IntersectionWith(
258// DomainOf(y).SubtractionWith(y0).InverseMultiplicationBy(-a))
259bool SolveDiophantineEquationOfSizeTwo(int64_t& a, int64_t& b, int64_t& cte,
260 int64_t& x0, int64_t& y0);
261
262// Returns true if the equation a * X + b * Y = cte has some integer solutions
263// in the domain of X and Y.
265 const Domain& y, int64_t b,
266 int64_t cte);
267
268// The argument must be non-negative.
269int64_t FloorSquareRoot(int64_t a);
270int64_t CeilSquareRoot(int64_t a);
271
272// Converts a double to int64_t and cap large magnitudes at kint64min/max.
273// We also arbitrarily returns 0 for NaNs.
274//
275// Note(user): This is similar to SaturatingFloatToInt(), but we use our own
276// since we need to open source it and the code is simple enough.
277int64_t SafeDoubleToInt64(double value);
278
279// Returns the multiple of base closest to value. If there is a tie, we return
280// the one closest to zero. This way we have ClosestMultiple(x) =
281// -ClosestMultiple(-x) which is important for how this is used.
282int64_t ClosestMultiple(int64_t value, int64_t base);
283
284// Assuming n "literal" in [0, n), and a graph such that graph[i] list the
285// literal in [0, n) implied to false when the literal with index i is true,
286// this returns an heuristic decomposition of the literals into disjoint at most
287// ones.
288//
289// Note(user): Symmetrize the matrix if not already, maybe rephrase in term
290// of undirected graph, and clique decomposition.
291std::vector<absl::Span<int>> AtMostOneDecomposition(
292 const std::vector<std::vector<int>>& graph, absl::BitGenRef random,
293 std::vector<int>* buffer);
294
295// Given a linear equation "sum coeff_i * X_i <= rhs. We can rewrite it using
296// ClosestMultiple() as "base * new_terms + error <= rhs" where error can be
297// bounded using the provided bounds on each variables. This will return true if
298// the error can be ignored and this equation is completely equivalent to
299// new_terms <= new_rhs.
300//
301// This is useful for cases like 9'999 X + 10'0001 Y <= 155'000 where we have
302// weird coefficient (maybe due to scaling). With a base of 10K, this is
303// equivalent to X + Y <= 15.
304//
305// Preconditions: All coeffs are assumed to be positive. You can easily negate
306// all the negative coeffs and corresponding bounds before calling this.
308 int64_t base, absl::Span<const int64_t> coeffs,
309 absl::Span<const int64_t> lbs, absl::Span<const int64_t> ubs, int64_t rhs,
310 int64_t* new_rhs);
311
312// The model "singleton" random engine used in the solver.
313//
314// In test, we usually set use_absl_random() so that the sequence is changed at
315// each invocation. This way, clients do not really on the wrong assumption that
316// a particular optimal solution will be returned if they are many equivalent
317// ones.
318class ModelRandomGenerator : public absl::BitGenRef {
319 public:
320 // We seed the strategy at creation only. This should be enough for our use
321 // case since the SatParameters is set first before the solver is created. We
322 // also never really need to change the seed afterwards, it is just used to
323 // diversify solves with identical parameters on different Model objects.
324 explicit ModelRandomGenerator(const SatParameters& params)
325 : absl::BitGenRef(deterministic_random_) {
326 deterministic_random_.seed(params.random_seed());
327 if (params.use_absl_random()) {
328 absl_random_ = absl::BitGen(absl::SeedSeq({params.random_seed()}));
329 absl::BitGenRef::operator=(absl::BitGenRef(absl_random_));
330 }
331 }
332
333 explicit ModelRandomGenerator(const absl::BitGenRef& bit_gen_ref)
334 : absl::BitGenRef(deterministic_random_) {
335 absl::BitGenRef::operator=(bit_gen_ref);
336 }
337
339 : ModelRandomGenerator(*model->GetOrCreate<SatParameters>()) {}
340
341 // This is just used to display ABSL_RANDOM_SALT_OVERRIDE in the log so that
342 // it is possible to reproduce a failure more easily while looking at a solver
343 // log.
344 //
345 // TODO(user): I didn't find a cleaner way to log this.
346 void LogSalt() const {}
347
348 private:
349 random_engine_t deterministic_random_;
350 absl::BitGen absl_random_;
351};
352
353// The model "singleton" shared time limit.
355 public:
357 : SharedTimeLimit(model->GetOrCreate<TimeLimit>()) {}
358};
359
360// Randomizes the decision heuristic of the given SatParameters.
361void RandomizeDecisionHeuristic(absl::BitGenRef random,
362 SatParameters* parameters);
363
364// This is equivalent of
365// absl::discrete_distribution<std::size_t>(input.begin(), input.end())(random)
366// but does no allocations. It is a lot faster when you need to pick just one
367// elements from a distribution for instance.
368int WeightedPick(absl::Span<const double> input, absl::BitGenRef random);
369
370// Context: this function is not really generic, but required to be unit-tested.
371// It is used in a clause minimization algorithm when we try to detect if any of
372// the clause literals can be propagated by a subset of the other literal being
373// false. For that, we want to enqueue in the solver all the subset of size n-1.
374//
375// This moves one of the unprocessed literal from literals to the last position.
376// The function tries to do that while preserving the longest possible prefix of
377// literals "amortized" through the calls assuming that we want to move each
378// literal to the last position once.
379//
380// For a vector of size n, if we want to call this n times so that each literal
381// is last at least once, the sum of the size of the changed suffixes will be
382// O(n log n). If we were to use a simpler algorithm (like moving the last
383// unprocessed literal to the last position), this sum would be O(n^2).
384//
385// Returns the size of the common prefix of literals before and after the move,
386// or -1 if all the literals are already processed. The argument
387// relevant_prefix_size is used as a hint when keeping more that this prefix
388// size do not matter. The returned value will always be lower or equal to
389// relevant_prefix_size.
390int MoveOneUnprocessedLiteralLast(
391 const absl::btree_set<LiteralIndex>& processed, int relevant_prefix_size,
392 std::vector<Literal>* literals);
393
394// Simple DP to compute the maximum reachable value of a "subset sum" under
395// a given bound (inclusive). Note that we abort as soon as the computation
396// become too important.
397//
398// Precondition: Both bound and all added values must be >= 0.
400 public:
401 MaxBoundedSubsetSum() : max_complexity_per_add_(/*default=*/50) { Reset(0); }
402 explicit MaxBoundedSubsetSum(int64_t bound, int max_complexity_per_add = 50)
403 : max_complexity_per_add_(max_complexity_per_add) {
404 Reset(bound);
405 }
406
407 // Resets to an empty set of values.
408 // We look for the maximum sum <= bound.
409 void Reset(int64_t bound);
410
411 // Returns the updated max if value was added to the subset-sum.
412 int64_t MaxIfAdded(int64_t candidate) const;
413
414 // Add a value to the base set for which subset sums will be taken.
415 void Add(int64_t value);
416
417 // Add a choice of values to the base set for which subset sums will be taken.
418 // Note that even if this doesn't include zero, not taking any choices will
419 // also be an option.
420 void AddChoices(absl::Span<const int64_t> choices);
421
422 // Adds [0, coeff, 2 * coeff, ... max_value * coeff].
423 void AddMultiples(int64_t coeff, int64_t max_value);
424
425 // Returns an upper bound (inclusive) on the maximum sum <= bound_.
426 // This might return bound_ if we aborted the computation.
427 int64_t CurrentMax() const { return current_max_; }
428
429 int64_t Bound() const { return bound_; }
430
431 private:
432 // This assumes filtered values.
433 void AddChoicesInternal(absl::Span<const int64_t> values);
434
435 // Max_complexity we are willing to pay on each Add() call.
436 const int max_complexity_per_add_;
437 int64_t gcd_;
438 int64_t bound_;
439 int64_t current_max_;
440 std::vector<int64_t> sums_;
441 std::vector<bool> expanded_sums_;
442 std::vector<int64_t> filtered_values_;
443};
444
445// Simple DP to keep the set of the first n reachable value (n > 1).
446//
447// TODO(user): Maybe modulo some prime number we can keep more info.
448// TODO(user): Another common case is a bunch of really small values and larger
449// ones, so we could bound the sum of the small values and keep the first few
450// reachable by the big ones. This is similar to some presolve transformations.
451template <int n>
453 public:
455 : reachable_(new int64_t[n]), new_reachable_(new int64_t[n]) {
456 Reset();
457 }
458
459 void Reset() {
460 for (int i = 0; i < n; ++i) {
461 reachable_[i] = std::numeric_limits<int64_t>::max();
462 }
463 reachable_[0] = 0;
464 new_reachable_[0] = 0;
465 }
466
467 // We assume the given positive value can be added as many time as wanted.
468 //
469 // TODO(user): Implement Add() with an upper bound on the multiplicity.
470 void Add(const int64_t positive_value) {
471 DCHECK_GT(positive_value, 0);
472 const int64_t* reachable = reachable_.get();
473 if (positive_value >= reachable[n - 1]) return;
474
475 // We copy from reachable_[i] to new_reachable_[j].
476 // The position zero is already copied.
477 int i = 1;
478 int j = 1;
479 int64_t* new_reachable = new_reachable_.get();
480 for (int base = 0; j < n && base < n; ++base) {
481 const int64_t candidate = CapAdd(new_reachable[base], positive_value);
482 while (j < n && i < n && reachable[i] < candidate) {
483 new_reachable[j++] = reachable[i++];
484 }
485 if (j < n) {
486 // Eliminate duplicates.
487 while (i < n && reachable[i] == candidate) i++;
488
489 // insert candidate in its final place.
490 new_reachable[j++] = candidate;
491 }
492 }
493 std::swap(reachable_, new_reachable_);
494 }
495
496 // Returns true iff sum might be expressible as a weighted sum of the added
497 // value. Any sum >= LastValue() is always considered potentially reachable.
498 bool MightBeReachable(int64_t sum) const {
499 if (sum >= reachable_[n - 1]) return true;
500 return std::binary_search(&reachable_[0], &reachable_[0] + n, sum);
501 }
502
503 int64_t LastValue() const { return reachable_[n - 1]; }
504
505 absl::Span<const int64_t> reachable() {
506 return absl::MakeSpan(reachable_.get(), n);
507 }
508
509 private:
510 std::unique_ptr<int64_t[]> reachable_;
511 std::unique_ptr<int64_t[]> new_reachable_;
512};
513
514// Yet another variant of FirstFewValues or MaxBoundedSubsetSum.
516 public:
517 // Computes all the possible subset sums in [0, maximum_sum].
518 // Returns them sorted. All elements must be non-negative.
519 //
520 // If abort_if_maximum_reached is true, we might not return all possible
521 // subset sums as we stop the exploration as soon as a subset sum is equal to
522 // maximum_sum. When this happen, we guarantee that the last element returned
523 // will be maximum_sum though.
524 //
525 // Worst case complexity is in O(2^num_elements) if maximum_sum is large or
526 // O(maximum_sum * num_elements) if that is lower.
527 //
528 // TODO(user): We could optimize even further the case of a small maximum_sum.
529 absl::Span<const int64_t> Compute(absl::Span<const int64_t> elements,
530 int64_t maximum_sum,
531 bool abort_if_maximum_reached = false);
532
533 // Returns the possible subset sums sorted.
534 absl::Span<const int64_t> SortedSums() const { return sums_; }
535
536 private:
537 std::vector<int64_t> sums_;
538 std::vector<int64_t> new_sums_;
539};
540
541// Similar to MaxBoundedSubsetSum() above but use a different algo.
543 public:
544 // If we pack the given elements into a bin of size 'bin_size', returns
545 // largest possible sum that can be reached.
546 //
547 // This implementation allow to solve this in O(2^(num_elements/2)) allowing
548 // to go easily to 30 or 40 elements. If bin_size is small, complexity is more
549 // like O(num_element * bin_size).
550 int64_t MaxSubsetSum(absl::Span<const int64_t> elements, int64_t bin_size);
551
552 // Returns an estimate of how many elementary operations
553 // MaxSubsetSum() is going to take.
554 double ComplexityEstimate(int num_elements, int64_t bin_size);
555
556 private:
557 // We use a class just to reuse the memory and not allocate it on each query.
558 SortedSubsetSums sums_a_;
559 SortedSubsetSums sums_b_;
560};
561
562// Use Dynamic programming to solve a single knapsack. This is used by the
563// presolver to simplify variables appearing in a single linear constraint.
564//
565// Complexity is the best of
566// - O(num_variables * num_relevant_values ^ 2) or
567// - O(num_variables * num_relevant_values * max_domain_size).
569 public:
570 // Solves the problem:
571 // - minimize sum costs * X[i]
572 // - subject to sum coeffs[i] * X[i] \in rhs, with X[i] \in Domain(i).
573 //
574 // Returns:
575 // - (solved = false) if complexity is too high.
576 // - (solved = true, infeasible = true) if proven infeasible.
577 // - (solved = true, infeasible = false, solution) otherwise.
578 struct Result {
579 bool solved = false;
580 bool infeasible = false;
581 std::vector<int64_t> solution;
582 };
583 Result Solve(absl::Span<const Domain> domains,
584 absl::Span<const int64_t> coeffs,
585 absl::Span<const int64_t> costs, const Domain& rhs);
586
587 private:
588 Result InternalSolve(int64_t num_values, const Domain& rhs);
589
590 // Canonicalized version.
591 std::vector<Domain> domains_;
592 std::vector<int64_t> coeffs_;
593 std::vector<int64_t> costs_;
594
595 // We only need to keep one state with the same activity.
596 struct State {
597 int64_t cost = std::numeric_limits<int64_t>::max();
598 int64_t value = 0;
599 };
600 std::vector<std::vector<State>> var_activity_states_;
601};
602
603// Manages incremental averages.
605 public:
606 // Initializes the average with 'initial_average' and number of records to 0.
607 explicit IncrementalAverage(double initial_average)
608 : average_(initial_average) {}
610
611 // Sets the number of records to 0 and average to 'reset_value'.
612 void Reset(double reset_value);
613
614 double CurrentAverage() const { return average_; }
615 int64_t NumRecords() const { return num_records_; }
616
617 void AddData(double new_record);
618
619 private:
620 double average_ = 0.0;
621 int64_t num_records_ = 0;
622};
623
624// Manages exponential moving averages defined as
625// new_average = decaying_factor * old_average
626// + (1 - decaying_factor) * new_record.
627// where 0 < decaying_factor < 1.
629 public:
630 explicit ExponentialMovingAverage(double decaying_factor)
631 : decaying_factor_(decaying_factor) {
632 DCHECK_GE(decaying_factor, 0.0);
633 DCHECK_LE(decaying_factor, 1.0);
634 }
635
636 // Returns exponential moving average for all the added data so far.
637 double CurrentAverage() const { return average_; }
638
639 // Returns the total number of added records so far.
640 int64_t NumRecords() const { return num_records_; }
641
642 void AddData(double new_record);
643
644 private:
645 double average_ = 0.0;
646 int64_t num_records_ = 0;
647 const double decaying_factor_;
648};
649
650// Utility to calculate percentile (First variant) for limited number of
651// records. Reference: https://en.wikipedia.org/wiki/Percentile
652//
653// After the vector is sorted, we assume that the element with index i
654// correspond to the percentile 100*(i+0.5)/size. For percentiles before the
655// first element (resp. after the last one) we return the first element (resp.
656// the last). And otherwise we do a linear interpolation between the two element
657// around the asked percentile.
659 public:
660 explicit Percentile(int record_limit) : record_limit_(record_limit) {}
661
662 void AddRecord(double record);
663
664 // Returns number of stored records.
665 int64_t NumRecords() const { return records_.size(); }
666
667 // Note that this runs in O(n) for n records.
668 double GetPercentile(double percent);
669
670 private:
671 std::deque<double> records_;
672 const int record_limit_;
673};
674
675// Keep the top n elements from a stream of elements.
676//
677// TODO(user): We could use gtl::TopN when/if it gets open sourced. Note that
678// we might be slighlty faster here since we use an indirection and don't move
679// the Element class around as much.
680template <typename Element, typename Score>
681class TopN {
682 public:
683 explicit TopN(int n) : n_(n) {}
684
685 void Clear() {
686 heap_.clear();
687 elements_.clear();
688 }
689
690 void Add(Element e, Score score) {
691 if (heap_.size() < n_) {
692 const int index = elements_.size();
693 heap_.push_back({index, score});
694 elements_.push_back(std::move(e));
695 if (heap_.size() == n_) {
696 // TODO(user): We could delay that on the n + 1 push.
697 std::make_heap(heap_.begin(), heap_.end());
698 }
699 } else {
700 if (score <= heap_.front().score) return;
701 const int index_to_replace = heap_.front().index;
702 elements_[index_to_replace] = std::move(e);
703
704 // If needed, we could be faster here with an update operation.
705 std::pop_heap(heap_.begin(), heap_.end());
706 heap_.back() = {index_to_replace, score};
707 std::push_heap(heap_.begin(), heap_.end());
708 }
709 }
710
711 bool empty() const { return elements_.empty(); }
712
713 const std::vector<Element>& UnorderedElements() const { return elements_; }
714 std::vector<Element>* MutableUnorderedElements() { return &elements_; }
715
716 private:
717 const int n_;
718
719 // We keep a heap of the n highest score.
720 struct HeapElement {
721 int index; // in elements_;
722 Score score;
723 bool operator<(const HeapElement& other) const {
724 return score > other.score;
725 }
726 };
727 std::vector<HeapElement> heap_;
728 std::vector<Element> elements_;
729};
730
731// ============================================================================
732// Implementation.
733// ============================================================================
734
735inline int64_t SafeDoubleToInt64(double value) {
736 if (std::isnan(value)) return 0;
737 if (value >= static_cast<double>(std::numeric_limits<int64_t>::max())) {
738 return std::numeric_limits<int64_t>::max();
739 }
740 if (value <= static_cast<double>(std::numeric_limits<int64_t>::min())) {
741 return std::numeric_limits<int64_t>::min();
742 }
743 return static_cast<int64_t>(value);
744}
745
746// Tells whether a int128 can be casted to a int64_t that can be negated.
747inline bool IsNegatableInt64(absl::int128 x) {
748 return x <= absl::int128(std::numeric_limits<int64_t>::max()) &&
749 x > absl::int128(std::numeric_limits<int64_t>::min());
750}
751
752template <typename K, typename V>
753inline int CompactVectorVector<K, V>::Add(absl::Span<const V> values) {
754 const int index = size();
755 starts_.push_back(buffer_.size());
756 sizes_.push_back(values.size());
757 buffer_.insert(buffer_.end(), values.begin(), values.end());
758 return index;
759}
760
761template <typename K, typename V>
762inline void CompactVectorVector<K, V>::AppendToLastVector(const V& value) {
763 sizes_.back()++;
764 buffer_.push_back(value);
765}
766
767template <typename K, typename V>
769 K key, absl::Span<const V> values) {
770 CHECK_LE(values.size(), sizes_[key]);
771 sizes_[key] = values.size();
772 if (values.empty()) return;
773 memcpy(&buffer_[starts_[key]], values.data(), sizeof(V) * values.size());
774}
775
776template <typename K, typename V>
777template <typename L>
779 const std::vector<L>& wrapped_values) {
780 const int index = size();
781 starts_.push_back(buffer_.size());
782 sizes_.push_back(wrapped_values.size());
783 for (const L wrapped_value : wrapped_values) {
784 buffer_.push_back(wrapped_value.Index().value());
785 }
786 return index;
787}
788
789// We need to support both StrongType and normal int.
790template <typename K, typename V>
791inline int CompactVectorVector<K, V>::InternalKey(K key) {
792 if constexpr (std::is_same_v<K, int>) {
793 return key;
794 } else {
795 return key.value();
796 }
797}
798
799template <typename K, typename V>
800inline absl::Span<const V> CompactVectorVector<K, V>::operator[](K key) const {
801 DCHECK_GE(key, 0);
802 DCHECK_LT(key, starts_.size());
803 DCHECK_LT(key, sizes_.size());
804 const int k = InternalKey(key);
805 const size_t size = static_cast<size_t>(sizes_.data()[k]);
806 if (size == 0) return {};
807 return {&buffer_.data()[starts_.data()[k]], size};
808}
809
810template <typename K, typename V>
811inline absl::Span<V> CompactVectorVector<K, V>::operator[](K key) {
812 DCHECK_GE(key, 0);
813 DCHECK_LT(key, starts_.size());
814 DCHECK_LT(key, sizes_.size());
815 const int k = InternalKey(key);
816 const size_t size = static_cast<size_t>(sizes_.data()[k]);
817 if (size == 0) return {};
818 return absl::MakeSpan(&buffer_.data()[starts_.data()[k]], size);
819}
820
821template <typename K, typename V>
822inline std::vector<absl::Span<const V>>
823CompactVectorVector<K, V>::AsVectorOfSpan() const {
824 std::vector<absl::Span<const V>> result(starts_.size());
825 for (int k = 0; k < starts_.size(); ++k) {
826 result[k] = (*this)[k];
827 }
828 return result;
829}
830
831template <typename K, typename V>
832inline void CompactVectorVector<K, V>::clear() {
833 starts_.clear();
834 sizes_.clear();
835 buffer_.clear();
836}
837
838template <typename K, typename V>
839inline size_t CompactVectorVector<K, V>::size() const {
840 return starts_.size();
842
843template <typename K, typename V>
844inline bool CompactVectorVector<K, V>::empty() const {
845 return starts_.empty();
847
848template <typename K, typename V>
849template <typename Keys, typename Values>
851 Keys keys, Values values, int minimum_num_nodes) {
852 // Compute maximum index.
853 int max_key = minimum_num_nodes;
854 for (const K key : keys) {
855 max_key = std::max(max_key, InternalKey(key) + 1);
856 }
857
858 if (keys.empty()) {
859 clear();
860 sizes_.assign(minimum_num_nodes, 0);
861 starts_.assign(minimum_num_nodes, 0);
862 return;
863 }
864
865 // Compute sizes_;
866 sizes_.assign(max_key, 0);
867 for (const K key : keys) {
868 sizes_[InternalKey(key)]++;
869 }
870
871 // Compute starts_;
872 starts_.assign(max_key, 0);
873 for (int k = 1; k < max_key; ++k) {
874 starts_[k] = starts_[k - 1] + sizes_[k - 1];
875 }
876
877 // Copy data and uses starts as temporary indices.
878 buffer_.resize(keys.size());
879 for (int i = 0; i < keys.size(); ++i) {
880 buffer_[starts_[InternalKey(keys[i])]++] = values[i];
881 }
882
883 // Restore starts_.
884 for (int k = max_key - 1; k > 0; --k) {
885 starts_[k] = starts_[k - 1];
886 }
887 starts_[0] = 0;
888}
889
890// Similar to ResetFromFlatMapping().
891template <typename K, typename V>
892template <typename Collection>
893inline void CompactVectorVector<K, V>::ResetFromPairs(const Collection& pairs,
894 int minimum_num_nodes) {
895 // Compute maximum index.
896 int max_key = minimum_num_nodes;
897 for (const auto& [key, _] : pairs) {
898 max_key = std::max(max_key, InternalKey(key) + 1);
899 }
900
901 if (pairs.empty()) {
902 clear();
903 sizes_.assign(minimum_num_nodes, 0);
904 starts_.assign(minimum_num_nodes, 0);
905 return;
906 }
907
908 // Compute sizes_;
909 sizes_.assign(max_key, 0);
910 for (const auto& [key, _] : pairs) {
911 sizes_[InternalKey(key)]++;
912 }
913
914 // Compute starts_;
915 starts_.assign(max_key, 0);
916 for (int k = 1; k < max_key; ++k) {
917 starts_[k] = starts_[k - 1] + sizes_[k - 1];
918 }
919
920 // Copy data and uses starts as temporary indices.
921 buffer_.resize(pairs.size());
922 for (int i = 0; i < pairs.size(); ++i) {
923 const auto& [key, value] = pairs[i];
924 buffer_[starts_[InternalKey(key)]++] = value;
925 }
926
927 // Restore starts_.
928 for (int k = max_key - 1; k > 0; --k) {
929 starts_[k] = starts_[k - 1];
930 }
931 starts_[0] = 0;
932}
933
934// Similar to ResetFromFlatMapping().
935template <typename K, typename V>
936inline void CompactVectorVector<K, V>::ResetFromTranspose(
937 const CompactVectorVector<V, K>& other, int min_transpose_size) {
938 if (other.empty()) {
939 clear();
940 if (min_transpose_size > 0) {
941 starts_.assign(min_transpose_size, 0);
942 sizes_.assign(min_transpose_size, 0);
943 }
944 return;
945 }
946
947 // Compute maximum index.
948 int max_key = min_transpose_size;
949 for (V v = 0; v < other.size(); ++v) {
950 for (const K k : other[v]) {
951 max_key = std::max(max_key, InternalKey(k) + 1);
952 }
953 }
954
955 // Compute sizes_;
956 sizes_.assign(max_key, 0);
957 for (V v = 0; v < other.size(); ++v) {
958 for (const K k : other[v]) {
959 sizes_[InternalKey(k)]++;
960 }
961 }
962
963 // Compute starts_;
964 starts_.assign(max_key, 0);
965 for (int k = 1; k < max_key; ++k) {
966 starts_[k] = starts_[k - 1] + sizes_[k - 1];
967 }
968
969 // Copy data and uses starts as temporary indices.
970 buffer_.resize(other.buffer_.size());
971 for (V v = 0; v < other.size(); ++v) {
972 for (const K k : other[v]) {
973 buffer_[starts_[InternalKey(k)]++] = v;
974 }
975 }
976
977 // Restore starts_.
978 for (int k = max_key - 1; k > 0; --k) {
979 starts_[k] = starts_[k - 1];
980 }
981 starts_[0] = 0;
982}
983
984// A class to generate all possible topological sorting of a dag.
985//
986// If the graph has no edges, it will generate all possible permutations.
987//
988// If the graph has edges, it will generate all possible permutations of the dag
989// that are a topological sorting of the graph.
990//
991// Typical usage:
992//
993// DagTopologicalSortIterator dag_topological_sort(5);
994//
995// dag_topological_sort.AddArc(0, 1);
996// dag_topological_sort.AddArc(1, 2);
997// dag_topological_sort.AddArc(3, 4);
998//
999// for (const auto& permutation : dag_topological_sort) {
1000// // Do something with each permutation.
1001// }
1002//
1003// Note: to test if there are cycles, it is enough to check if at least one
1004// iteration occurred in the above loop.
1005//
1006// Note 2: adding an arc during an iteration is not supported and the behavior
1007// is undefined.
1008
1009class DagTopologicalSortIterator {
1010 public:
1012
1013 // Graph maps indices to their children. Any children must exist.
1014 explicit DagTopologicalSortIterator(int size)
1015 : graph_(size, std::vector<int>{}) {}
1017 // An iterator class to generate all possible topological sorting of a dag.
1018 //
1019 // If the graph has no edges, it will generate all possible permutations.
1020 //
1021 // If the graph has edges, it will generate all possible permutations of the
1022 // dag that are a topological sorting of the graph.
1023 //
1024 // The class maintains 5 fields:
1025 // - graph_: a vector of vectors, where graph_[i] contains the list of
1026 // elements that are adjacent to element i. This is not owned.
1027 // - size_: the size of the graph.
1028 // - missing_parent_numbers_: a vector of integers, where
1029 // missing_parent_numbers_[i] is the number of parents of element i that
1030 // are not yet in permutation_. It is always 0 except during the
1031 // execution of operator++().
1032 // - permutation_: a vector of integers, that is a topological sorting of the
1033 // graph except during the execution of operator++().
1034 // - element_original_position_: a vector of integers, where
1035 // element_original_position_[i] is the original position of element i in
1036 // the permutation_. See the algorithm below for more details.
1037
1038 class Iterator {
1039 friend class DagTopologicalSortIterator;
1041 public:
1042 using iterator_category = std::input_iterator_tag;
1043 using value_type = const std::vector<int>;
1044 using difference_type = ptrdiff_t;
1048 Iterator& operator++();
1049
1050 friend bool operator==(const Iterator& a, const Iterator& b) {
1051 return &a.graph_ == &b.graph_ && a.ordering_index_ == b.ordering_index_;
1053
1054 friend bool operator!=(const Iterator& a, const Iterator& b) {
1055 return !(a == b);
1057
1058 reference operator*() const { return permutation_; }
1059
1060 pointer operator->() const { return &permutation_; }
1061
1062 private:
1063 // End iterator.
1064 explicit Iterator(const std::vector<std::vector<int>>& graph
1065 ABSL_ATTRIBUTE_LIFETIME_BOUND,
1066 bool)
1067 : graph_(graph), ordering_index_(-1) {}
1068
1069 // Begin iterator.
1070 explicit Iterator(const std::vector<std::vector<int>>& graph
1071 ABSL_ATTRIBUTE_LIFETIME_BOUND);
1072
1073 // Unset the element at pos.
1074 void Unset(int pos);
1075
1076 // Set the element at pos to the element at k.
1077 void Set(int pos, int k);
1078
1079 // Graph maps indices to their children. Children must be in [0, size_).
1080 const std::vector<std::vector<int>>& graph_;
1081 // Number of elements in graph_.
1082 int size_;
1083 // For each element in graph_, the number of parents it has that are not yet
1084 // in permutation_. In particular, it is always 0 outside of operator++().
1085 std::vector<int> missing_parent_numbers_;
1086 // The current permutation. It is ensured to be a topological sorting of the
1087 // graph outside of operator++().
1088 std::vector<int> permutation_;
1089 // Keeps track of the original position of the element in permutation_[i].
1090 // See the comment above the class for the detailed algorithm.
1091 std::vector<int> element_original_position_;
1092
1093 // Index of the current ordering. Used to compare iterators. It is -1 if the
1094 // end has been reached.
1095 int64_t ordering_index_;
1096 };
1097
1098 Iterator begin() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
1099 return Iterator(graph_);
1101 Iterator end() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
1102 return Iterator(graph_, true);
1104
1105 void Reset(int size) { graph_.assign(size, {}); }
1106
1107 // Must be called before iteration starts or between iterations.
1108 void AddArc(int from, int to) {
1109 DCHECK_GE(from, 0);
1110 DCHECK_LT(from, graph_.size());
1111 DCHECK_GE(to, 0);
1112 DCHECK_LT(to, graph_.size());
1113 graph_[from].push_back(to);
1114 }
1115
1116 private:
1117 // Graph maps indices to their children. Children must be in [0, size_).
1118 std::vector<std::vector<int>> graph_;
1119};
1120
1121// To describe the algorithm in operator++() and constructor(), we consider the
1122// following invariant, called Invariant(pos) for a position pos in [0, size_):
1123// 1. permutations_[0], ..., permutations_[pos] form a prefix of a topological
1124// ordering of the graph;
1125// 2. permutations_[pos + 1], ..., permutations_.back() are all other elements
1126// that have all their parents in permutations_[0], ..., permutations_[pos],
1127// ordered lexicographically by the index of their last parent in
1128// permutations_[0], ... permutations_[pos] and then by their index in the
1129// graph;
1130// 3. missing_parent_numbers_[i] is the number of parents of element i that are
1131// not in {permutations_[0], ..., permutations_[pos]}.
1132// 4. element_original_position_[i] is the original position of element i of
1133// the permutation following the order described in 2. In particular,
1134// element_original_position_[i] = i for i > pos.
1135// Set and Unset maintain these invariants.
1136
1137// Precondition: Invariant(size_ - 1) holds.
1138// Postcondition: Invariant(size_ - 1) holds if the end of the iteration is not
1139// reached.
1140inline DagTopologicalSortIterator::Iterator&
1141DagTopologicalSortIterator::Iterator::operator++() {
1142 CHECK_GE(ordering_index_, 0) << "Iteration past end";
1143 if (size_ == 0) {
1144 // Special case: empty graph, only one topological ordering is
1145 // generated.
1146 ordering_index_ = -1;
1147 return *this;
1148 }
1149
1150 Unset(size_ - 1);
1151 for (int pos = size_ - 2; pos >= 0; --pos) {
1152 // Invariant(pos) holds.
1153 // Increasing logic: once permutation_[pos] has been put back to its
1154 // original position by Unset(pos), elements permutations_[pos], ...,
1155 // permutations_.back() are in their original ordering, in particular in
1156 // the same order as last time the iteration on permutation_[pos] occurred
1157 // (according to Invariant(pos).2, these are exactly the elements that have
1158 // to be tried at pos). All possibilities in permutations_[pos], ...,
1159 // permutations_[element_original_position_[pos]] have been run through.
1160 // The next to test is permutations_[element_original_position_[pos] + 1].
1161 const int k = element_original_position_[pos] + 1;
1162 Unset(pos);
1163 // Invariant(pos - 1) holds.
1164
1165 // No more elements to iterate on at position pos. Go backwards one position
1166 // to increase that one.
1167 if (k == permutation_.size()) continue;
1168 Set(pos, k);
1169 // Invariant(pos) holds.
1170 for (++pos; pos < size_; ++pos) {
1171 // Invariant(pos - 1) holds.
1172 // According to Invariant(pos - 1).2, if pos >= permutation_.size(), there
1173 // are no more elements we can add to the permutation which means that we
1174 // detected a cycle. It would be a bug as we would have detected it in
1175 // the constructor.
1176 CHECK_LT(pos, permutation_.size())
1177 << "Unexpected cycle detected during iteration";
1178 // According to Invariant(pos - 1).2, elements that can be used at pos are
1179 // permutations_[pos], ..., permutations_.back(). Starts the iteration at
1180 // permutations_[pos].
1181 Set(pos, pos);
1182 // Invariant(pos) holds.
1183 }
1184 // Invariant(size_ - 1) holds.
1185 ++ordering_index_;
1186 return *this;
1187 }
1188 ordering_index_ = -1;
1189 return *this;
1190}
1191
1192inline DagTopologicalSortIterator::Iterator::Iterator(
1193 const std::vector<std::vector<int>>& graph)
1194 : graph_(graph),
1195 size_(graph.size()),
1196 missing_parent_numbers_(size_, 0),
1197 element_original_position_(size_, 0),
1198 ordering_index_(0) {
1199 if (size_ == 0) {
1200 // Special case: empty graph, only one topological ordering is generated,
1201 // which is the "empty" ordering.
1202 return;
1203 }
1204
1205 for (const auto& children : graph_) {
1206 for (const int child : children) {
1207 missing_parent_numbers_[child]++;
1208 }
1209 }
1210
1211 for (int i = 0; i < size_; ++i) {
1212 if (missing_parent_numbers_[i] == 0) {
1213 permutation_.push_back(i);
1214 }
1215 }
1216 for (int pos = 0; pos < size_; ++pos) {
1217 // Invariant(pos - 1) holds.
1218 // According to Invariant(pos - 1).2, if pos >= permutation_.size(), there
1219 // are no more elements we can add to the permutation.
1220 if (pos >= permutation_.size()) {
1221 ordering_index_ = -1;
1222 return;
1223 }
1224 // According to Invariant(pos - 1).2, elements that can be used at pos are
1225 // permutations_[pos], ..., permutations_.back(). Starts the iteration at
1226 // permutations_[pos].
1227 Set(pos, pos);
1228 // Invariant(pos) holds.
1229 }
1230 // Invariant(pos - 1) hold. We have a permutation.
1231}
1232
1233// Unset the element at pos.
1234//
1235// - Precondition: Invariant(pos) holds.
1236// - Postcondition: Invariant(pos - 1) holds.
1237inline void DagTopologicalSortIterator::Iterator::Unset(int pos) {
1238 const int n = permutation_[pos];
1239 // Before the loop: Invariant(pos).2 and Invariant(pos).3 hold.
1240 // After the swap below: Invariant(pos - 1).2 and Invariant(pos - 1).3 hold.
1241 for (const int c : graph_[n]) {
1242 if (missing_parent_numbers_[c] == 0) permutation_.pop_back();
1243 ++missing_parent_numbers_[c];
1244 }
1245 std::swap(permutation_[element_original_position_[pos]], permutation_[pos]);
1246 // Invariant(pos).4 -> Invariant(pos - 1).4.
1247 element_original_position_[pos] = pos;
1248}
1249
1250// Set the element at pos to the element at k.
1251//
1252// - Precondition: Invariant(pos - 1) holds and k in [pos,
1253// permutation_.size()).
1254// - Postcondition: Invariant(pos) holds and permutation_[pos] has been swapped
1255// with permutation_[k].
1256inline void DagTopologicalSortIterator::Iterator::Set(int pos, int k) {
1257 int n = permutation_[k];
1258 // Before the loop: Invariant(pos - 1).2 and Invariant(pos - 1).3 hold.
1259 // After the loop: Invariant(pos).2 and Invariant(pos).3 hold.
1260 for (int c : graph_[n]) {
1261 --missing_parent_numbers_[c];
1262 if (missing_parent_numbers_[c] == 0) permutation_.push_back(c);
1263 }
1264 // Invariant(pos - 1).1 -> Invariant(pos).1.
1265 std::swap(permutation_[k], permutation_[pos]);
1266 // Invariant(pos - 1).4 -> Invariant(pos).4.
1267 element_original_position_[pos] = k;
1268}
1269
1270} // namespace sat
1271} // namespace operations_research
1272
1273#endif // OR_TOOLS_SAT_UTIL_H_
SharedTimeLimit(TimeLimit *time_limit)
Definition time_limit.h:327
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 ResetFromTranspose(const CompactVectorVector< V, K > &other, int min_transpose_size=0)
Similar to ResetFromFlatMapping().
Definition util.h:938
void ResetFromPairs(const Collection &pairs, int minimum_num_nodes=0)
Similar to ResetFromFlatMapping().
Definition util.h:895
void ResetFromFlatMapping(Keys keys, Values values, int minimum_num_nodes=0)
Definition util.h:852
void reserve(int size, int num_entries)
Definition util.h:93
void clear()
Restore to empty vector<vector<>>.
Definition util.h:834
void emplace_back(V const *begin, V const *end)
Definition util.h:155
void ReplaceValuesBySmallerSet(K key, absl::Span< const V > values)
Definition util.h:770
std::vector< absl::Span< const V > > AsVectorOfSpan() const
Definition util.h:825
void RemoveBySwap(K key, int index)
Definition util.h:141
int AddLiterals(const std::vector< L > &wrapped_values)
Definition util.h:780
size_t size() const
Size of the "key" space, always in [0, size()).
Definition util.h:841
void reserve(int size)
Reserve memory if it is already known or tightly estimated.
Definition util.h:89
void AppendToLastVector(const V &value)
Definition util.h:764
int Add(absl::Span< const V > values)
Definition util.h:755
friend bool operator==(const Iterator &a, const Iterator &b)
Definition util.h:1052
void AddArc(int from, int to)
Must be called before iteration starts or between iterations.
Definition util.h:1110
double CurrentAverage() const
Returns exponential moving average for all the added data so far.
Definition util.h:637
int64_t NumRecords() const
Returns the total number of added records so far.
Definition util.h:640
ExponentialMovingAverage(double decaying_factor)
Definition util.h:630
absl::Span< const int64_t > reachable()
Definition util.h:505
bool MightBeReachable(int64_t sum) const
Definition util.h:498
void Add(const int64_t positive_value)
Definition util.h:470
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:607
Similar to MaxBoundedSubsetSum() above but use a different algo.
Definition util.h:542
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:402
ModelRandomGenerator(const absl::BitGenRef &bit_gen_ref)
Definition util.h:333
ModelRandomGenerator(const SatParameters &params)
Definition util.h:324
int64_t NumRecords() const
Returns number of stored records.
Definition util.h:665
Percentile(int record_limit)
Definition util.h:660
Yet another variant of FirstFewValues or MaxBoundedSubsetSum.
Definition util.h:515
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:534
void Add(Element e, Score score)
Definition util.h:690
std::vector< Element > * MutableUnorderedElements()
Definition util.h:714
const std::vector< Element > & UnorderedElements() const
Definition util.h:713
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:749
int64_t SafeDoubleToInt64(double value)
Definition util.h:737
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
LinearExpr operator*(LinearExpr expr, int64_t factor)
Definition cp_model.h:1276
std::string FormatName(absl::string_view name)
This is used to format our table first row entry.
Definition util.h:207
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
ClosedInterval::Iterator end(ClosedInterval interval)
ClosedInterval::Iterator begin(ClosedInterval interval)
STL namespace.
trees with all degrees equal to
if(!yyg->yy_init)
Definition parser.yy.cc:966
static int input(yyscan_t yyscanner)