OR-Tools  8.2
sat/util.cc
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#include "ortools/sat/util.h"
15
16#include <algorithm>
17#include <cmath>
18
20
21namespace operations_research {
22namespace sat {
23
24int MoveOneUnprocessedLiteralLast(const std::set<LiteralIndex>& processed,
25 int relevant_prefix_size,
26 std::vector<Literal>* literals) {
27 if (literals->empty()) return -1;
28 if (!gtl::ContainsKey(processed, literals->back().Index())) {
29 return std::min<int>(relevant_prefix_size, literals->size());
30 }
31
32 // To get O(n log n) size of suffixes, we will first process the last n/2
33 // literals, we then move all of them first and process the n/2 literals left.
34 // We use the same algorithm recursively. The sum of the suffixes' size S(n)
35 // is thus S(n/2) + n + S(n/2). That gives us the correct complexity. The code
36 // below simulates one step of this algorithm and is made to be "robust" when
37 // from one call to the next, some literals have been removed (but the order
38 // of literals is preserved).
39 int num_processed = 0;
40 int num_not_processed = 0;
41 int target_prefix_size = literals->size() - 1;
42 for (int i = literals->size() - 1; i >= 0; i--) {
43 if (gtl::ContainsKey(processed, (*literals)[i].Index())) {
44 ++num_processed;
45 } else {
46 ++num_not_processed;
47 target_prefix_size = i;
48 }
49 if (num_not_processed >= num_processed) break;
50 }
51 if (num_not_processed == 0) return -1;
52 target_prefix_size = std::min(target_prefix_size, relevant_prefix_size);
53
54 // Once a prefix size has been decided, it is always better to
55 // enqueue the literal already processed first.
56 std::stable_partition(literals->begin() + target_prefix_size, literals->end(),
57 [&processed](Literal l) {
58 return gtl::ContainsKey(processed, l.Index());
59 });
60 return target_prefix_size;
61}
62
63void IncrementalAverage::Reset(double reset_value) {
64 num_records_ = 0;
65 average_ = reset_value;
66}
67
68void IncrementalAverage::AddData(double new_record) {
69 num_records_++;
70 average_ += (new_record - average_) / num_records_;
71}
72
73void ExponentialMovingAverage::AddData(double new_record) {
74 num_records_++;
75 average_ = (num_records_ == 1)
76 ? new_record
77 : (new_record + decaying_factor_ * (average_ - new_record));
78}
79
80void Percentile::AddRecord(double record) {
81 records_.push_front(record);
82 if (records_.size() > record_limit_) {
83 records_.pop_back();
84 }
85}
86
87double Percentile::GetPercentile(double percent) {
88 CHECK_GT(records_.size(), 0);
89 CHECK_LE(percent, 100.0);
90 CHECK_GE(percent, 0.0);
91 std::vector<double> sorted_records(records_.begin(), records_.end());
92 std::sort(sorted_records.begin(), sorted_records.end());
93 const int num_records = sorted_records.size();
94
95 const double percentile_rank =
96 static_cast<double>(num_records) * percent / 100.0 - 0.5;
97 if (percentile_rank <= 0) {
98 return sorted_records.front();
99 } else if (percentile_rank >= num_records - 1) {
100 return sorted_records.back();
101 }
102 // Interpolate.
103 DCHECK_GE(num_records, 2);
104 DCHECK_LT(percentile_rank, num_records - 1);
105 const int lower_rank = static_cast<int>(std::floor(percentile_rank));
106 DCHECK_LT(lower_rank, num_records - 1);
107 return sorted_records[lower_rank] +
108 (percentile_rank - lower_rank) *
109 (sorted_records[lower_rank + 1] - sorted_records[lower_rank]);
110}
111
112void CompressTuples(absl::Span<const int64> domain_sizes, int64 any_value,
113 std::vector<std::vector<int64>>* tuples) {
114 if (tuples->empty()) return;
115
116 // Remove duplicates if any.
118
119 const int num_vars = (*tuples)[0].size();
120
121 std::vector<int> to_remove;
122 std::vector<int64> tuple_minus_var_i(num_vars - 1);
123 for (int i = 0; i < num_vars; ++i) {
124 const int domain_size = domain_sizes[i];
125 if (domain_size == 1) continue;
126 absl::flat_hash_map<const std::vector<int64>, std::vector<int>>
127 masked_tuples_to_indices;
128 for (int t = 0; t < tuples->size(); ++t) {
129 int out = 0;
130 for (int j = 0; j < num_vars; ++j) {
131 if (i == j) continue;
132 tuple_minus_var_i[out++] = (*tuples)[t][j];
133 }
134 masked_tuples_to_indices[tuple_minus_var_i].push_back(t);
135 }
136 to_remove.clear();
137 for (const auto& it : masked_tuples_to_indices) {
138 if (it.second.size() != domain_size) continue;
139 (*tuples)[it.second.front()][i] = any_value;
140 to_remove.insert(to_remove.end(), it.second.begin() + 1, it.second.end());
141 }
142 std::sort(to_remove.begin(), to_remove.end(), std::greater<int>());
143 for (const int t : to_remove) {
144 (*tuples)[t] = tuples->back();
145 tuples->pop_back();
146 }
147 }
148}
149
150} // namespace sat
151} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
double GetPercentile(double percent)
Definition: sat/util.cc:87
void AddRecord(double record)
Definition: sat/util.cc:80
int64_t int64
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
Definition: stl_util.h:58
int MoveOneUnprocessedLiteralLast(const std::set< LiteralIndex > &processed, int relevant_prefix_size, std::vector< Literal > *literals)
Definition: sat/util.cc:24
void CompressTuples(absl::Span< const int64 > domain_sizes, int64 any_value, std::vector< std::vector< int64 > > *tuples)
Definition: sat/util.cc:112
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...